神奇的位运算（计算二进制中1的个数）

caoxiaolin

发现一个好玩的算法

[C] 纯文本查看 复制代码

#include <stdio.h>

//方法1
int count_ones(int num)
{
	int count = 0;
	
	while(num > 0)
	{
		if(num & 01 == 1)
		{
			++count;
		}
		
		num >>= 1;
	}
	
	return count;
}

//方法2
int count_ones2(int a)
{
	int m_1 = 0x55555555; // 01 01 01 ..
	int m_2 = 0x33333333; // 0011 0011 ..
	int m_4 = 0x0f0f0f0f; // 0000 1111
	int m_8 = 0x00ff00ff; // 00000000 11111111
	int m_16 = 0x0000ffff;// 0000... 1111...
	
	int b = (a & m_1) + ((a >> 1)&m_1);
	int c = (b & m_2) + ((b >> 2)&m_2);
	int d = (c & m_4) + ((c >> 4)&m_4);
	int e = (d & m_8) + ((d >> 8)&m_8);
	int f = (e & m_16) + ((e >> 16)&m_16);
	
	return f;
}

int main(void)
{
	int num = 9;
	int ret;
	
	ret = count_ones(num);
	printf("%d\n", ret);
	
	ret = count_ones2(num);
	printf("%d\n", ret);
	
	return 0;
}

哈哈，自己画了个图

kk1212

楼主你这个算法主要是用于什么场景呢，游戏还是？

happyqq521

你需要剑指offer
int TheNumOf1(unsigned int num)
{
        int count = 0;
        while (num)
        {
                num = num&(num - 1);
                count++;
        }
        return count;

caoxiaolin

happyqq521 发表于 2018-8-29 12:08
你需要剑指offer
int TheNumOf1(unsigned int num)
{

谢谢，大佬！

peachglide

方法2很精妙，不用循环就可以得出，主要用于相似度算法