【C言語】ビットを数える（32bit）

古典的ながら立っているビットを数えるプログラム書けますか？
今時のライブラリには実装されていると思いますが、考えて書いてみるのも楽しいですよ。

ここで扱う int は 32bit とします。

●普通に思いつく方法

int count_bits(int n)
{
  int i;
  int sum = 0;
  for (i = sizeof(int) * 8 - 1; i >= 0; i--)
  {
      sum += (n >> i) & 1;
  }
  return sum;
}

回してシフトの繰り返しで数える方法ですね。誰もが最初に書くパターンかと思います。可読性◎

●の〜みそコネコネしたらできた方法

int count_bits(int n)
{
  int sum;
  for (sum = 0; n != 0; n &= n - 1)
  {
    sum++;
  }
  return sum;
}

ビット演算に慣れてきた頃に、この方がプログラムしてる感でてね？って思って書くようなパターンですね。

●テーブルを持っておく方法

int count_bits(int n)
{
  int table[256]={
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
  };
  int sum = 0;
  int i;
  for (i = 0; i < sizeof(int); i++)
  {
    sum += table[(n >> 8 * i) & 0xff];
  }
  return sum;
}

sin, cosでテーブル持ったら速かったという知見を得て、これもテーブルで持ってみようかなってパターンでしょうか。

●ループを使わない方法

int count_bits(int n)
{
  int sum;
  sum = (n >> 1) & 03333333333;
  sum = n - sum - ((sum >> 1) & 03333333333);
  sum = ((sum + (sum >> 3)) & 0707070707) % 077;
  return sum;
}

ここからは変態の域です。可読性を無視して、とにかくループをなくしたい一心でやり遂げちゃったパターンです。ちゃんと考えられてますよ。

●最高峰（1960年代）

int count_bits(int n)
{
  n = (n & 0x55555555) + (n >> 1 & 0x55555555);
  n = (n & 0x33333333) + (n >> 2 & 0x33333333);
  n = (n & 0x0f0f0f0f) + (n >> 4 & 0x0f0f0f0f);
  n = (n & 0x00ff00ff) + (n >> 8 & 0x00ff00ff);
  n = (n & 0x0000ffff) + (n >> 16 & 0x0000ffff);
  return n;
}

何を考えて書いてたのでしょう。頭の中の思考回路を見てみたいものです。ひらめきか努力のどっちかでしょうね。最速ですが可読性って？

●若き頃の遊月さんが自力で考えた方法

# define BITC1(n) ((u_int)(n) & 1)
# define BITC2(n) (BITC1 ((n) >>  1) + BITC1 (n))
# define BITC4(n) (BITC2 ((n) >>  2) + BITC2 (n))
# define BITC8(n) (BITC4 ((n) >>  4) + BITC4 (n))
# define BITC16(n) (BITC8 ((n) >>  8) + BITC8 (n))
# define BITC32(n) (BITC16((n) >> 16) + BITC16(n))

なんか同じものを使うのが嫌だったので、自分なりに考えてみました。
加算とシフトだけしか使ってないので速いはず。と思ってますが、マクロを展開するとすごく長くなる衝撃的事実がわかり、ちょっと悲しい。
たぶん、同じもの転がってるんじゃないでしょうか。

●どれが一番速いのか

このご時世、何でもいいです。いまや速度アップをガンバるのは趣味の世界です。むしろ可読性の高い回すだけの方が最適化もかかっていいと思います。

●おまけ

C++に至ってはカウントする方法が用意されています。

C++03～

std::bitset<4> bs("1011");
int n = bs.count();

C++20

int n = std::popcount(n);

他にも遊んでみたパターンとかあったら教えてください。さりげなく使わせていただきます。ライセンスフリーでお願いしますw