bitCount

doper

发布于 2022-09-26 17:46:35

7110

发布于 2022-09-26 17:46:35

文章被收录于专栏：后台技术杂项笔记

bitCount-计算数字二进制中1的个数

主要介绍bitcount位运算实现，思路和java中bitcount的实现一样。

1. 题目描述

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量).）。

LeetCode

2. 解决方法

解法1

第一反应就是直接暴力，代码如下:

int hammingWeight(uint32_t n) {
    int ret = 0;
    for (int i = 0; i < 32; i++) {
        if (n & (1 << i)) {
            ret++;
        }
    }
    return ret;
}

这种算法的时间复杂度O(k)，因为这里为uint32_t，k为32。取决于传入的数据的数据类型长度。

空间复杂度O(1)。

解法2

在解法一中这种算法可以优化，具体分析过程见leetcode。代码如下

int hammingWeight(uint32_t n) {
    int ret = 0;
    while (n) {
        n &= n - 1;
        ret++;
    }
    return ret;
}

时间复杂度O(log_n)，循环次数等于n的二进制位中1的个数。

空间复杂度O(1)。

解法3

除了上述解法外，还有一种基于位运算的解法，先上C/C++代码

int hammingWeight(uint32_t n) {
    n = n - ((n >> 1) & 0x55555555);
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
    n = (n + (n >> 4)) & 0x0f0f0f0f;
    n = n + (n >> 8);
    n = n + (n >> 16);
    return n & 0x3f;
}

这也是java里bitcount的实现。下面具体分析这种解法的过程。

3. bitcount解法分析

为了更好的了解过程，下面将对上述解法3的代码逐行分析。

第一行

n = n - ((n >> 1) & 0x55555555);

要理解这一行代码的作用，首先要先明白下述原理。

一个2bit的二进制数，其所有的组合有00, 01, 10, 11。若要计算这个2bit的数的二进制有多少个1，则可以用这个数减去其二进制第二个位上的数字，得到的便是这个2bit数字的二进制中的1个个数。

根据这个原理，就可以知道上面那行代码的作用，它依次统计两个bit上1的个数，并将结果保存到对应的两个bit上，举例:

第二行

n = (n & 0x33333333) + ((n >> 2) & 0x33333333);

在上面我们将数字每2个bit分一组，计算出这两个bit有多少个1，并将结果放到对应的组上。这行代码的目的则是为了将相邻两组中的1的个数加起来。从而实现将数字二进制中4个bit为一组进行分组，并且每组中1的个数有多少个。

继续复用上述例子

第三行

n = (n + (n >> 4)) & 0x0f0f0f0f;

与上述同理，将数字8个bit为一组，并计算每组有多少个1

第四行

n = n + (n >> 8);

这里也和上述同理，利用8bit分组的结果，将相邻两个8bit组和起来，计算16bit一组中，每组中有多少个1。

第五行

n = n + (n >> 16);

同理，计算32bit一组有多少个1。

第六行

return n & 0x3f;

因为n为32位，在最大的情况下也只有32个1，因此用6个位即可表示所有情况。因此和0x3f与运算。

全部代码

n = n - ((n >> 1) & 0x55555555);	// 1
n = (n & 0x33333333) + ((n >> 2) & 0x33333333);	// 2
n = (n + (n >> 4)) & 0x0f0f0f0f;	// 3
n = n + (n >> 8);	// 4
n = n + (n >> 16);	// 5
return n & 0x3f;	// 6

这里可能会有疑问，既然在return的时候已经只取了最后6个位，那为什么第2 3行不可以和第4 5行一样不要过滤呢？看下面这个例子。

当我们输入uint32_t类型的最大值的时候，分别看有过滤和没过滤，每一行代码的输出结果

验证代码:

#include <iostream>
#include <climits>

using namespace std;

void print_bin(unsigned n) {
    int i;
    for(i = sizeof(n)*8 - 1; i>=0; --i) {
        if(n & (1<<i)) {
            printf("1");
        } else { 
            printf("0");
        }
        if(i % 4 == 0) {
            printf(" ");
        }
    }
    printf("\n");
    return ;
}

int bitCount(unsigned i) {
    printf("原始数字i = %u\n二进制:\n", i);
    print_bin(i);
    printf("统计每2位\n");
    i = i - ((i >> 1) & 0x55555555);
    print_bin(i);
    printf("统计每4位\n");
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    print_bin(i);
    printf("统计每8位\n");
    i = (i + (i >> 4)) & 0x0f0f0f0f;			// 注意这一行
    print_bin(i);
    printf("统计每16位\n");
    i = i + (i >> 8);
    print_bin(i);
    printf("统计每32位\n");
    i = i + (i >> 16);
    print_bin(i);
    printf("最终过滤\n");
    print_bin(i & 0x3f);
    return i & 0x3f;
}

int main() {
    cout << bitCount(UINT_MAX) << endl;
    return 0;
}

有0x0f0f0f0f过滤的

无0x0f0f0f0f过滤的把n = (n + (n >> 4)) & 0x0f0f0f0f;中的0x0f0f0f0f删掉。

这里可以发现最终结果中多了一个1,现在顺着输出往回找看看这个1是哪里来的。

可以发现由于没有过滤，其无效bit在加的过程导致其进位到有效bit上了，直接导致结果出错。

那为什么后面就不需要过滤？理论上可以过滤，但是在32位的情况下可以发现到后面，即使无效bit再怎么和前面相加，都不会导致其进位到有效bit上了（比如在i = i + (i>>8)中，因为高8位和低8位中的前4位在上面已经置0了，而两个4bit的数相加的大小是不可能超过8bit的，也就不会有无效位进位问题了）。因此就在最后return的时候过滤，减少算法与运算的次数，提高效率。

emm…反正挺麻烦的，最后再看一下大概流程。

int hammingWeight(uint32_t n) {
    n = n - ((n >> 1) & 0x55555555);	//2bit一组，计算有多少个1
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);	//根据2bit分组的结果，计算4bit一组有多少个1
    n = (n + (n >> 4)) & 0x0f0f0f0f;	//根据4bit分组的结果，计算8bit一组有多少个1
    n = n + (n >> 8);	//根据8bit分组的结果，计算16bit一组有多少个1，这里没过滤，有无效位
    n = n + (n >> 16);	//根据16bit分组的结果，计算32bit一组有多少个1，这里也没过滤，有无效位
    return n & 0x3f;	//一次性过滤，只取最后6个位的结果。
}