ビットの逆転

ビットを逆順にする。
1011 => 1101

ふつう思いつくのはこんな感じ？

unsigned long BitReversal(unsigned long src, char bit/*=32*/)
{
  unsigned long reversed = 0;
  for(int i=1; i<(bit+1); ++i) {
    if(src & 1)
      reversed |= (1 << (bit-i));
    src >>= 1;
  }
  return reversed;
}

元の値の最下位ビットが1なら、先頭から数えた現在位置に1立てる。
元の値を1ビットシフト。

ビット逆順の妙義
ループを使わないし、分岐もない。
元ネタは「ハッカーのたのしみ」という本(Hacker's Delight）

unsigned rev(unsigned x){
  x = (x & 0x55555555) << 1 | (x >> 1) & 0x55555555;
  x = (x & 0x33333333) << 2 | (x >> 2) & 0x33333333;
  x = (x & 0x0F0F0F0F) << 4 | (x >> 4) & 0x0F0F0F0F;
  x = (x << 24) | ((x & 0xFF00) << 8) |
    ((x >> 8) & 0xFF00) | (x >> 24);
  return x;
}

なんだこれ。


その他、逆転の妙義

Bit Twiddling Hacks
http://graphics.stanford.edu/~seander/bithacks.html

どうすれば、こんなことを思いつけるようになるのか。