Hacker News new | comments | ask | show | jobs | submit login

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.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: