Bitwise & Bitshift in Java

In programming we use control flow statements to change the execution of our code. If this then that, sort of thing. I'm sure we all know the standard keywords, if, else, else if. When we use if or else if we put a condition in the parenthesis, which will return a boolean, essentially a yes do this, or a no skip this bit of code and move on.

Here's a (simple) example -

if (1 < 2) {
    System.out.println("One is less than two, well played.");
} else {
    System.out.println("Why am I here? No one listens to me.");
}

Conditional, Relational, Equality Operators

In the snippet of code above you can see the less than operator < evaluating the two operands.

An operand is a object which the operator provides a function
on. In our example above, 1 < 2, 1 and 2 would be operands.

Other operators we know and love are -

Relatioinal

• <= less than or equal to
• > greater than, >= greater than or equal to

Equality

• == equal to
• != not equal to

Conditional

• || or
• && and

The last two are interesting, have you ever seen them on their own, like | or &? Well these are the bitwise version of those conditional operators, bitwise or and bitwise and. The difference being conditional operators work by evaluating two boolean values, while bitwise operators can evaluate two booleans, or two integer types (whole numbers) by evaluating the binary representation. Lets explore them in more depth.

Integral types in Java are byte, short, int, long and
char

Bitwise Operators

Firstly lets have a little look at what an integer looks like in binary. We can use the handy static method Integer.toBinaryString(int) and output to console.

int twenty = 20;
System.out.println(Integer.toBinaryString(twenty)); // 10100

// the bits are one in position 2^2 (which equals 4) and 2^4 (16)
// 10100
// ^ ^ 
// 16 + 4 = 20

Important note: Integer.toBinaryString() does not return
extra leading zeroes. An int is 32 bits, but only the largest
bit of the value to smallest bit is shown in the returned
string.

| inclusive OR

The inclusive or operator will check the binary digits of two integer types, one column at a time, if either is binary 1, then the result is binary 1. Here's an example -

int five = 5;  // 0101
int nine = 9;  // 1001
System.out.println(Integer.toBinaryString(five | nine)); // 1101

What is happening here? Lets break it down -

// each bit in each column is compared, from left to right -
// 0 or 1, 1 or 0, 0 or 0 and finally 1 or 1

// 0101
// 1001
// ----
// 1101 == decimal 13

So you could say when a smaller integer is being compared with a bitwise or statement with a larger integer, the result will always at least the value of the bigger number.

& AND

The and operator will only result in binary one when both bits are binary one.

int three = 3; // 011
int five = 5; //  101
System.out.println(Integer.toBinaryString(three & five)); // 1 

// from right to left, 0 & 1 = 0, 1 & 0 = 0, 1 & 1 = 1
// 011
// 101
// ---
// 001

We can use & to discover whether a number is odd or even. As
the only odd digit in a binary pattern is $2^0$ , the rightmost bit, we can
use a bit mask to return the first bit, 1 or 0, odd or even, when comparing a number.

int nine = 9; // 1001
int six = 6; //  0110
//                  ^ rightmost bit
int bitMask = 1; // 0001
System.out.println(1 == (six & bitMask) ? "Odd" : "Even"); // Odd
System.out.println(1 == (nine & bitMask) ? "Odd" : "Even");// Even

A bitmask is a binary pattern which will allow us to use bitwise
operators to choose which bits of another pattern to operate on

A common way to check if a number is odd or even is using the modulus operator %, which will return the remainder between two numbers. When using modulus 2, any even number will return zero, any odd number one.

System.out.println(11 % 2); // 1, we know it's odd
System.out.println(10 % 2); // 0, we know it's even

^ exclusive or XOR

When evaluating two bits it will return 1 only when a single operand is 1.

int five = 5; // 101
int six = 6; // 110
System.out.println(Integer.toBinaryString(five ^ six)); // 11
// 101 
// 110 
// ----
// 011, decimal 3

~ unary complement / NOT

Inverts all binary one bits to zero, and all binary zero bits to one. In essence NOT 1 == 0, NOT 0 == 1.

int five = 5; // 101b
System.out.println(~five); //  
// 101
// --- NOT
// 11111111111111111111111111111010 == -6

Hold on, why is ~5, 101 in binary, inverted with a bitwise NOT ~, not 010, i.e. decimal 2? Well, computers use binary to represent numbers, both positive and negative. One way to represent negative numbers is a numbering scheme called twos complement. What this means is the leftmost bit in a binary pattern, or the most significant bit (as it's the largest number), is used to signify whether the number is positive or negative, 1 is for a negative number, 0positive. As we are using a integer primitive with our bitwise NOT here, an int is 32 bit, or 4 bytes, in size. As mentioned earlier, the method Integer.toBinaryString() omits preceeding zeroes in a pattern by default, but the rest of the int is infact filled with zeroes to the MSB on the left.

So, all those zeroes have now been inverted to ones, but how does that calculate to negative six? Binary is a summation of all bit values which are 1.

// 0111
// ^^^^
// ||||_ 2^0 == 1
// |||_ 2^1 == 2
// ||_ 2^2 == 4
// |_ 2^3 == 8
// 
// So summing the bits which are 1 gives us, 4 + 2 + 1 == 7

As the MSB is negative if it is 1, and remember our NOT operator inverted it to 1, that value is our base value before we sum the rest of the binary digits from left to right.

Lets do a example with a smaller integer type, byte which is 8 bits or, not surprisingly, one byte.

byte five = 5;
// 0x00FF is a bitmask in hexadecimal, it means we only see 8 
// bits, representing our byte primitive
System.out.println(Integer.toBinaryString(0x00FF & ~five));
// 11111010
// ||||| |
// ||||| |_ 2^1 == 2
// ||||| 
// |||||_ 2^3 == 8
// ||||_ 2^4 == 16
// |||_ 2^5 == 32
// ||_ 2^6 == 64 
// |_ -2^7 == -128 (Most significant bit)

// Doing the sum;
// -256 + 64 + 32 + 16 + 8 + 2 == -6

I hope that helps you understand quickly how we got to negative six as our bitwise NOT result, but do please check this BBC guide on twos complement for some more help if you need it as I won't go into it any deeper.

Unary means the operator works on only one
operand. For example as seen in for loops frequently, i++
unary postfix operator, increments i by one.

Bitshift

There is also some other operators known as bitshift. These move the bits left or right in a binary pattern.

<< left shift

Moves the bits in a binary pattern to n times to the left. It is represented as number << placesToShift, for example 1 << 2, moves the bits in integer one two places to the left. The effect of moving the bits multiplies the number by $2^n$ . That is to say, one left shift will multiply the number by $2^1 = 2$ . A shift two places left would be the number multiplied by $2^2 = 4$ .

System.out.println(2 << 1); // 4
// 0010 == decimal 2
// 0010 << 1 == 0100 == 4
                 ^- 
System.out.println(2 << 2) // 8
// 0010 << 2 == 1000 == 8
                ^--  

>> right shift

As above, the right shift uses the format number >> timesToShift, but it shifts the bits to the right. In effect dividing the number by $2^n$ .

int eight = 8; // 1000 
System.out.println(8 >> 1); // 2^1 == 2. 8 / 2 == 4
// 1000 >> 1 == 0100 == 4
System.out.println(8 >> 2); // 2^2 == 4. 8 / 4 == 2
// 1000 >> 2 == 0010 == 2
System.out.println(8 >> 3); // 2^3 == 8. 8 / 8 == 1
// 1000 >> 4 == 0001 == 1

Now you've read this blog you can do this quick trick to impress your coding friends, to divide any number in half integer >> 1!

With negative numbers things get a little more interesting. Remember twos compliment uses the most significant bit to declare the number positive or negative, for a positive number bits will be filled with zeroes, for a negative number bits will be filled with ones. The same method applies from the bitwise NOT example above, the binary is summed to find the resulting number.

byte negativeFour = -4;
System.out.println(Integer.toBinaryString(0x00FF & 
    negativeFour));      // 11111100
System.out.println(Integer.toBinaryString(0x00FF & 
    negativeFour >> 1)); // 11111110
//                          ^ 1 filled to the left

>>> unsigned right shift

Twos complement is a signed representation of a number in binary form. That is to say it can represent positive and negative numbers. An unsigned number has no bit that declares it one or the other, so they are always positive. In the case of the unsigned right shift, space after a shift is filled with zeroes, so any negative number will become a positive number as the MSB will no longer be 1.

int negativeFour = -4;
System.out.println(Integer.toBinaryString(negativeFour));
System.out.println(Integer.toBinaryString(negativeFour >>> 2));
System.out.println(negativeFour >>> 2);

// Output
// 11111111111111111111111111111100
// ^ MSB is 1, the number is negative
// 00111111111111111111111111111111*
// ^^ shifted two places right and filled with zeroes 
// The final output is the sum of the resulting binary,
// without a sign bit it is a positive number
// 1073741823

* I had to amend the zeroes here for example purposes. The actual output will be without the zeroes.

I hope that is clear for you, it's a little tricky to calculate these long binary patterns just looking at them.

Example use case of bitshift with booleans

There is really only one bitwise operator which isn't directly translatable with a single conditional operator and that is XOR, exclusive or.

Say you are have a staff rota application. It has employee objects, with a method that returns if they are scheduled to be at work for a given shift. You only need one worker per shift, so you have a method which checks that only one worker is scheduled on a shift at a time, using the ^ operator.

// atWork(Date) returns true if employee scheduled for work on 
// that date. Both employees are scheduled for work today.
LocalDate today = LocalDate.now();
if(emplyee1.atWork(today) ^ employee2.atWork(today) {
    // we save the rota if only one employee is working
    workRota.save();
} else {
   // reschedule one of the employees, amend the rota
}

We can make the same statement with conditional operators but it is a bit more long winded -

if (!employee.atWork(today) && employee.atWork(today) 
   || employee.atWork(today) && !employee.atWork(today))

It may be a convoluted example that you probably won't have to put in to practice yourself, but it's another tool for your toolbelt, which is never a bad thing.

Conclusion

Bitwise and bitshift can be confusing at first, possibly you've not seen them often, and you may wonder why you would use them. In fact they can be very useful in algorithms, where manipulating binary bits efficiently is very important. Mainly though, it's good that if you see these in someone else's code you can understand what is happening.

Cover image by Gerd Altmann from Pixabay