演習 2-9

無職の間にK&Rを再読。演習問題の解答をさらす。解く順番は適当。

演習 2-9
２の補数システムでは、x = x & (x - 1) により、x の最も右の１ビットが消える。なぜか説明せよ。この事実を使って、もっと速い bitcount プログラムを書け。

Exercise 2-9
In a two's complement number system, x &= (x - 1) deletes the rightmost 1-bit in x. Explain why. Use this observation to write a faster version of bitcount.

「説明せよ」と言われても困るが、1 を引くと最も右の１ビットが繰り下げられる。そうすると最も右の１ビットと１つ下位のビットだけが反転する。それを＆演算すると、反転した２ビットだけが 0 になる。つまり、最も右の１ビットが消える。

説明がしづらいけど、例示すれば分かりやすい。

  0101 1100
- 0000 0001
= 0101 1010

この場合、最も右の 2 ビット目とその隣の 1 ビットが反転している。

  0101 1100
& 0101 1010
= 0101 1000

それを元の x と＆演算すると 2 ビット目が消えてなくなる。

最初の bitcount は最も左のビットが出てくるまで繰り返すので、例えば 32ビットの最上位だけが 1 だった場合でも繰り返し回数は３２回となる。一方、速いほうの bitcount では、 1 になっているビットの数だけ繰り返すので、上記の場合は繰り返しは１回ですむ。

しかし、美しいなぁ。
最初問題文見ただけでは意味が分からなかったけど、実際に試してみて「すげーっ！」てなった。
独力でこういう発想ができるようになりたい。

#include <stdio.h>

/* Answer */
int bitcount(unsigned x)
{
  int ret;
  
  for (ret = 0; x != 0; ret++)
    x = x & (x - 1);
  
  return ret;
}



void showbits(long num, int size);
void _showbits(long num, int remain);


int main(void)
{
  unsigned x = 0xABCD1234;

  showbits(x, sizeof(x));
  
  printf("%d\n", bitcount(x));
  
  return 0;
}



void showbits(long num, int size)
{
  _showbits(num, size * 2 - 1);
  putchar('\n');
}


void _showbits(long num, int remain)
{
  static const char bitpattern[16][5] = {
    "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111",
    "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111",
  };
 
  if (remain > 0) {
    _showbits(num >> 4, remain - 1);
    putchar(',');
  }
  
  printf("%s", bitpattern[ num & 0x0F ]);
}