uDiary

◆ bit 番号をこたえる

Bitboard がらみなんですが。

ある特定の bit だけが on であるような整数を、 その、on にしたいビットの番号からつくるのは簡単です。1 を必要なだけ左シフトすればいい。

では、そのような整数の、1-bit だけ on になっているビットのビット位置を知るには どうすればよいか。

「ハッカーのたのしみ」図 5-12 にあるプログラム片をもとに、次のようなコードを 書いてみました。

 /*
  * Before calling bitpos64 or bitpos32, you should check
  * x is not zero.
  */

 inline static int
 bitpos64(unsigned long long x)
 {
   volatile double value;
   volatile unsigned long long *p = (unsigned long long*) &value;

   value = (double) x;
   return (((*p >> 52) + 1) & 0x3F);
 }

 inline static int
 bitpos32(unsigned long x)
 {
   volatile double value;
   volatile unsigned long long *p = (unsigned long long*) &value;

   value = (double) x;
   return (((*p >> 52) + 1) & 0x1F);
 }

びみょーに怪しげですが、sparc, x86_64 いずれにおいても期待どおり動作する模様。 （unsigned long long を用いているぶん、エンディアンの影響を受けないところが、 「ハッカーのたのしみ」にあるオリジナルと異なります。）

大は小を兼ねるのですが、余計なキャストがいやなので、 64-bit 版と 32-bit 版の両方を用意しました。

追記：上記のコードは、「1-bit だけ on になっているビットのビット位置を知る」 ために使えますが、より正確には、on になっているビットのうち、一番 MSB に近いものの ビット位置を知るために使えます。ただし、「ハッカーのたのしみ」の元のコードにあった、 x が 0 だった場合のための対処がないので、0 でないことは呼び出し側で保証する必要が あります。

関連：IEEE 754 (Wikipedia)