how-many-1.md

一个二进制数中有多少个一，经典问题，第一次看见是在C和指针中，使用的方法是移位。

查表

查表是最简单的做法，并且是时间复杂度最好的算法。

移位

#include <stdio.h>

int main(){
	int i = 255;
	int count = 0;
	while(i){
		if(i & 1)
			count ++;
		i = i >> 1;

	}
	printf("%d\n",count );
	return 0;
}

时间复杂度O(len(i))

时间复杂度为i中1的个数的做法

#include <stdio.h>

int main(){
	int i = 255;
	int count = (i > 0? 1: 0);
	while(i){
		if(i & (i - 1))
			count ++;
		i = (i - 1) & i;

	}
	printf("%d\n",count );
	return 0;
}

和小美蒙了一晚上的算法，竟然蒙出来了，很是刺激。

出发点很简单，从一个只有一个1的数开始，想办法消掉这个1，然后推广开到若干个1.

看到一个绝佳的解法，来自Java SDK的Integer.bitCount

public static int bitCount(int i) {
     // HD, Figure 5-2
     i = i - ((i >>> 1) & 0x55555555);
     i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
     i = (i + (i >>> 4)) & 0x0f0f0f0f;
     i = i + (i >>> 8);
     i = i + (i >>> 16);
     return i & 0x3f;
}