1のビットを数える

01011010を4にする関数。
結論から言うと、__builtin_popcountを使えば良い。

int popcount(unsigned int n) {
	int i = 0;
	while (n) {
		i += n & 1;
		n >>= 1;
	}
	return i;
}

ごく普通にやるとこう。遅い。

int popcount(unsigned int n) {
	int i = 0;
	while (n) {
		i += ((n & 3) + 1) >> 1;
		n >>= 2;
	}
	return i;
}

2ビットずつ数えるバージョン。あまり速くない。

int popcount(unsigned int n) {
	int i = 0;
	while (n) {
		n &= n - 1;
		i++;
	}
	return i;
}

n & (n - 1)が一番右の1のビットを消すことを利用したバージョン。悪くない。
と、ここまで考えたところでギブアップし、検索したらビットを数える・探すアルゴリズムを見つけた。すごい。