“Bitwising” – Bitwise Operations in Java

I have a bad memory concerning particular details of programming languages which I don’t use very often, and bitwise operations are a good example of such details. Therefore, I decided to develop a Java program that serves the purpose of recapping the concepts that I’ve learned in school a few years ago.

In the following table one may find a short overview of the operations that are covered in the simple program below.

Operator Name Description Examples
~ not Unary operation that performs logical negation on each bit. After negation, bits that have the value 0 will have value 1 and the ones having value 1 will have value 0. ~4 = -5

~ 00000100

=11111011

& and Performs the logical AND operation on pairs of corresponding bits of the different numbers. The result is 1 if the pair of bits under comparison is 1, and 0 otherwise. 7&1 = 1

00000111 &

00000001 =

00000001

| or Performs the logical inclusive OR operation on pairs of corresponding bits of the different numbers. The result is 1 if at least one of the bits of the pair under comparison is 1, and 0 otherwise. 7 | 1 = 7

00000111 |

00000001 =

00000111

^ xor Performs the exclusive OR operation on pairs of corresponding bits of the different numbers. The result is 1 if the pair of bits under comparison is different, and 0 otherwise. 7^1 = 6

00000111 ^

00000001 =

00000110

<< signed left shift Shifts the bit pattern on the left operand n positions to the left. Value n is specified by the right hand side operand. Bits with value of 0 are shifted into the low order positions. Equivalent to multiply by 2, the result of the operation value << n is the same as calculating the expression value * (2^n).  7 << 2 = 28

00000111 << 2

=00011100

>> signed right shift Shifts the bit pattern on the left operand n positions to the right. Value n is specified by the right hand side operand. Bits with value of 0 or 1 are shifted into the high order positions in order to preserve the sign. Equivalent to divide by 2. the result of the operation value >> n is the same as calculating the expression value / (2^n). 7 >> 2 = 1

00000111 >> 2

=00000001

>>> unsigned right shift This operation is identical to the signed right shift operation with the exception that it inserts 0 in the high order bits, therefore the sign value may change.

If the left hand side operand is positive, the result will be the same as the signed right shift operation.

If the left hand side operand is negative, the result is equivalent to right shift n positions, specified by the value on the right hand side operand, of the bit pattern on the left-hand side operand. As the high order bits will be zero filled, the sign may change.

 

7 >>> 2 = 1

00000111 >>> 2

=00000001

 

Note: An example with negative numbers is provided in the source code.

Bitwise Operators Demo

The program is rather simple. It generates two random numbers between 0 and 5000, and then applies the bitwise operations to the numbers generated.

A special method for printing the binary representation of the number was used
because AFAIK the method “Integer.toBinaryString(…)” does not return the most
significant part of the binary numbers and for my purpose I wanted to have this
part represented in the output.

Output

The generated output is a set of messages containing the results of the performed
operations, and looks like this:

* Operator: AND &
 Binary representation: 00001000 10101101 - Decimal Representation: 2221
 Binary representation: 00000101 00001000 - Decimal Representation: 1288
 Binary representation: 00000000 00001000 - Decimal Representation: 8


Source Code


package examples.operators.bitwise;

import java.util.Random;

public class BitwiseOperators
{
public static void main(String[] args)
{
System.out.println("*************************");
System.out.println("* Bitwise Operators Demo");
System.out.println("*************************");

// generate a random Integer between 0 and 5000
Random randomNumber = new Random();
int firstValueGenerated = randomNumber.nextInt(5000);
int secondValueGenerated = randomNumber.nextInt(5000);

System.out.println("First Generated Integer: " + firstValueGenerated);
System.out.println("Second Generated Integer: " + secondValueGenerated);

// print generated numbers in binary
IntToBinary(firstValueGenerated);
IntToBinary(secondValueGenerated);

System.out.println(" ");
System.out.println("*************************");
System.out.println("* Operations & Results   ");
System.out.println("*************************");

System.out.println(" ");
System.out.println("* Operator: NOT (Complement) ~ ");
IntToBinary(firstValueGenerated);
IntToBinary(~firstValueGenerated);

System.out.println(" ");
System.out.println("* Operator: Negative -");
IntToBinary(firstValueGenerated);
IntToBinary(-firstValueGenerated);

System.out.println(" ");
System.out.println("* Operator: AND &");

IntToBinary(firstValueGenerated);
IntToBinary(secondValueGenerated);
IntToBinary(firstValueGenerated & secondValueGenerated);

System.out.println(" ");
System.out.println("* Operator: OR |");

IntToBinary(firstValueGenerated);
IntToBinary(secondValueGenerated);
IntToBinary(firstValueGenerated | secondValueGenerated);

System.out.println(" ");
System.out.println("* Operator: XOR ^");

// 1 if the two bits are different, and 0 if they are the same.
IntToBinary(firstValueGenerated);
IntToBinary(secondValueGenerated);
IntToBinary(firstValueGenerated ^ secondValueGenerated);

System.out.println(" ");
System.out.println("* Operator: Signed left shift << (i.e. value << 2)");

IntToBinary(firstValueGenerated);
IntToBinary(firstValueGenerated << 2);

System.out.println(" ");
System.out.println("* Operator: Signed right shift >> (i.e. value >> 2)");

IntToBinary(firstValueGenerated);
IntToBinary(firstValueGenerated >> 2);

System.out.println(" ");
System.out.println("* Operator: Unsigned right shift >>> (i.e. value >>> 2)");

IntToBinary(firstValueGenerated);
IntToBinary(firstValueGenerated >>> 2);

System.out.println(" ");
System.out.println("* Operator: Unsigned right shift >> (Negative values: -16 >> 2)");
IntToBinary(-16);
IntToBinary(-16 >> 2);

System.out.println(" ");
System.out.println("* Operator: Unsigned right shift >>> (Negative values: -16 >>> 2)");
IntToBinary(-16);
IntToBinary(-16 >>> 2);

System.out.println(" ");
System.out.println("* Operator: Unsigned right shift >>> (Negative values: -1 >>> 24)");
IntToBinary(-1);
IntToBinary(-1 >>> 24);
}

private static void IntToBinary(int number)
{
String binaryNumber = new String();

// used for formatting the string
int counter = 0;

// check each bit of the number
for (int i = 31; i >= 0; i--)
{
/*
* Here we are interested in the result of the AND operation:
*
* If the AND operation returns a binary number different than 0
* that means that there was a match between the "mask" that we
* are applying and the number, therefore the string value will be 1
*
* If the AND operation returns 0 that means that the "mask" didn't
* match any bit of the number, therefore the number will be 0
*
*/

if( ((1 << i) & number) != 0)
{
binaryNumber += "1";
}
else
{
binaryNumber += "0";
}

// separate each 8 bits with a space except the last octet
counter++;
if(counter % 8 == 0 && i != 0)
{
binaryNumber += " ";
}
}

System.out.println("Binary representation: " + binaryNumber +
" - Decimal Representation: " + number);
}
}

Feel free to comment out and to suggest new topics or examples or if you think that something should be more detailed or explained.

 

undefined reference to __udivdi3

During the last month I have been playing with real-time scheduling in the Linux kernel. Basically, I’ve downloaded  the SCHED_DEADLINE implementation from their git repository and did some changes in some files in order to understand better how real-time task scheduling can be handled in Linux.

I used a 64-bit machine with Ubuntu and Eclipse CDT version to implement my modifications. You may wonder why did I use Eclipse? The answer to that is simply: Eclipse is one of the best tools that I know that besides being an excellent IDE (Integrated Development Environment) it has great code indexing and cross-reference capabilities. Moving on to the subject of this post, in my 64-bit machine I’m able to compile the modified version of kernel without any kind of problems but I’m not able to run my version. After some discussion with an expert in the subject, he told me that probably I wasn’t compiling the correct modules that would allow me to run the OS without any problems. After some thoughts on the subject, I decided to compile the same modified version in a 32-bit machine which I wasn’t using anymore, to see if I was able to, at least, run my modified version of the Linux kernel.

I confess that initially I thought that the compilation process would be smooth, but I got surprised when the code didn’t compile and gcc threw the error undefined reference to __udivdi3.

After some googling, I discovered that the error was thrown in a line where a division involving u64 data types was being conducted. Indeed I’ve found some good pointers to the problem, namely:

- http://kerneltrap.org/mailarchive/linux-kernel-newbies/2009/2/5/4902104

- https://bugs.launchpad.net/ubuntu/+source/linux-meta/+bug/237528

So, it looks like the problem is caused by a compatibility problem between the kernel sources and gcc v4.3. Well, that would make sense initially when I was using that version in the 32-bit machine. But after an upgrade of the gcc version to 4.4.3, I still get the error in my 32-bit machine and surprisingly with the same version in my 64-bit machine it compiles smoothly. So, is the error related to the machine’s architecture? Let’s see each machine’s architecture:

64-bit machine architecture: “model name    : AMD Turion(tm) X2 Dual-Core Mobile RM-74″

32-bit machine architecture: “model name    : Intel(R) M processor 1.60GHz”

After some googling (once again), I’ve found this thread that somehow fundaments my suspicions:

http://stackoverflow.com/questions/1063585/udivdi3-undefined-howto-find-code

Indeed it was an architecture issue. After modifying my code, by using the do_div function to perform a 64 bit division in a 32-bit architecture, the code compiled like a charm.

Regarding this type of operations, the following pointer is also helpful: http://www.captain.at/howto-udivdi3-umoddi3.php

And now let’s run the kernel ;).

Welcome to geekisms!

Please allow me to present myself for the sake of good manners :). I’m just an unknown guy who loves to play with technology. This blog contains nothing more than some of my experiences with several types of devices and software, Most of the experiences target operating systems, virtual machines, embedded systems and many other interesting topics around the above ones. I hope that some of the content presented in the blog suit your needs. Any ideas or suggestions are welcomed. Thank you very much for visiting.

Follow

Get every new post delivered to your Inbox.