Bit Level Manipulation (Posted on April 6th, 2013)
Bit level manipulation allows us to write more efficient code due to the fact that CPU's are really good at handling bits. In fact that's all they really do. Even if you've never played around with bit manipulation it's likely that your compiler has modified your code to use bit manipulation.
Finding Odd AND Even Numbers
At some point everyone's probably written some code to this effect:
def odd_or_even(number): if number % 2 == 0: return "Even" return "Odd"
However, as we all know long division can be kind of annoying, so we don't want our program to have to do any of that. We all know that to check if a number is odd or even we just need to check the last digit. Well it turns out that the same is true for binary. In binary there is only one slot that contains an odd number, the first one. Therefore, any number with a 1 set in the first slot has to be an odd number. Most compilers realize this and change our code to something like:
def odd_or_even(number): if number & 1 == 0: return "Even" return "Odd"
The "&" operator performs a bitwise AND. If our number was 7 then it would yield 1 because only the first binary column for both numbers contains a 1. Likewise if the number was 6 then we'd get back 0.
111 (7) 001 (AND with 1) 001 110 (6) 001 (AND with 1) 000
Slide to the Left. Now Slide to the Right
Another optimization most compilers make involves division and multiplication. You probably write something like:
def double(number): return number * 2 def half(number): return number / 2
However, what you're really doing is shifting one bit to the left or one bit to the right respectively.
def double(number): return number << 1 def half(number): return number >> 1
If our number was 6 then it would yield 12 and 3.
0110 (6) 1100 (6 after being left shifted = 12) 110 (6) 011 (6 after being right shifted = 3)
Swapping Values Without a Temporary Variable
One cool trick that can be done with bit level manipulation is swapping the values of two variables with XOR. XOR compares each column and checks if they are different or the same. If they are different than the new value for that column is one, otherwise it is 0. We can take advantage of this and swap two values in place
Wikipedia has a great graphic showing how this is done with 10 and 3.
The code for this is as such:
x = 10 y = 3 x ^= y y ^= x x ^= y
On a side note, if you're using Python or Ruby you could also do something like this:
x, y = y, x
I hope you found these optimizations/tricks mildly interesting. If so, in my research for other bit level tricks I found this really cool resource which is a large compilation of tricks. A lot of interesting stuff on there.
As always if you have any feedback or questions feel free to drop them in the comments below or contact me privately on my contact page. Thanks for reading!
My name is Max Burstein and I am a graduate of the University of Central Florida and creator of Problem of the Day and Live Dota. I enjoy developing large, scalable web applications and I seek to change the world.