Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Bit Twiddling Hacks (2009)

graphics.stanford.edu

Post reply on HN
Print view View original

21–28 of 28 posts

Re: Bit Twiddling Hacks (2009)

#21

Post by exDM69 »

zokier wrote: post #8

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_instructi... https://thephd.dev/_vendor/future_cxx/papers/C%20-%20Modern%...

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.

Re: Bit Twiddling Hacks (2009)

#22

Post by the-alchemist »

lifefeed wrote: post #14
threatofrain wrote: post #3

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

Daniel Lemire's entire 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.

agreed! great blog

Re: Bit Twiddling Hacks (2009)

#23

Post by dahart »

white_beach wrote: post #6
threatofrain wrote: post #3

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

here's one or two shr ecx, 1 lea eax, [rcx + 1FC00000h] shr eax, 1 add eax, ecx

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

Re: Bit Twiddling Hacks (2009)

#24

Post by mjevans »

kittoes wrote: post #18
threatofrain wrote: post #3

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

Not sure if this counts, but I got tired of seeing all of the magic constants used in several of these tricks and not understanding how they were generated. Came up with the following via trial and error: static T NthFermatMask (this int value) where T : IBinaryInteger { var x = T.AllBitsSet; var y = T.IsNegative(value: x).As (); return ((((x >>> y) / value.NthFermatNumber ()) (this int value) where T : IBinaryIntege…

That's why the example also had the bit-encoding laid out.

The magic constants start off with an every other order, then combine that comb size until you're left with front and back.

    5 0101 1010 A
    3 0011 1100 C
    F 1111 0000 0

Re: Bit Twiddling Hacks (2009)

#25

Post by kittoes »

mjevans wrote: post #24
kittoes wrote: post #18

Earlier quoted context omitted.

Not sure if this counts, but I got tired of seeing all of the magic constants used in several of these tricks and not understanding how they were generated. Came up with the following via trial and error: static T NthFermatMask (this int value) where T : IBinaryInteger { var x = T.AllBitsSet; var y = T.IsNegative(value: x).As (); return ((((x >>> y) / value.NthFermatNumber ()) (this int value) where T : IBinaryIntege…

That's why the example also had the bit-encoding laid out. The magic constants start off with an every other order, then combine that comb size until you're left with front and back. 5 0101 1010 A 3 0011 1100 C F 1111 0000 0

[dead]

Re: Bit Twiddling Hacks (2009)

#28

Post by overanalytcl »

zokier wrote: post #8

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_instructi... https://thephd.dev/_vendor/future_cxx/papers/C%20-%20Modern%...

The last link doesn't work.
Post reply on HN