I decided to write an article about a thing that is second nature to embedded systems programmers – low level bit hacks. Bit hacks are ingenious little programming tricks that manipulate integers in a smart and efficient manner. Instead of performing operations (such as counting the number of 1 bits in an integer) by looping over individual bits, these programming tricks 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
Numbers in this article are 8 bit signed integers (though the operations work on arbitrary length 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 most significant bit (or in signed arithmetic - sign 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.
If you like this topic, you can subscribe to my blog, or you can just read along. There is also going to be the second part of this article where I'll cover more advanced bit hacks, and I'll also release a cheat sheet with all these bit tricks.
Here we go!
Bit Hack #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 some examples. 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.
Now let's look at -43. Just as a reminder, a quick way to find negative of a given number in two's complement representation is to invert all bits and add one. So -43 is 11010101 in binary. Again notice that the last bit is 1, and the integer is odd. (Note that if we used one's complement it wouldn't be true!)
Now let's take a look at an even integer 98. In binary 98 is 1100010.
01100010
& 00000001
--------
00000000
After AND-ing the result is 0. It means that the bit b0 of original integer 98 was 0. Thus the given integer is even.
Now the negative -98. It's 10011110. Again, bit b0 is 0, after AND-ing, the result is 0, meaning -98 is even, which indeed is true.
Bit Hack #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 some examples.
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.
Note: In my article bit numeration starts with 0. So it's 0th bit, 1st bit, ..., 7th bit.
What about -33? Does it have the 5th bit set?
11011111 (-33 in binary)
& 00100000 (1<<5)
--------
00000000
Result is 0, so the 5th bit is not set.
Bit Hack #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 want to turn on the 2nd bit.
01111000 (120 in binary)
| 00000100 (1<<2)
--------
01111100
What about -120 and 6th bit?
10001000 (-120 in binary)
| 01000000 (1<<6)
--------
11001000
Bit Hack #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
Bit Hack #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 with 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 XOR property is used in calculating parity in RAID arrays and used in simple cryptography cyphers, but more about that in some other article.
Bit Hack #6. Turn off the rightmost 1-bit.
y = x & (x-1)
Now it finally gets more interesting!!! Bit hacks #1 - #5 were kind of boring to be honest.
This bit hack turns off the rightmost one-bit. For example, given an integer 00101010 (the rightmost 1-bit in bold) it turns it into 00101000. Or given 00010000 it turns it into 0, as there is just a single 1-bit.
Here are more examples:
01010111 (x)
& 01010110 (x-1)
--------
01010110
01011000 (x)
& 01010111 (x-1)
--------
01010000
10000000 (x = -128)
& 01111111 (x-1 = 127 (with overflow))
--------
00000000
11111111 (x = all bits 1)
& 11111110 (x-1)
--------
11111110
00000000 (x = no rightmost 1-bits)
& 11111111 (x-1)
--------
00000000
Why does it work?
If you look at the examples and think for a while, you'll realize that there are two possible scenarios:
-
The value has the rightmost 1 bit. In this case subtracting one from it sets all the lower bits to one and changes that rightmost bit to 0 (so that if you add one now, you get the original value back). This step has masked out the rightmost 1-bit and now AND-ing it with the original value zeroes that rightmost 1-bit out.
-
The value has no rightmost 1 bit (all 0). In this case subtracting one underflows the value (as it's signed) and sets all bits to 1. AND-ing all zeroes with all ones produces 0.
Bit Hack #7. Isolate the rightmost 1-bit.
y = x & (-x)
This bit hack finds the rightmost 1-bit and sets all the other bits to 0. The end result has only that one rightmost 1-bit set. For example, 01010100 (rightmost bit in bold) gets turned into 00000100.
Here are some more examples:
10111100 (x)
& 01000100 (-x)
--------
00000100
01110000 (x)
& 10010000 (-x)
--------
00010000
00000001 (x)
& 11111111 (-x)
--------
00000001
10000000 (x = -128)
& 10000000 (-x = -128)
--------
10000000
11111111 (x = all bits one)
& 00000001 (-x)
--------
00000001
00000000 (x = all bits 0, no rightmost 1-bit)
& 00000000 (-x)
--------
00000000
This bit hack works because of two's complement. In two's complement system -x is the same as ~x+1. Now let's examine the two possible cases:
- There is a rightmost 1-bit bi. In this case let's pivot on this bit and divide all other bits into two flanks - bits to the right and bits to the left. Remember that all the bits to the right bi-1, bi-2 ... b0 are 0's (because bi was the rightmost 1-bit). And bits to the left are the way they are. Let's call them bi+1, ..., bn.
Now, when we calculate -x, we first do ~x which turns bit bi into 0, bits bi-1 ... b0 into 1s, and inverts bits bi+1, ..., bn, and then we add 1 to this result.
Since bits bi-1 ... b0 are all 1's, adding one makes them carry this one all the way to bit bi, which is the first zero bit.
If we put it all together, the result of calculating -x is that bits bi+1, ..., bn get inverted, bit bi stays the same, and bits bi-1, ..., b0 are all 0's.
Now, AND-ing x with -x makes bits bi+1, ..., bn all 0, leaves bit bi as is, and sets bits bi-1, ..., b0 to 0. Only one bit is left, it's the bit bi - the rightmost 1-bit.
- There is no rightmost 1-bit. The value is 0. The negative of 0 in two's complement is also 0. 0&0 = 0. No bits get turned on.
We have proved rigorously that this bithack is correct.
Bit Hack #8. Right propagate the rightmost 1-bit.
y = x | (x-1)
This is best understood by an example. Given a value 01010000 it turns it into 01011111. All the 0-bits right to the rightmost 1-bit got turned into ones.
This is not a clean hack, tho, as it produces all 1's if x = 0.
Let's look at more examples:
10111100 (x)
| 10111011 (x-1)
--------
10111111
01110111 (x)
| 01110110 (x-1)
--------
01110111
00000001 (x)
| 00000000 (x-1)
--------
00000001
10000000 (x = -128)
| 01111111 (x-1 = 127)
--------
11111111
11111111 (x = -1)
| 11111110 (x-1 = -2)
--------
11111111
00000000 (x)
| 11111111 (x-1)
--------
11111111
Let's prove it, though not as rigorously as in the previous bithack (as it's too time consuming and this is not a scientific publication). There are two cases again. Let's start with easiest first.
-
There is no rightmost 1-bit. In that case x = 0 and x-1 is -1. -1 in two's complement is 11111111. OR-ing 0 with 11111111 produces the same 11111111. (Not the desired result, but that's the way it is.)
-
There is the rightmost 1-bit bi. Let's divide all the bits in two groups again (like in the previous example). Calculating x-1 modifies only bits to the right, turning bi into 0, and all the lower bits to 1's. Now OR-ing x with x-1 leaves all the higher bits (to the left) the same, leaves bit bi as it was 1, and since lower bits are all low 1's it also turns them on. The result is that the rightmost 1-bit got propagated to lower order bits.
Bit Hack #9. Isolate the rightmost 0-bit.
y = ~x & (x+1)
This bithack does the opposite of #7. It finds the rightmost 0-bit, turns off all bits, and sets this bit to 1 in the result. For example, it finds the zero in bold in this number 10101011, producing 00000100.
More examples:
10111100 (x)
--------
01000011 (~x)
& 10111101 (x+1)
--------
00000001
01110111 (x)
--------
10001000 (~x)
& 01111000 (x+1)
--------
00001000
00000001 (x)
--------
11111110 (~x)
& 00000010 (x+1)
--------
00000010
10000000 (x = -128)
--------
01111111 (~x)
& 10000001 (x+1)
--------
00000001
11111111 (x = no rightmost 0-bit)
--------
00000000 (~x)
& 00000000 (x+1)
--------
00000000
00000000 (x)
--------
11111111 (~x)
& 00000001 (x+1)
--------
00000001
Proof: Suppose there is a rightmost 0-bit. Then ~x turns this rightmost 0 bit into 1 bit. And so does x+1 (because bits more right to the rightmost 0 bit are 1's). Now AND-ing ~x with x+1 evaporates all the bits up to this rightmost 0 bit. This is the highest order bit set in the result. Now what about lower order bits to the right of rightmost 0 bit? They also got evaporated because because x+1 turned them into 0's (they were 1's) and ~x turned them into 0's. They got AND-ed with 0 and evaporated.
Bit Hack #10. Turn on the rightmost 0-bit.
y = x | (x+1)
This hack changes the rightmost 0-bit into 1. For example, given an integer 10100011 it turns it into 10100111.
More examples:
10111100 (x)
| 10111101 (x+1)
--------
10111101
01110111 (x)
| 01111000 (x+1)
--------
01111111
00000001 (x)
| 00000010 (x+1)
--------
00000011
10000000 (x = -128)
| 10000001 (x+1)
--------
10000001
11111111 (x = no rightmost 0-bit)
| 00000000 (x+1)
--------
11111111
00000000 (x)
| 00000001 (x+1)
--------
00000001
Here is the proof as a bunch of true statements. OR-ing x with x+1 does not lose any information. Adding 1 to x fills the first rightmost 0. The result is max{x, x+1}. If x+1 overflows it's x and there were no 0 bits. If it doesn't, it's x+1 which just got rightmost bit filled with 1.
Hacker's Delight
There's a book 300 pages long entirely about bit hacks like these. It's called Hacker's Delight. Take a look. If you liked the contents of my post, then you'll love this book.
Bonus stuff
If you decide to play more with these hacks, here are a few utility functions to print binary values of 8 bit signed integers in Perl, Python and C.
Print binary representation in Perl:
sub int_to_bin {
my $num = shift;
print unpack "B8", pack "c", $num;
}
Or you can print it from command line right away:
perl -wle 'print unpack "B8", pack "c", shift' <integer> # For example: perl -wle 'print unpack "B8", pack "c", shift' 113 01110001 perl -wle 'print unpack "B8", pack "c", shift' -- -128 10000000
Print binary number in Python:
def int_to_bin(num, bits=8):
r = ''
while bits:
r = ('1' if num&1 else '0') + r
bits = bits - 1
num = num >> 1
print r
Print binary representation in C:
void int_to_bin(int num) {
char str[9] = {0};
int i;
for (i=7; i>=0; i--) {
str[i] = (num&1)?'1':'0';
num >>= 1;
}
printf("%s\n", str);
}
Have fun with these. I'll write about advanced bit hacks next. See you then!