Here we shall discuss some very low level Bit hacks that can really speed up your program execution time when used effectively.
Every now and then we see bit level operators. Bit hacks are ingenious little programming tricks that manipulate integers in a smart and efficient manner. Instead of performing some operation (such as counting the 1 bits in an integer) by looping over individual bits, these programming nuggets do the same with one or two carefully chosen bitwise operations.
To get things going I’ll assume that you know what the two’s complement binary representation of an integer is and also that you know all the the bitwise operations.
I’ll use the following notation for bitwise operations in the article:
& - bitwise and | - bitwise or ^ - bitwise xor ~ - bitwise not << - bitwise shift left >> - bitwise shift right
The numbers in the article are 8 bit signed integers that are represented as two’s complement and they are usually named ‘x’. The result is usually ‘y’. The individual bits of ‘x’ are named b7, b6, b5, b4, b3, b3, b2, b1 and b0. The bit b7 is the sign bit (the most significant bit), and b0 is the least significant.
I’ll start with the most basic bit hacks and gradually progress to more difficult ones. I’ll use examples to explain how each bithack works.
BITHACK 1: Check if the integer is even or odd
if ((x & 1) == 0)
{
// x is even
}
else
{
// x is odd
}
I am pretty sure everyone has seen this trick. The idea here is that an integer is odd if and only if the least significant bit b0 is 1. It follows from the binary representation of ‘x’, where bit b0 contributes to either 1 or 0. By AND-ing ‘x’ with 1 we eliminate all the other bits than b0. If the result after this operation is 0, then ‘x’ was even because bit b0 was 0. Otherwise ‘x’ was odd.
Let’s look at an example. Let’s take integer 43, which is odd. In binary 43 is 00101011. Notice that the least significant bit b0 is 1 (in bold). Now let’s AND it with 1:
00101011
& 00000001 (note: 1 is the same as 00000001)
--------
00000001
See how AND-ing erased all the higher order bits b1-b7 but left bit b0 the same it was? The result is thus 1 which tells us that the integer was odd.
BITHACK 2: Test if the n-th bit is set.
if (x & (1<<n))
{
// n-th bit is set
}
else
{
// n-th bit is not set
}
In the previous bit hack we saw that (x & 1) tests if the first bit is set. This bit hack improves this result and tests if n-th bit is set. It does it by shifting that first 1-bit n positions to the left and then doing the same AND operation, which eliminates all bits but n-th.
Here is what happens if you shift 1 several positions to the left:
1 00000001 (same as 1<<0) 1<<1 00000010 1<<2 00000100 1<<3 00001000 1<<4 00010000 1<<5 00100000 1<<6 01000000 1<<7 10000000
Now if we AND ‘x’ with 1 shifted n positions to the left we effectively eliminate all the bits but n-th bit in ‘x’. If the result after AND-ing is 0, then that bit must have been 0, otherwise that bit was set.
Let’s look at an example.
Does 122 have 3rd bit set? The operation we do to find it out is:
122 & (1<<3)
Now, 122 is 01111010 in binary. And (1<<3) is 00001000.
01111010
& 00001000
--------
00001000
We see that the result is not 0, so yes, 122 has the 3rd bit set.
BITHACK 3: Set the n-th bit
y = x | (1<<n)
This bit hack combines the same (1<<n) trick of setting n-th bit by shifting with OR operation. The result of OR-ing a variable with a value that has n-th bit set is turning that n-th bit on. It’s because OR-ing any value with 0 leaves the value the same; but OR-ing it with 1 changes it to 1 (if it wasn’t already). Let’s see how that works in action:
Suppose we have value 120, and we wish to turn on the 2nd bit.
01111000 (120 in binary)
| 00000100 (1<<2)
--------
01111100
BITHACK 4: Unset the n-th bit
y = x & ~(1<<n)
The important part of this bithack is the ~(1<<n) trick. It turns on all the bits except n-th.
Here is how it looks:
~1 11111110 (same as ~(1<<0)) ~(1<<1) 11111101 ~(1<<2) 11111011 ~(1<<3) 11110111 ~(1<<4) 11101111 ~(1<<5) 11011111 ~(1<<6) 10111111 ~(1<<7) 01111111
The effect of AND-ing variable ‘x’ with this quantity is eliminating n-th bit. It does not matter if the n-th bit was 0 or 1, AND-ing it with 0 sets it to 0.
Here is an example. Let’s unset 4th bit in 127:
01111111 (127 in binary)
& 11101111 (~(1<<4))
--------
01101111
BITHACK 5: Toggle the n-th bit
y = x ^ (1<<n)
This bit hack also uses the wonderful “set n-th bit shift hack” but this time it XOR’s it with the variable ‘x’. The result of XOR-ing something with something else is that if both bits are the same, the result is 0, otherwise it’s 1. How does it toggle n-th bit? Well, if n-th bit was 1, then XOR-ing it with 1 changes it to 0; conversely, if it was 0, then XOR-ing it with 1 changes it to 1. See, the bit got flipped.
Here is an example. Suppose you want to toggle 5th bit in value 01110101:
01110101
^ 00100000
--------
01010101
What about the same value but 5th bit originally 0?
01010101
^ 00100000
--------
01110101
Notice something? XOR-ing the same bit twice returned it to the same value. This nifty little trick can be used in many programming questions.