Bitwise operations

bitwise operator

An operator that manipulates the bits of one or more of its operands individually and in parallel. Examples include the binary logical operators (&, |, ^), the binary shift operators (<<, >>, >>>) and the unary one’s complement operator (~).

REMEMBER : wherever possible, always prefer bit manipulation to other techniques.

^ - bitwise exclusive OR - bitwise XOR

Swapping numbers using bitwise operations

The beauty of this method is, we do not have to worry about the datatype of the input variables. Or, their limits. We don’t have to worry about overflows. This will work in any language, including the ones that do not support overflows.

public static ImmutablePair swapUsingBitwiseManipulation(ImmutablePair pair) {
    int a = (int) pair.left;
    int b = (int) pair.right;

    a = a ^ b;
    b = a ^ b; // actually (a ^ b) ^ b, which would give us a -> assign this value to b.
    a = a ^ b; // which is, (a ^ b) -((a ^ b) ^ b) = (a ^ b) ^ a = b -> assign this value to a.

    return new ImmutablePair(a, b);
  }

Find out whether there is an odd number (one that doesn’t match the others - not divisible by 2 odd numbers) in an array

A XOR B XOR C XOR D XOR E is true iff an odd number of the variables are true.

1. Bits for 0 - 0000
1. Bits for 9 - 1001
1. Bits for 3 - 0011
1. Bits for 7 - 0111

1. XOR on 0 and { 9, 3, 9, 3, 9, 7, 9 }
1. XOR on 0 and 9 - 0000 1001 ---- 1001
1. XOR on 1001 and 3 - 1001 0011 ---- 1010
1. XOR on 1010 and 9 - 1010 1001 ---- 0011
1. XOR on 0011 and 3 - 0011 0011 ---- 0000
1. XOR on 0000 and 9 - 0000 1001 ---- 1001
1. XOR on 1001 and 7 - 1001 0111 ---- 1110
1. XOR on 0000 and 9 - 1110 1001 ---- 0111 - this evaluates to 7

Reading material

If you want to learn more about Bitwise operator in Java and Programming in general, read the book Hackers Delight by Henry S. Warren. Its the bible to learn about bitwise and bitshift operation and revered by expert programmers.