7 ms·
Bit Twiddling Hacks
- adrianN 16y agoNowadays things like these should only be interesting to compiler writers.
- natemartin 16y agoMight still be useful for some embedded applications.
- Xk 16y agoBelieve it or not, there are still programs that require blazingly fast bit operations. I used like ten different bit hacks for a game engine I wrote which uses bitboards[1]. [1] http://en.wikipedia.org/wiki/Bitboard http://en.wikipedia.org/wiki/Bitboard
- gaius 16y agoIt's no surprise this is hosted on graphics.stanford.edu.
- akdubya 16y agoBitwise operations pop up fairly often in advanced data structures (Hash Array Mapped Tries, Bloom Filters, etc). The big advantage in my view is being able to perform complex, data-intensive tasks in otherwise limited environments (e.g., mobile devices).
- cultureulterior 16y agoThere are algorithms that use bits just like there are algorithms that use trees. You wouldn't expect your compiler to write your algorithms for you, would you. Just recently, I've used the bitboards representation for cellular automata (which lets you compute 64 cells at the same time by doing about 100 non-branching integer instructions). I have difficulty seeing a compiler that can recognize that algorithmic optimization.
- andreasvc 16y agoI took him to mean that compiler writers should provide these bit operations in the most efficient manner on the current platform, e.g. __builtin_ctzl instead of directly using assembly or using arithmetical solutions.
- haberman 16y agoIt 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.
- gorset 16y ago"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.
- Thasc 16y agoI had no idea there was a patented way to compute the absolute value of an integer. Insane.
- scorchin 16y agoWhenever a discussion on rearranging bits and bytes comes up, I can't help but recommend Hacker's Delight by Henry S. Warren http://amzn.com/0201914654 http://amzn.com/0201914654
- anthonyb 16y agoYep, I just got that from Amazon a few days ago. I'm a Python/Web programmer in my day job, but I'm looking to get more into the low level stuff. I recently got a Nerdkit too - lots of fun :)
- deleted 16y ago[deleted]
- azar1 16y agoThis page was a life saver in my fall CS class.
- reichstein 16y agoBit-fiddling at the C-level isn't necessarily faster on all platforms. E.g., the "masked combine bits" case where he says that r = a ^ ((a ^ b) & mask) is one operation shorter than r = (a ^ ~mask) | (b ^ mask). On ARM, the (a ^ ~mask) can be performed by one instruction, so the instruction count is actually the same, and the latter way of doing it parallelizes better (only a dependency depth of two instead of three). I.e., the "optimized" version is actually likely to be slower on some CPUs.