Bit Twiddling Hacks (2009)

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.

   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.

   Scale float by powers of 2

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/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.

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.

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.

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.

shr ecx, 1 lea eax, [rcx + 1FC00000h] shr eax, 1 add eax, ecx

    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);
    }

    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);
        }
    }

You should of course always check your compiler output when doing stuff like this, but doubly so in those cases.