4 ms·

Bit Twiddling Hacks (2009)

92 points by elpocko 2y ago

hi-v-rocknroll 2y ago
It's nice that it expresses algorithms in C. It's more concrete than most of Hacker's Delight, which is similar and more comprehensive, but often vaguer and occassionally covers tricks used on historical architectures and systems.[0] 0. Hacker's Delight (Second Edition) by Henry S. Warren, 2013, ISBN: 0321842685
- unwind 2y ago
  It is nice, and it's also nice that it contains notes on how right-shifting a signed integer is implementation-defined in C (it's not the much-feared undefined behavior) so inherently non-portable. You should of course always check your compiler output when doing stuff like this, but doubly so in those cases.
  - dahart 2y ago
    Unfortunately it doesn’t mention how left-shifting a negative signed integer is undefined behavior. There are a few cases where constants were changed to fix this, e.g. using (1U<<n) instead of (1<<n), but strangely that change didn’t get propagated everywhere and it appears there are still a couple cases in the code that might be UB. Specifically, the variation of variable-width sign-extend in 3 operations looks crazy. Aren’t there multiple UBs in this one? unsigned b; // number of bits representing the number in x int x; // sign extend this b-bit number to r int r; // resulting sign-extended number // The following variation is not portable, but on architectures that employ an arithmetic right-shift, maintaining the sign, it should be fast. const int s = -b; // OR: sizeof(x) * CHAR_BIT - b; r = (x << s) >> s; Not sure if I’m missing something, but it looks like this relies on shift by a negative number (UB), potential left shift of a 1 bit into the sign bit (UB), and potential right shift of a negative number (implementation defined). Isn’t this much worse than non-portable, but guaranteed to be undefined?
threatofrain 2y ago
This thing is posted so often on HN. Does anyone have any new cool tricks that aren't in the normal compendium of tricks?
- jandrewrogers 2y ago
  There are additional tricks that are more specialized or generalizations of the ideas here beyond their presented scope, like SWAR (SIMD Within A Register) over arbitrary packed bitfields. I realize this is not that helpful but most of the tricks not listed here won’t be interesting to most people. Many of the bit twiddling tricks that are widely known are also known to compilers, which can generate them automatically. Hell, x86 has single instructions that implement many of the well-known tricks directly. Where these tricks become handy again is SIMD vectorization. The compiler is much less clever in these situations and the scalar bit-twiddling instructions often don’t have vectorized equivalents.
- white_beach 2y ago
  here's one or two shr ecx, 1 lea eax, [rcx + 1FC00000h] shr eax, 1 add eax, ecx
  - dahart 2y ago
    This reminded me of the puzzle book “xchg rax,rax”. Maybe that has some hidden insights… :P https://www.xorpd.net/pages/xchg_rax/snip_00.html https://www.xorpd.net/pages/xchg_rax/snip_00.html
- icelusxl 2y ago
  Maybe http://0x80.pl http://0x80.pl -- this site features mainly SIMD/SWAR code.
- lifefeed 2y ago
  Daniel Lemire's entire blog: https://lemire.me/blog/ https://lemire.me/blog/ . It focuses on low level optimizations, often by using SIMD, avoiding division, and being generally clever. It's nothing I use in my job, but I enjoy reading every post.
AeZ1E 2y ago
with this bitwise magic, my code will find the sign faster than you can say "boolean operation!" who needs branching when you've got clever tricks up your sleeve? hate to say it, but this beats the obvious way, hands down!
- abc123def456 2y ago
  would modern compilers not convert the simple boolean operations into clever bit twiddling hacks for you?
zokier 2y ago
It's worth noting that modern x86 CPUs have specialized extensions for bit manipulation. Furthermore C23 added stdbit.h that has some operations for bit manipulation https://en.wikipedia.org/wiki/X86_Bit_manipulation_instruction_set https://en.wikipedia.org/wiki/X86_Bit_manipulation_instructi... https://thephd.dev/_vendor/future_cxx/papers/C%20-%20Modern%20Bit%20Utilities.html https://thephd.dev/_vendor/future_cxx/papers/C%20-%20Modern%...
- exDM69 2y ago
  Absolutely, look into your standard library, CPU built-ins and intrinsics first. However, these tricks are not useless even on modern CPUs. There are scalar instructions for a lot of this stuff, but if you are working with SIMD, several of them are not available. Recently I wrote bit interleaving stuff with Morton codes. Maybe the scalar instruction would be faster in isolation but I already have my data in SSE registers for other arithmetic so in total it was probably faster. I used the code in this article as a basis.
- overanalytcl 2y ago
  The last link doesn't work.
jcmeyrignac 2y ago
Some related links: http://aggregate.org/MAGIC/ http://aggregate.org/MAGIC/ https://web.archive.org/web/20190703172150/http://www.hackersdelight.org/ https://web.archive.org/web/20190703172150/http://www.hacker...
froh 2y ago
in the same spirit and an alive project: https://jjj.de/fxt/fxtpage.html https://jjj.de/fxt/fxtpage.html
lloydatkinson 2y ago
I’m surprised the yearly advent of code never requires any bit twiddling.
- vismit2000 2y ago
  https://adventofcode.com/2020/day/14 https://adventofcode.com/2020/day/14
billpg 2y ago
Decades ago, I discovered a compiler for an obscure microprocessor was generating a subtraction operation to test if two integers are equal. I then turned the optimisations on and it generated an XOR instruction instead. I suspect a lot of these hacks are used by an optimising compiler.
deleted 2y ago
[deleted]
thealistra 2y ago
Oh is it this time of the year already?

92 points by elpocko 2y ago

It's nice that it expresses algorithms in C. It's more concrete than most of Hacker's Delight, which is similar and more comprehensive, but often vaguer and occassionally covers tricks used on historical architectures and systems.[0] 0. Hacker's Delight (Second Edition) by Henry S. Warren, 2013, ISBN: 0321842685

unwind 2y ago
It is nice, and it's also nice that it contains notes on how right-shifting a signed integer is implementation-defined in C (it's not the much-feared undefined behavior) so inherently non-portable. You should of course always check your compiler output when doing stuff like this, but doubly so in those cases.
- dahart 2y ago
  Unfortunately it doesn’t mention how left-shifting a negative signed integer is undefined behavior. There are a few cases where constants were changed to fix this, e.g. using (1U<<n) instead of (1<<n), but strangely that change didn’t get propagated everywhere and it appears there are still a couple cases in the code that might be UB. Specifically, the variation of variable-width sign-extend in 3 operations looks crazy. Aren’t there multiple UBs in this one? unsigned b; // number of bits representing the number in x int x; // sign extend this b-bit number to r int r; // resulting sign-extended number // The following variation is not portable, but on architectures that employ an arithmetic right-shift, maintaining the sign, it should be fast. const int s = -b; // OR: sizeof(x) * CHAR_BIT - b; r = (x << s) >> s; Not sure if I’m missing something, but it looks like this relies on shift by a negative number (UB), potential left shift of a 1 bit into the sign bit (UB), and potential right shift of a negative number (implementation defined). Isn’t this much worse than non-portable, but guaranteed to be undefined?

threatofrain 2y ago

This thing is posted so often on HN. Does anyone have any new cool tricks that aren't in the normal compendium of tricks?

jandrewrogers 2y ago
There are additional tricks that are more specialized or generalizations of the ideas here beyond their presented scope, like SWAR (SIMD Within A Register) over arbitrary packed bitfields. I realize this is not that helpful but most of the tricks not listed here won’t be interesting to most people. Many of the bit twiddling tricks that are widely known are also known to compilers, which can generate them automatically. Hell, x86 has single instructions that implement many of the well-known tricks directly. Where these tricks become handy again is SIMD vectorization. The compiler is much less clever in these situations and the scalar bit-twiddling instructions often don’t have vectorized equivalents.
white_beach 2y ago
here's one or two shr ecx, 1 lea eax, [rcx + 1FC00000h] shr eax, 1 add eax, ecx
- dahart 2y ago
  This reminded me of the puzzle book “xchg rax,rax”. Maybe that has some hidden insights… :P https://www.xorpd.net/pages/xchg_rax/snip_00.html https://www.xorpd.net/pages/xchg_rax/snip_00.html
icelusxl 2y ago
Maybe http://0x80.pl http://0x80.pl -- this site features mainly SIMD/SWAR code.
lifefeed 2y ago
Daniel Lemire's entire blog: https://lemire.me/blog/ https://lemire.me/blog/ . It focuses on low level optimizations, often by using SIMD, avoiding division, and being generally clever. It's nothing I use in my job, but I enjoy reading every post.

AeZ1E 2y ago

with this bitwise magic, my code will find the sign faster than you can say "boolean operation!" who needs branching when you've got clever tricks up your sleeve? hate to say it, but this beats the obvious way, hands down!

abc123def456 2y ago
would modern compilers not convert the simple boolean operations into clever bit twiddling hacks for you?

zokier 2y ago

It's worth noting that modern x86 CPUs have specialized extensions for bit manipulation. Furthermore C23 added stdbit.h that has some operations for bit manipulation https://en.wikipedia.org/wiki/X86_Bit_manipulation_instruction_set https://en.wikipedia.org/wiki/X86_Bit_manipulation_instructi... https://thephd.dev/_vendor/future_cxx/papers/C%20-%20Modern%20Bit%20Utilities.html https://thephd.dev/_vendor/future_cxx/papers/C%20-%20Modern%...

exDM69 2y ago
Absolutely, look into your standard library, CPU built-ins and intrinsics first. However, these tricks are not useless even on modern CPUs. There are scalar instructions for a lot of this stuff, but if you are working with SIMD, several of them are not available. Recently I wrote bit interleaving stuff with Morton codes. Maybe the scalar instruction would be faster in isolation but I already have my data in SSE registers for other arithmetic so in total it was probably faster. I used the code in this article as a basis.
overanalytcl 2y ago
The last link doesn't work.

jcmeyrignac 2y ago

Some related links: http://aggregate.org/MAGIC/ http://aggregate.org/MAGIC/ https://web.archive.org/web/20190703172150/http://www.hackersdelight.org/ https://web.archive.org/web/20190703172150/http://www.hacker...

froh 2y ago

in the same spirit and an alive project: https://jjj.de/fxt/fxtpage.html https://jjj.de/fxt/fxtpage.html

lloydatkinson 2y ago

I’m surprised the yearly advent of code never requires any bit twiddling.

vismit2000 2y ago
https://adventofcode.com/2020/day/14 https://adventofcode.com/2020/day/14

billpg 2y ago

Decades ago, I discovered a compiler for an obscure microprocessor was generating a subtraction operation to test if two integers are equal. I then turned the optimisations on and it generated an XOR instruction instead. I suspect a lot of these hacks are used by an optimising compiler.

deleted 2y ago

[deleted]

thealistra 2y ago

Oh is it this time of the year already?