It is amazing what you can accomplish with bit twiddling.I've been working on a Protocol Buffer decoder, and I was looking for ways to optimize varint decoding. On a Google-internal list I asked how you'd transform the 64-bit integer:`````` 0aaa aaaa 0bbb bbbb 0ccc cccc 0ddd dddd 0eee eeee 0fff ffff 0ggg gggg 0hhh hhhh `````` into:`````` 0000 0000 aaaa aaab bbbb bbcc cccc cddd dddd eeee eeef ffff ffgg gggg ghhh hhhh `````` Not two hours later I had several impressive transformations that I never would have come up with on my own. The two most effective:`````` b = ((b & 0x7f007f007f007f00) >> 1) | (b & 0x007f007f007f007f); b = ((b & 0xffff0000ffff0000) >> 2) | (b & 0x0000ffff0000ffff); b = ((b & 0xffffffff00000000) >> 4) | (b & 0x00000000ffffffff); `````` and:`````` b += b & 0x007f007f007f007fULL; b += 3 * (b & 0x0000ffff0000ffffULL); b += 15 * (b & 0x00000000ffffffffULL); `````` I don't know how these guys come up with this stuff.

 "b += 15 * (b & 0x00000000ffffffffULL)" might look more magical than it actually is. The crux is:`````` b * 4 `````` is the same as`````` b << 2 `````` thus`````` b += 3 * b `````` is the same as`````` b = b << 2 `````` So plus, a multiply and a mask make it possible to shift only a subset of the bits in the integer. The first transformation uses two masks and bitwise or to achieve the same.

Search: