二进制数的1的数量

算法实现

这个实现很多地方都有

unsigned int popcount_u64(unsigned long long x)
{
    //按2位: 00->00, 01/10->01, 11->10
    x = x - ((x >> 1) & 0x5555555555555555ULL);

    //按4位: [0000, 0001, 0010, 0100, 0101, 0110, 1000, 1001, 1010] -> [0000, 0001, 0010, 0011, 0100](0/1/2/3/4)
    x = (x & 0x3333333333333333ULL) + ((x >> 2) & 0x3333333333333333ULL);

    //按8位: [00000000, 00000001, ..., 10101001, 10101010] -> [0x00, 0x01, ..., 0x8](0~8)
    x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0FULL;

    //乘以0x0101010101010101，所有的8位求和都到了最高8位(最大64不会溢出)，右移56位取出最高8位
    return (x * 0x0101010101010101ULL) >> 56;
}

unsigned int popcount_u32(unsigned int x)
{
    return popcount_u64((unsigned long long)x);
} 

测试程序

#include <time.h>
#include <stdlib.h>
#include <stdio.h>

unsigned int popcount_u64(unsigned long long x)
{
    //按2位: 00->00, 01/10->01, 11->10
    x = x - ((x >> 1) & 0x5555555555555555ULL);

    //按4位: [0000, 0001, 0010, 0100, 0101, 0110, 1000, 1001, 1010] -> [0000, 0001, 0010, 0011, 0100](0/1/2/3/4)
    x = (x & 0x3333333333333333ULL) + ((x >> 2) & 0x3333333333333333ULL);

    //按8位: [00000000, 00000001, ..., 10101001, 10101010] -> [0x00, 0x01, ..., 0x8](0~8)
    x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0FULL;

    //乘以0x0101010101010101，所有的8位求和都到了最高8位(最大56不会溢出)，右移56位取出最高8位
    return (x * 0x0101010101010101ULL) >> 56;
}

unsigned int popcount_u32(unsigned int x)
{
    return popcount_u64((unsigned long long)x);
} 

//Brian Kernighan 算法
unsigned int popcount_(unsigned long long x) {
    unsigned int count = 0;

    while (x != 0) {
        x &= x - 1;
        count++;
    }

    return count;
}


#define NUM 1000

int main()
{
    unsigned long long test[NUM];
    int err = 0;

    srand(time(NULL));  
    for (int i = 0; i < NUM; i++)
        test[i] = ((unsigned long long)rand()) << rand();  

    for (int i=0; i<10; i++)
        printf("%llx, %d\n", test[i], popcount_u64(test[i]));
    printf("\n");

    for (int i=0; i<NUM; i++)
        if (popcount_u64(test[i]) != popcount_(test[i])) {
            printf("fail: %llx\n", test[i]);
            err++;
        }

    if (!err) printf("success!\n");

    return 0;
}

原文地址：https://blog.csdn.net/qq_43491149/article/details/142529303

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！