Live data from Hacker News

Bit Twiddling Hacks (2009)

graphics.stanford.edu

11–20 of 28 posts

Re: Bit Twiddling Hacks (2009)

#11

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

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.

Re: Bit Twiddling Hacks (2009)

#14

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.

Re: Bit Twiddling Hacks (2009)

#15
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.

Re: Bit Twiddling Hacks (2009)

#17

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

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.

Re: Bit Twiddling Hacks (2009)

#18

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 : IBinaryInteger {
        return ((T.One 
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:

    public static TResult BitwisePair(this TInput value, TInput other) where TInput : IBinaryInteger where TResult : IBinaryInteger {
        switch (value) {
            case short:
            case ushort:
                if (Bmi2.IsSupported) {
                    return (
                        TResult.CreateTruncating(value: Bmi2.ParallelBitDeposit(mask: 0.NthFermatMask(), value: uint.CreateTruncating(value: value))) |
                        TResult.CreateTruncating(value: Bmi2.ParallelBitDeposit(mask: (0.NthFermatMask() (), value: ulong.CreateTruncating(value: value))) |
                        TResult.CreateTruncating(value: Bmi2.X64.ParallelBitDeposit(mask: (0.NthFermatMask() .Size) >> 1);
        var evenBits = TResult.CreateTruncating(value: other);
        var oddBits = TResult.CreateTruncating(value: value);

        if (loopOffset.NthPowerOfTwo() .Log2Size) - loopOffset) - 1);

            do {
                offset = (i + (loopOffset - 1));
                shift = offset.NthPowerOfTwo();

                DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift);
            } while (0 ()) ()) ()) ()) ()) ()) ()) ();

            evenBits = ((evenBits | (evenBits 

Re: Bit Twiddling Hacks (2009)

#19
post #11

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

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.

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
    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;
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?

Re: Bit Twiddling Hacks (2009)

#20

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

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.

Post reply on HN