4 ms·
Bit Twiddling Hacks
- simias 14y agoAn oldie but a goodie. Mandatory warning: please don't use those unless you really know what you're doing. Most modern CPUs have instructions for computing all of that stuff and the compiler will try to use them. Those clever hacks might actually hurt both readability and performance if they're misused. Typically on PC architectures (and even on most modern embedded systems) you shouldn't have to use those hacks.
- deleted 14y ago[deleted]
- nitrogen 14y agoI've used similar techniques (such as reciprocal multiplication, which is not mentioned on this page) to provide a significant speed advantage for some code on ARM systems. Actual performance-sensitive code, such as the core routines video codecs, is still written in assembly language or with intrinsics.
- pandaman 14y agoIt's a little known fact that >> in C++ (and I suspect in C as well) on a signed type is not guaranteed to be an arithmetical shift. It's up to the implementation and most implementation choose arithmetical shift for signed and logical shift for unsigned but this does not mean that all the implementations do this. So some of this tricks are contingent on the particular implementation specific behavior.
- csmatt 14y agoStrange, I was using this the other day for the TI Launchpad-based project I'm working on.
- jwecker 14y agoClassic compilation. Always check for cpu builtin functions (rtfm gcc) first though when you need this kind of optimization "in real life."
- DanielRibeiro 14y agoFormer conversations: http://news.ycombinator.com/item?id=2570269 http://news.ycombinator.com/item?id=2570269 http://news.ycombinator.com/item?id=3452408 http://news.ycombinator.com/item?id=3452408 http://news.ycombinator.com/item?id=513935 http://news.ycombinator.com/item?id=513935 http://news.ycombinator.com/item?id=2630593 http://news.ycombinator.com/item?id=2630593 http://news.ycombinator.com/item?id=4590134 http://news.ycombinator.com/item?id=4590134 http://news.ycombinator.com/item?id=86419 http://news.ycombinator.com/item?id=86419
- halayli 14y agoOn a similar note: http://www.amazon.com/gp/product/0321842685/ref=s9_simh_gw_p14_d0_i1?pf_rd_m=ATVPDKIKX0DER&pf_rd_s=center-2&pf_rd_r=1QMBXBDPHW9X6ZJ1KDN9&pf_rd_t=101&pf_rd_p=1389517282&pf_rd_i=507846 http://www.amazon.com/gp/product/0321842685/ref=s9_simh_gw_p...
- jasomill 14y agoWhile we're posting Amazon links, http://www.amazon.com/Art-Computer-Programming-Combinatorial-Algorithms/dp/0201038048 http://www.amazon.com/Art-Computer-Programming-Combinatorial... has a fascinating 200+ page section on Boolean and bitwise tricks and techniques (Knuth: "A trick is a clever idea that can be used once, while a technique is a trick that can be used at least twice.").
- zxcdw 14y agoI think the real value of these hacks is to understand how and they work rather than the possible efficiency gains they may give. Sure, sometimes you just have to get the gains, but these days, on modern platforms this is hardly ever the case. But man, if you think you know how to deal with the binary and bitwise operations, please take some time to go through all of the hacks and examine how they work. It's quite possible you learn something new and interesting, which may have surprising applications elsewhere.