add bitreverse function

[JeffBezanson]

This can be useful for parsing binary formats, and generally helps round out the set of bit-level operations.

[Keno]

why the mix of arithmetic and logic shifts?

[StefanKarpinski]

There is no <<<?

[jakobnissen]

Sorry to jump in, but why not use bswap for some of these operations? It's shorter, easier to understand, less reliant on magic numbers, and presumably compiles to efficient LLVM.

[jakobnissen]

In fact, one could use a single method for all ints, like this:

function bitreverse1(x::Base.BitInteger)
    z = unsigned(x)
    mask1 = 0x55555555555555555555555555555555 % typeof(z)
    mask2 = 0x33333333333333333333333333333333 % typeof(z)
    mask4 = 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f % typeof(z)
    z = ((z & mask1) << 1) | ((z >> 1) & mask1)
    z = ((z & mask2) << 2) | ((z >> 2) & mask2)
    z = ((z & mask4) << 4) | ((z >> 4) & mask4)
    return bswap(z) % typeof(x)
end

On my machine, this generates more efficient code, too, but I don't know if it uses too much "compile time magic".

[KristofferC]

In fact, LLVM already has a bitreverse intrinsic: https://llvm.org/docs/LangRef.html#llvm-bitreverse-intrinsics. But it will probably compile to the same thing.

[StefanKarpinski]

But with the intrinsic, it's (more) not our problem to make sure it's fast on all the architectures.

[JeffBezanson]

I'll use this implementation, since adding intrinsics is harder and I'd rather avoid llvmcall.