Bit Twiddling Hacks

This was posted a number of times before:<p><a href="http://news.ycombinator.com/item?id=2570269" rel="nofollow">http://news.ycombinator.com/item?id=2570269</a><p><a href="http://news.ycombinator.com/item?id=513935" rel="nofollow">http://news.ycombinator.com/item?id=513935</a><p><a href="http://news.ycombinator.com/item?id=86419" rel="nofollow">http://news.ycombinator.com/item?id=86419</a><p>And also:<p><a href="http://news.ycombinator.com/item?id=1811104" rel="nofollow">http://news.ycombinator.com/item?id=1811104</a>

These are cool, but how much is automatically done for you by the compiler? For example, if I changed all of my calls to min(x,y) with<p>r = y + ((x - y) &#38; ((x - y) &#62;&#62; (sizeof(int) * CHAR_BIT - 1))); // min(x, y)<p>my code would quickly become unreadable. I could define a macro, but those are supposedly evil[1].<p>[1] <a href="http://www.parashift.com/c++-faq-lite/inline-functions.html#faq-9.5" rel="nofollow">http://www.parashift.com/c++-faq-lite/inline-functions.html#...</a>

If you enjoyed this, you'll also probably like Hacker's Delight: <a href="http://www.hackersdelight.org/" rel="nofollow">http://www.hackersdelight.org/</a>

I like Morton Numbers--they're a great example of the notion that dimensionality is an interpretation, and you can compress higher dimensions down to 1 while still retaining a 1-to-1 correspondence. However, good luck with modifying the bit twiddling algorithms shown here when you want to deal with Big Numbers that overflow C/C++'s built-in types. Here's a slow (I haven't measured how slow) Python version that's insensitive to how big the number is:<p><pre><code> def tomorton(x,y): x = bin(x)[2:] lx = len(x) y = bin(y)[2:] ly = len(y) L = max(lx, ly) m = 0 for j in xrange(1, L+1): # note: ith bit of x requires x[lx - i] since our bin numbers are big endian xi = int(x[lx-j]) if j-1 &#60; lx else 0 yi = int(y[ly-j]) if j-1 &#60; ly else 0 m += 2**(2*j)*xi + 2**(2*j+1)*yi return m/4</code></pre>

Premature optimization heaven!!<p>But seriously, I'm going to crawl through this and see if there is anything that can speed up some drawing code I have. Very nice!

These are pretty neat. I use a few of them relatively often at work, but if I ever saw<p>c = ((((c - 0x3f800000) &#62;&#62; r) + 0x3f800000) &#62;&#62; 23) - 127;<p>in production code I would be sad.

Search for Ratko Tomic bits on google. He was doing these optimizations in the late 80s and early 90s.<p>How I miss the RIME/RelayNet C language forums...