Just for reference:
In Data/IntMap/Base.hs
highestBitMask :: Nat -> Nat
highestBitMask x0
= case (x0 .|. shiftRL x0 1) of
x1 -> case (x1 .|. shiftRL x1 2) of
x2 -> case (x2 .|. shiftRL x2 4) of
x3 -> case (x3 .|. shiftRL x3 8) of
x4 -> case (x4 .|. shiftRL x4 16) of
#if !(defined(__GLASGOW_HASKELL__) && WORD_SIZE_IN_BITS==32)
x5 -> case (x5 .|. shiftRL x5 32) of -- for 64 bit platforms
#endif
x6 -> (x6 `xor` (shiftRL x6 1))
In FXT bithigh.h:
static inline ulong highest_one(ulong x)
// Return word where only the highest bit in x is set.
// Return 0 if no bit is set.
{
#if defined BITS_USE_ASM
if ( 0==x ) return 0;
x = asm_bsr(x);
return 1UL<<x;
#else
x = highest_one_01edge(x);
return x ^ (x>>1);
#endif // BITS_USE_ASM
}
And in FXT bits/bithigh-edge.h:
static inline ulong highest_one_01edge(ulong x)
// Return word where all bits from (including) the
// highest set bit to bit 0 are set.
// Return 0 if no bit is set.
//
// Feed the result into bit_count() to get
// the index of the highest bit set.
{
#if defined BITS_USE_ASM
if ( 0==x ) return 0;
x = asm_bsr(x);
return (2UL<<x) - 1;
#else // BITS_USE_ASM
x |= x>>1;
x |= x>>2;
x |= x>>4;
x |= x>>8;
x |= x>>16;
#if BITS_PER_LONG >= 64
x |= x>>32;
#endif
return x;
#endif // BITS_USE_ASM
}
=====
However... I think the easy solution for this is to just find this in http://graphics.stanford.edu/~seander/bithacks.html, and cite it instead. I looked briefly and couldn't find it, but I'm almost sure it's in there.
- Clark