4 ms·

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.
- the-alchemist 2y ago
  agreed! great blog
TinkersW 2y ago
Tricks that work on floating point are sometimes useful and not listed there.. Make float sortable as integer. (the reason you might wish to do this is that integer comparisons are faster and run on more ports, also you won't get unsortable data from NAN). You can undo the transform by calling this fxn again. You only need this with a mix of positive/negative floats, if they are all positive you can skip this. int i = cast_int(f); shift_right_sign_bits(i, 31) & 0x7FFFFFFF) ^ i Scale float by powers of 2 Cast a float to integer and add 0x00800000 * N(N being the power of 2). Subtract to divide. Fails with 0 value float. Not super useful unless you already have the float in the integer domain for some other reason, also integer adds/subs run on more ports and are 1 cycle. The fast sqrt function is well known but you can do this for other powers of 2 //An approximate pow(a, 1/4) float fastPow_1_4(float a) { return asfloat((asuint(a) >> 2u) + 798700996u); } //An approximate pow(a, 1/8) float fastPow_1_8(float a) { return asfloat((asuint(a) >> 3u) + 931853847u); } //An approximate pow(a, 1/16) float fastPow_1_16(float a) { return asfloat((asuint(a) >> 4u) + 998350438u); } //An approximate pow(a, 1/32) float fastPow_1_32(float a) { return asfloat((asuint(a) >> 5u) + 1031705320u); } They are very low accuracy as they don't have a newton raphson step, and were just intended for stuff like graphics where accuracy isn't always important.
kittoes 2y ago
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<T>(this int value) where T : IBinaryInteger<T> { var x = T.AllBitsSet; var y = T.IsNegative(value: x).As<int>(); return ((((x >>> y) / value.NthFermatNumber<T>()) << y) | T.One); } static T NthFermatNumber<T>(this int value) where T : IBinaryInteger<T> { return ((T.One << (1 << value)) + T.One); } NthFermatNumber generates the nth Fermat number (see https://oeis.org/A000215 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: public static TResult BitwisePair<TInput, TResult>(this TInput value, TInput other) where TInput : IBinaryInteger<TInput> where TResult : IBinaryInteger<TResult> { switch (value) { case short: case ushort: if (Bmi2.IsSupported) { return ( TResult.CreateTruncating(value: Bmi2.ParallelBitDeposit(mask: 0.NthFermatMask<uint>(), value: uint.CreateTruncating(value: value))) | TResult.CreateTruncating(value: Bmi2.ParallelBitDeposit(mask: (0.NthFermatMask<uint>() << 1), value: uint.CreateTruncating(value: other))) ); } break; case int: case uint: if (Bmi2.X64.IsSupported) { return ( TResult.CreateTruncating(value: Bmi2.X64.ParallelBitDeposit(mask: 0.NthFermatMask<ulong>(), value: ulong.CreateTruncating(value: value))) | TResult.CreateTruncating(value: Bmi2.X64.ParallelBitDeposit(mask: (0.NthFermatMask<ulong>() << 1), value: ulong.CreateTruncating(value: other))) ); } break; default: break; } const int loopOffset = 7; int offset; int shift; var bitCountDividedByTwo = (int.CreateChecked(value: BinaryIntegerConstants<TResult>.Size) >> 1); var evenBits = TResult.CreateTruncating(value: other); var oddBits = TResult.CreateTruncating(value: value); if (loopOffset.NthPowerOfTwo<int>() < bitCountDividedByTwo) { var i = ((int.CreateChecked(value: BinaryIntegerConstants<TResult>.Log2Size) - loopOffset) - 1); do { offset = (i + (loopOffset - 1)); shift = offset.NthPowerOfTwo<int>(); DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); } while (0 < --i); } offset = 6; if ((shift = offset.NthPowerOfTwo<int>()) < bitCountDividedByTwo) { DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); } offset = 5; if ((shift = offset.NthPowerOfTwo<int>()) < bitCountDividedByTwo) { DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); } offset = 4; if ((shift = offset.NthPowerOfTwo<int>()) < bitCountDividedByTwo) { DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); } offset = 3; if ((shift = offset.NthPowerOfTwo<int>()) < bitCountDividedByTwo) { DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); } offset = 2; if ((shift = offset.NthPowerOfTwo<int>()) < bitCountDividedByTwo) { DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); } offset = 1; if ((shift = offset.NthPowerOfTwo<int>()) < bitCountDividedByTwo) { DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); } offset = 0; if ((shift = offset.NthPowerOfTwo<int>()) < bitCountDividedByTwo) { DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); } return (oddBits | (evenBits << shift)); [MethodImpl(MethodImplOptions.AggressiveInlining)] static void DistributeBits(int offset, int shift, ref TResult evenBits, ref TResult oddBits) { var mask = offset.NthFermatMask<TResult>(); evenBits = ((evenBits | (evenBits << shift)) & mask); oddBits = ((oddBits | (oddBits << shift)) & mask); } }
corysama 2y ago
I don’t have the code handy, but I know it’s pretty easy to Google up the bit hack to convert an integer to a position in a Morton order curve. The new thing I found long ago is that once you have done that, it’s pretty easy to figure out how to incrementally advance along the curve in much fewer instructions than the initial int—>Morton conversion.

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.

the-alchemist 2y ago
agreed! great blog

TinkersW 2y ago

Tricks that work on floating point are sometimes useful and not listed there.. Make float sortable as integer. (the reason you might wish to do this is that integer comparisons are faster and run on more ports, also you won't get unsortable data from NAN). You can undo the transform by calling this fxn again. You only need this with a mix of positive/negative floats, if they are all positive you can skip this. int i = cast_int(f); shift_right_sign_bits(i, 31) & 0x7FFFFFFF) ^ i Scale float by powers of 2 Cast a float to integer and add 0x00800000 * N(N being the power of 2). Subtract to divide. Fails with 0 value float. Not super useful unless you already have the float in the integer domain for some other reason, also integer adds/subs run on more ports and are 1 cycle. The fast sqrt function is well known but you can do this for other powers of 2 //An approximate pow(a, 1/4) float fastPow_1_4(float a) { return asfloat((asuint(a) >> 2u) + 798700996u); } //An approximate pow(a, 1/8) float fastPow_1_8(float a) { return asfloat((asuint(a) >> 3u) + 931853847u); } //An approximate pow(a, 1/16) float fastPow_1_16(float a) { return asfloat((asuint(a) >> 4u) + 998350438u); } //An approximate pow(a, 1/32) float fastPow_1_32(float a) { return asfloat((asuint(a) >> 5u) + 1031705320u); } They are very low accuracy as they don't have a newton raphson step, and were just intended for stuff like graphics where accuracy isn't always important.

kittoes 2y ago

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<T>(this int value) where T : IBinaryInteger<T> { var x = T.AllBitsSet; var y = T.IsNegative(value: x).As<int>(); return ((((x >>> y) / value.NthFermatNumber<T>()) << y) | T.One); } static T NthFermatNumber<T>(this int value) where T : IBinaryInteger<T> { return ((T.One << (1 << value)) + T.One); } NthFermatNumber generates the nth Fermat number (see https://oeis.org/A000215 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: public static TResult BitwisePair<TInput, TResult>(this TInput value, TInput other) where TInput : IBinaryInteger<TInput> where TResult : IBinaryInteger<TResult> { switch (value) { case short: case ushort: if (Bmi2.IsSupported) { return ( TResult.CreateTruncating(value: Bmi2.ParallelBitDeposit(mask: 0.NthFermatMask<uint>(), value: uint.CreateTruncating(value: value))) | TResult.CreateTruncating(value: Bmi2.ParallelBitDeposit(mask: (0.NthFermatMask<uint>() << 1), value: uint.CreateTruncating(value: other))) ); } break; case int: case uint: if (Bmi2.X64.IsSupported) { return ( TResult.CreateTruncating(value: Bmi2.X64.ParallelBitDeposit(mask: 0.NthFermatMask<ulong>(), value: ulong.CreateTruncating(value: value))) | TResult.CreateTruncating(value: Bmi2.X64.ParallelBitDeposit(mask: (0.NthFermatMask<ulong>() << 1), value: ulong.CreateTruncating(value: other))) ); } break; default: break; } const int loopOffset = 7; int offset; int shift; var bitCountDividedByTwo = (int.CreateChecked(value: BinaryIntegerConstants<TResult>.Size) >> 1); var evenBits = TResult.CreateTruncating(value: other); var oddBits = TResult.CreateTruncating(value: value); if (loopOffset.NthPowerOfTwo<int>() < bitCountDividedByTwo) { var i = ((int.CreateChecked(value: BinaryIntegerConstants<TResult>.Log2Size) - loopOffset) - 1); do { offset = (i + (loopOffset - 1)); shift = offset.NthPowerOfTwo<int>(); DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); } while (0 < --i); } offset = 6; if ((shift = offset.NthPowerOfTwo<int>()) < bitCountDividedByTwo) { DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); } offset = 5; if ((shift = offset.NthPowerOfTwo<int>()) < bitCountDividedByTwo) { DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); } offset = 4; if ((shift = offset.NthPowerOfTwo<int>()) < bitCountDividedByTwo) { DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); } offset = 3; if ((shift = offset.NthPowerOfTwo<int>()) < bitCountDividedByTwo) { DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); } offset = 2; if ((shift = offset.NthPowerOfTwo<int>()) < bitCountDividedByTwo) { DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); } offset = 1; if ((shift = offset.NthPowerOfTwo<int>()) < bitCountDividedByTwo) { DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); } offset = 0; if ((shift = offset.NthPowerOfTwo<int>()) < bitCountDividedByTwo) { DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); } return (oddBits | (evenBits << shift)); [MethodImpl(MethodImplOptions.AggressiveInlining)] static void DistributeBits(int offset, int shift, ref TResult evenBits, ref TResult oddBits) { var mask = offset.NthFermatMask<TResult>(); evenBits = ((evenBits | (evenBits << shift)) & mask); oddBits = ((oddBits | (oddBits << shift)) & mask); } }

corysama 2y ago

I don’t have the code handy, but I know it’s pretty easy to Google up the bit hack to convert an integer to a position in a Morton order curve. The new thing I found long ago is that once you have done that, it’s pretty easy to figure out how to incrementally advance along the curve in much fewer instructions than the initial int—>Morton conversion.