求一個數字二進制中 1 的個數

問題描述

任意給定一個 32 位無符号的整數 n，計算 n 的二進制表示中 1 的個數，比如 n = 3（011)）時，傳回 2

這是一到筆試面試經典的題目，下面介紹幾種解法來實作這一道題目，如果你有更好的解法，歡迎指導交流

方法一：普通法

通過移位解決，每次向右移一位（ >> 1），然後判斷最後一位是不是 1（&1），最多循環 32 次

int BitCount(unsigned int n)
{
	int count = 0;
	while (n > 0) {
		if (n & 1 == 1) {
			count++;
		}
		n = n >> 1;
	}
	return count;
}           

使用下面的測試用例計算一下時間

int main(void) {

	std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();
	for (uint32_t i = 1; i <= numeric_limits<long long>::max(); ++i) {
		BitCount(i);
	}
	std::chrono::high_resolution_clock::time_point end = std::chrono::high_resolution_clock::now();
	std::chrono::duration<double, std::milli> time_span = end - start;
	std::cout << "time:" << time_span.count() << std::endl;
	getchar();
	return 0;
}           

時間列印是：time:0.0012

方法二：快速法

這種方法速度比較快，運算次數與 n 中 1 的個數有關，每次不斷的清除 n 二進制中最右邊的 1，同時累加計數器，一直到 n 為 0，一般筆試面試給出這種解法也就可以了

int BitCount(unsigned int n)
{
	int count = 0;
	while (n > 0) {
		n &= (n - 1);
		count++;
	}
	return count;
}           

時間列印是：time:0.0005

最常見的就是這兩種辦法了，尤其是第二種在面試的時候是很喜歡問的

方法三：查表法

用于求一個連續集合内，所有數字二進制種 1 的個數

要求實作 vector<int> countBits(int num) 函數

這裡運用一個比較巧妙的思想，對于一個正整數 n

1、如果 n 是偶數，那麼 n 二進制的個數與 n / 2 中二進制的格式都是一樣的，比如 2，4，8，16，32，64，他們都隻有一個 1，再比如 6 和 3 的二進制都是 2 個 1，因為 n 是由 n/2 左移一位過來的，左移是在結尾補 0，是以 1 的個數并不會增加

vector<int> countBits(int num) {
	int bits[4] = { 0,1,1,2 };
	std::vector<int> result;
	result.push_back(0);
	for (int i = 1; i <= num; ++i) {
		if (i == 4) {
			break;
		}
		result.push_back(bits[i]);
		
	}
	
	if (result.size() == num + 1) {
		return result;
	}
	
	for (int i = 4; i <= num; ++i) {
		int count = result[(i >> 1)];
		if (i & 1 != 0) {
			count += 1;
			
		}
		result.push_back(count);
	}
	return result;
}