网站 › 『编程语言区』 › 神奇的位运算（计算二进制中1的个数）

caoxiaolin 发表于 2018-8-29 11:27

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

发现一个好玩的算法
{:301_975:}

#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 发表于 2018-8-29 12:06

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

happyqq521 发表于 2018-8-29 12:08

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

caoxiaolin 发表于 2018-8-29 16:18

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


谢谢，大佬！

peachglide 发表于 2018-8-30 16:51

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

查看完整版本: 神奇的位运算（计算二进制中1的个数）