Java Bit Twiddling

This post explains some of the less commonly used operators in Java, namely the bitwise and bit shift operators and how they can be cleverly used to multiply or divide integers, test for evenness etc. The operators are shown in the table below:

Name	Description
~a (NOT)	Negates each bit. 0s becomes 1s and vice versa. ~a=(-a)-1
a & b (AND)	In each pair of corresponding bits, the result is 1 if the first bit is 1 AND the second bit is 1, 0 otherwise.
a | b (OR)	In each pair of corresponding bits, the result is 1 if the first bit is 1 OR the second bit is 1 OR both bits are 1, and otherwise the result is 0
a ^ b (XOR)	In each pair of corresponding bits, the result in each position is 1 if the two bits are different, and 0 if they are the same.
a << n (LEFT-SHIFT)	Shifts bit pattern to the left by n positions and places 0s on the right.
a >> n (RIGHT-SHIFT)	Shifts bit pattern to the right by n positions and places the sign-bit on the left, thus preserving the sign of the operand.
a >>> n (UNSIGNED-RIGHT-SHIFT)	Shifts bit pattern to the right by n positions and places 0s on the left.

Examples of bitwise and bit shift operators in action:

a = 3 (11)
b = 6 (110)

~a = -4 (11111111111111111111111111111100)
a & b = 2 (10)
a | b = 7 (111)
a ^ b = 5 (101)
a << 2 = 12 (1100)
b >> 1 = 3 (11)
b >>> 1 = 3 (11)

The code used to generate this is shown below:

final int a = 3; // 011
final int b = 6; // 110

System.out.printf("a = %s\t(%s)\n", a,
                 Integer.toBinaryString(a));
System.out.printf("b = %s\t(%s)\n", b,
                 Integer.toBinaryString(b));

/**
 * NOT
 */
int not = ~a;
System.out.printf("~a = %s\t(%s)\n", not,
                 Integer.toBinaryString(not));

/**
 * AND
 */
int and = a & b;
// 011
// 110
//----&
// 010
System.out.printf("a & b = %s\t(%s)\n", and,
                 Integer.toBinaryString(and));

/**
 * OR
 */
int or = a | b ;
// 011
// 110
//----|
// 111
System.out.printf("a | b = %s\t(%s)\n", or,
                 Integer.toBinaryString(or));

/**
 * XOR
 */
int xor = a ^ b ;
// 011
// 110
//----^
// 101
System.out.printf("a ^ b = %s\t(%s)\n", xor,
                 Integer.toBinaryString(xor));

/**
 * LEFT-SHIFT
 */
int lshift = a << 2;
// 00011
// ----- <<2
// 01100
System.out.printf("a << 2 = %s\t(%s)\n", lshift,
                 Integer.toBinaryString(lshift));

/**
 * RIGHT-SHIFT
 */
int rshift = b >> 1;
// 110
// ----- >>1
// 011
System.out.printf("b >> 1 = %s\t(%s)\n", rshift,
                 Integer.toBinaryString(rshift));

/**
 * UNSIGNED-RIGHT-SHIFT
 */
int urshift = b >>> 1;
// 110
// ----- >>1
// 011
System.out.printf("b >>> 1 = %s\t(%s)\n", urshift,
                 Integer.toBinaryString(urshift));

Usage of bit manipulation:
So, where do you use this? In the olden days, they were used for efficiency but most modern compilers today perform optimisations for you, so you don't have to worry about it. The bitwise and bit shift operators are not used very frequently in day-to-day programming, but here are a few scenarios where they can be used - mainly to impress you colleagues :)

1. Checking if an integer is even or odd
If an integer is odd, its rightmost bit will always be 1 and if it is even, it will always be 0. For example, 4 is 100 and 5 is 101.

public boolean isEven(int a){
    return a & 1 == 0;
}

2. Multiplying/Dividing by powers of two
Shifting to the left is just like multiplying by a power of two. For example 3 << 2 is 12. In general, a << n is a*(2^n). Keep in mind that a left shift can result in "overflow" which occurs when you exceed the limits of the range of the data type you are using and can cause unexpected behaviour.

A right shift is an integer division by a power of 2. Shifting right 1 position is the same as dividing by two. This approach is used in the Collections Framework, such as the Arrays class to find the middle element of an array. In general, a >> n is a/(2^n). Be careful, when right shifting negative integers. For example, 5 >> 1 gives 2, but -5 >> 1, gives -3.

3. Is an integer positive or negative?
Shift the integer right 31 places. The value of the far left bit is copied to the other bits. The far left bit is 1 when the value is negative and 0 otherwise.

public boolean isNegative(int a){
    return (a >> 31) != 0;
}

4. Negating an integer
You can use the NOT operator to determine the negative of any integer as shown in the snippet below. The basic idea is you invert all the bits and then add 1.

int num = 4;
int neg = ~num + 1; //-4

Note that you can also do the reverse and determine the positive of a negative integer by subtracting 1 and then inverting the bits.

5. Check if the nth bit is set
This is a more generalised version of the even/odd check. We move the 1 bit n places to the left and then apply the AND operation. If the nth bit was not set, this would result in 0.

public boolean isBitSet(int a, int n){
    return a & (1 << n) != 0;
}

6. Setting the nth bit

a | (1<<n)

7. Unsetting the nth bit

a & ~(1<<n)

8. Toggling the nth bit

a ^ (1<<n)

9. Unsetting the rightmost 1-bit

a & (a-1)

10. Checking if number is a power of 2
If the number is a power of 2, there will be only one 1-bit. If we unset this bit, we will get 0.

return (a & (a-1)) == 0;

11. Swapping values without a temporary variable
Swap two variables without a temporary variable using XOR:

x = x ^ y;
y = x ^ y;
x = x ^ y;

References:
Bit Twiddling Hacks
Java Ranch - Bit Shifting
Low Level Bit Hacks You Absolutely Must Know