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) & ((x - y) >> (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 < lx else 0
yi = int(y[ly-j]) if j-1 < 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) >> r) + 0x3f800000) >> 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...