There's a remarkable number of algorithms from Hacker's Delight already in the Julia base code – notably in the implementation of BitArray, but also elsewhere. We are somewhat constrained by the primitives we can expose by what LLVM includes<http://llvm.org/docs/LangRef.html#bit-manipulation-intrinsics>. It may be able to recognize certain idioms and translate them into x86 instructions, however.
> On Apr 20, 2014, at 6:58 PM, Laszlo Hars <[email protected]> wrote: > > Paul Erdős, the roving ambassador of mathematics thought that God created "The Book" in which the most elegant proof of each mathematical theorem is written. I am sure God aslo has a book for the fastest and for the nicest Julia programs. Finding those programs would be our goal, if we had infinite time... > > The problem with bit wizardry is that some of it is superfluous. For example, many modern CPUs have bit reversal in single machine instructions, because it is often needed, e.g. in FFT computations. Julia does not support them, yet. Rotational shifts are also missing. We can spend days with writing nice code for these just to see them becoming obsolete at a new Julia update. Still, we can go over an implement most of the algorithms from Jörg Arndt's book: Matters Computational ( http://www.jjj.de/fxt/fxtbook.pdf). It has the most complete collection of low-level functions I have seen. It would be quite easy to code them up in Julia. But the question remains: do we want the nicest, the shortest or the fastest code, or the one with a reasonable combination of these features? > > Btw. The variations of bit reversal functions I added to my previous post can still be tweaked further: > ~~~ > function reflect1(n::Uint8) # Two '&' operators and some parentheses removed > n = n >>> 4 | n << 4 > n = n&0xcc >>> 2 | n&0x33 << 2 > n & 0xaa >>> 1 | n & 0x55 << 1 > end > > r4 = uint8([0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15]) > function reflect2(n::Uint8) # 4-bit lookup table (if 8-bit table is too large) > r4[n>>>4+1] | r4[(n&15)+1]<<4 > end > > function reflect3(n::Uint8) # Building up the reverse bit-by-bit > r = zero(Uint8) > for i = 0:7 > r = r<<1 | (n>>>i)&1 > end > r > end > > function reflect4(n::Uint8) # Bits put together, no assignment > n<<7 | (n>>>1)&1<<6 | (n>>>2)&1<<5 | (n>>>3)&1<<4 | > (n>>>4)&1<<3 | (n>>>5)&1<<2 | (n>>>6)&1<<1 | n>>>7 > end > ~~~
