To inaugurate my latest attempt at a blog, I want to talk about something cool I’ve read about lately. I’ve received this question a couple times at interviews, and I think it was just to demonstrate that I could work with bitwise values.
For instance, take the number 57:
57 = 00111001
It’s easy enough to see that 57 has 4 bits set to 1. How do you check that in code? My answer has always been to loop through the number of bits (in this case 8, but usually 32), shifting to the right each time and then count how often the lowest bit comes up as a 1.
value = 57
count = 0
for i in xrange(8):
count += (value >> i) & 1
Effectively what I’m doing here is just looping through the 8 bits, rotating the value to the right and stripping off the least significant bit and adding it to the total (if it’s 1, then it adds to the total).
Since I’m using python for the example, I can abbreviate it a bit like this:
count1s = lambda x: sum( (x >> i) & 1 for i in xrange(32) )
That’s more compact, certainly, but it’s still linear time with respect to the number of bits that you are examining, and that’s where today’s coolness comes into play. It turns out there’s a log time algorithm for doing this.
Because it can get a bit long when I show all my work long-hand, let me jump straight to the code that will give the results for an 8 bit integer in 3 steps (and could be extended to do 32 bits in 5 steps, and so on):
x = 57
y = (x & 0x55) + ((x & 0xaa) >> 1)
y = (y & 0x33) + ((y & 0xcc) >> 2)
y = (y & 0x0f) + ((y & 0xf0) >> 4)
Follow through the link if you want the nitty gritty.