プログラミング言語 C 2.9

ある整数 xに対して、 x & (x-1)が最も右の "1"であるビットを削除するという
事実を使って、bitcountの高速版を作れという問題。x & (x-1)がこうなる理由は
x & (x-1)をすると、最も右の 1ビット以下のビットが反転するため、それと論理積を
とるとすべて 0になるため。

#include <stdio.h>
#include <assert.h>
#include "util.h"

static int bitcount(unsigned int x);
static void test_bitcount(void );

int
main(void)
{
     test_bitcount();
     return 0;
}

static void
test_bitcount()
{
     assert(bitcount(0x0) == 0);
     assert(bitcount(0x1) == 1);
     assert(bitcount(0xf) == 4);
     assert(bitcount(0xffff) == 16);
     assert(bitcount(0xffffffff) == 32);
}

static int
bitcount(unsigned int x)
{
     int count = 0;

     if (x >= 1) {
          count = 1;
     }

     while ((x = (x & (x - 1))) != 0) {
          count++;
     }

     return count;
}