Re:Bit Twiddling Hacks
by kittoes on Friday August 23, 2024 @10:23AM
(#41329280)
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:
NthFermatNumber generates the nth Fermat number (see https://oeis.org/A000215) and NthFermatMask generates magic constants of the form 0x55555555, 0x33333333, 0x0F0F0F0F, etc. To demonstrate usage, here is a generic interleave bits implementation:
[ Parent
| on HN ]
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