「位运算」二进制中质数个计算置位

发表于 2022-04-05 更新于 2022-04-27 Artalk： loading...

bitCount源码分析位运算判断质数比特计数

主要是比特计数和判断质数

762. 二进制表示中质数个计算置位

“求给定范围内，二进制表示下，'1’的个数为质数(素数)的数字有多少”

判断一个数是否为质数
求置位位数(二进制表示下，'1’的个数)

bitCount源码分析部分

问题描述

数据范围为

判断是否为质数

质数：大于1的数中，只能被1和本身整除的数，称为质数或者素数。最小的质数为2。

初步思路

boolean isP(int x) {
    if (x == 1) return false;
    for (int i = x / 2; i > 1; -- i) {
        if (x % i == 0) return false;
    }
    return true;
}

改进

由于乘法的运算效率要高于除法，因此可以用乘法替换除法

boolean isP(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0) return false;
    }
    return true;
}

再次改进

由于输入的数在 $[1,10^6]$ 范围内，而 $\lceil \log_2{10^6}\rceil=20$ ，即二进制1的个数最多为19(开区间，不可能取到20)，而小于等于19的质数只有 $\{2,3,5,7,11,13,17,19\}$ ，因此可以借鉴之前 $bitMap$ 的思想，用一个 $int$ 型变量来存储： $0b\ \cdots \ 1010 \ 0010 \ 1000 \ 1010 \ 1100$ ，转换为10进制为 $665772$ 。接下来判断是否为质数的操作就简化了许多。

1	if (((1 << count(i)) & 665772) != 0) res ++;

比特计数

初步思路

最朴素想法：直接遍历每一个二进制位，如果为1，则计数器加1

int count(int x) {
    int cnt = 0;
    for (int i = 30; i >= 0; --i) {
        if ((x >> i & 1) == 1) cnt++;
    }
    return cnt;
}

进阶思路

众所周知， $x \& (x$ - $1)$ ，可以去除二进制最后一个 $1$ 。

在循环中，不停地对 $x$ 做这个操作，直到 $x=0$ ，每一次循环，计数器加1，即可统计出 $1$ 的个数。

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

最优思路

java jdk中有现成的函数 $Integer.bitCount()$

以下为其源码

jdk@1.8

public static int bitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

参考两篇写得很好的博客

Integer.bitCount() 函数理解
java源码Integer.bitCount算法解析，分析原理（统计二进制bit位）

这个算法是优化后的版本

计算流程

先看原始版本

public static int bitCount(int i) {
    i = (i & 0x55555555) + ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i & 0x0f0f0f0f) + ((i >>> 4) & 0x0f0f0f0f);
    i = (i & 0x00ff00ff) + ((i >>> 8) & 0x00ff00ff);
    i = (i & 0x0000ffff) + ((i >>> 16) & 0x0000ffff);
    return i;
}

简单来说，是依次统计每两位的 $1$ 的个数、每四位的 $1$ 的个数、每八位(一个Byte字节)的 $1$ 的个数

1
2
3

i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;

然后移位，将(从高位到低位的顺序)第一个、第二个、第三个字节的值(此时每个字节单独出来的值=本字节的1个数)累加到第四个字节上

1 2	i = i + (i >>> 8); i = i + (i >>> 16);

然后输出有效位的值即可 return i &0x3f，因为 $int$ 型变量最多32位， $\log_2{32}=5$ ，最多需要6位二进制位即可表示全部(因为5位表示的范围为 $[0,2^{5}$ - $1]=[0,31]$ )

1	0x3f=0b0011 1111

$i \& 0x3f$ 表示取最低6位的值。

关于以上每步的详细解释

第一步

假设现在要统计 $x=0b1101=13$ 的二进制1的个数

0x5=0b0101，x & 0x5 得到的是，每一个偶数二进制位上的 $1$ 的个数，值为1代表该位有1个 $1$ ，值为0代表该位有0个 $1$

1101 & 0101 = 0101
说明在第0位上有1个1，第2位上有1个1。（从低位到高位开始数）

x >>> 1 & 0x5，先将 $x$ 右移一位，得到的是，每一个奇数二进制位上的 $1$ 的个数

1101 >>> 1 = 0110
0110 & 0101 = 0100
说明在第1位上有0个1，第3位上有1个1。

然后相加，结果得到1001 ，这个得到的就是每两位的 $1$ 的个数

1001 按两位分开看
10 01 前两位有 0b01=1 个1，后两位有 0b10=2 个1

接下来就类似的思路

0x3=0b0011 取的是每四位低两位的值

通过x & 0x3 和 x >>> 2 & 0x3 得到前两位和后两位的 $1$ 的个数，然后加起来即为每四位

的 $1$ 的个数

$x$ 此时更新为了0b1001
1001 & 0011 = 0001
1001 >>> 2 & 0011 = 0010

0001 + 0010 = 0011
即0b1101的低四位有0011=3个 $1$ ，由于0b1101=13二进制只有四位，实际上3就是其全部的 $1$ 的个数。

0xffffffff依此类推

第二步

为什么没有继续计算每16位和每32位的 $1$ 的个数？

~~因为没必要~~

经过前面三轮

// 优化后的代码
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;

已经得到了每八位(每个字节)的 $1$ 的个数，假设从高位起，四个字节分别为 $B1,B2,B3,B4$ 。

执行i += i >>> 8之后

$B2'= B1+B2,\ B4'=B3+B4$

再执行i += i >>> 16之后

$B4''=B2'+B4'=B1+B2+B3+B4$

第四个字节保存了所有字节的值的和，而第四个字节是最低位，其单独拿出来的值就是真实的值

这里想表达什么呢？举个🌰
现在 $x=0b0000\ 0000 \ |\ 0000\ 0000\ |\ 0000 \ 0101\ |\ 0000\ 0011$
第三个字节为0000 0101=5，第四个字节为000 0011=3
而实际上第三个字节代表的值为 0000 0101 0000 0000 = 5 * 256 = 1280
第四个字节代表的值则就是3