Hacker's Delight ハッカーの楽しみ

この本は計算機のリソース（メモリ、時間など）の利用を最大限に最適化するための、ハッキングに使い凄技が満載です。特に感心させられるのは、単純なシフトや論理演算（論理和、論理積、排他的論理和、否定）と加・減算だけて、高度な計算を実現してしまうことです。以下は、そのいくつかの例です。

一番右側のビットに関する演算

一番右の1であるビットをオフ（0）にしたい。ない時には結果が0になる。応用編としては、結果が0である場合、ｘは2の冪乗であること。
x&(x-1)
符号なしの数値が2^n-1(0とオール１を含む）であるかどうかを確認したい
   x&(x+1)
一番右の１であるビットを取り出したい。なければ結果は０である。(例：01011000=>00001000)。
x &(-x)
一番右の0であるビットを取り出した。なければ結果は０である。(例：10100111>00001000)。
  ~x & (x+1)
後置ゼロ（Trailing Zero)のマスクを作りたい。０の場合オール1になる。(例：01011000=>00000111)。
  ~x & (x-1)
  ~(x | -x)
 (x&-x)-1
一番右側の1であるビットと後置ゼロのマスクを作りたい。0の場合はオール1になる。(例：01011000=>00001111)
  x^(x-1)
一番右側にある1を右一杯に伝播させたい。0の場合ロール１になる。（例：01011000=>01011111)。
  x | (x-1)
一番右側の連続1ビットをオフ（0）にしたい。（例：01011000=>01000000)。これの応用は負ではない数値は2^j-2^k(j>=k>=0; ^は冪乗）の形であるかどうかを確認することです。結果は
0であれば、真です。
  ((x|(x-1))+1)&x
上記の計算式は「対」でもある。つまり、1を０で置き換えれば、また、x-1をx+1、x+1をx-1、-xを~(x+1),&を|、|を&0で置き換えて、xと~xをそのままにすれば、に対する記述・判別しきになる。
例えば、以下の式は一番右側の0をオン(1)にすることができる。（例：10100111=>10101111)。
  x | (x+1)

左ローテートシフト。Xは符号なしである。
  (x<<n)|(x>>(32-n)
右ローテートシフト。。Xは符号なしである。
  (<>>n)|(x<<(32-n)

変数（ｘ）に２つの値（aとb）を交代に代入したい
ｘ <- a + b - x
   x <- a^b^x
これは、以下のコードより効率的である
if (x == a) x = b;
  else x = a;
ある2の冪乗に繰り上げ、繰り下げたい。例えば、２のK乗の場合。
繰り上げ：x&((-1)<<k)
あるいは、(x>>k)<<k ここで、>>は論理右シフトです（０で埋める）　　　　
繰り下げ：t<-(1<<k)-1; (x+t)&~t
あるいは、t<-(-1)<<k; (x-t-1)&t
次の2の冪乗に繰り上げたい
x = x|(x>>1);
x = x|(x>>2);
x = x|(x>>4);
x = x|(x>>8);
x = x|(x>>16);
  x <- (x-(x>>1))
次の2の冪乗に繰り下げたい
  x = x-1;
x = x|(x>>1);
x = x|(x>>2);
x = x|(x>>4);
x = x|(x>>8);
x = x|(x>>16);
  x <- (x+1)
1の数を数えたい
 x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
 x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
 x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
 x = (x & 0x0000FFFF) + ((x >>16) & 0x0000FFFF);
パリティを計算したい
   x = x ^ (x >> 1);
   x = (x ^ (x >> 2)) & 0x11111111;
   x = x*0x11111111;
   p = (x >> 28) & 1;
先行ゼロ（Leading Zero）の数を数えたい。NLZ(Number of Leading Zero)
   x = x - ((x >> 1) & 0x55555555);
   x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
   x = (x + (x >> 4)) & 0x0F0F0F0F;
   x = x + (x << 8);
   x = x + (x << 16);
n <- (x>>24)
NLZをつかて、２を底とするlogを計算できる
31-nlz(x)<log2(x)<32-nlz(x-1)
後置ゼロを数えたい
32-nlz(~x&(x-1))

Hacker's Delight is book by Henry S. Warren, Jr.. There is a dedicated website for this book. It has the link to the sample source codes in the book. This book is for C programmers, providing many "superoptimizer" tricks. According to the above site:

A superoptimizer is a program that makes a serious attempt at finding optimal code, in the sense of a minimal number of instructions, for a given function. It works by trying all sequences of computational instructions of a given length, simulating each sequence for various inputs, until it finds (stumbles on) a sequence that matches a given user-defined function.

The site above also contains a link to "Pokerlistings Odds Calculator", which is a fun site for gamblers.