在0中找1

来自姬鸿昌的知识库
跳到导航 跳到搜索

https://www.bilibili.com/video/BV1UK411D724

题目

比如给定“10001110”，答案是4；

在比如“10001000”，答案是2；

那如果是“1000111010001000……”非常多、非常长呢？


与运算和右移的解

思路：

位运算的与操作：

……1(2)&1(2)=……1(2)

……1
& 1
……1


……0(2)&1(2)=……0(2)

……0
& 1
……0



右位移

>>

1 1 1 0

→

0 1 1 1

代码实现示例

public class Test {

    public static void main(String[] args) {
        long count1in0 = 0b00101010010100000000011111;

        int count = 0;

        while (count1in0 != 0) {

            if ((count1in0 & 1) % 10 == 1) {
                count++;
            }

            count1in0 >>= 1;

        }

        System.out.println(count);

    }

}

10

时间复杂度O(n)，n是0、1一共有多少位。


x&x-1的解法

思路：

x&(x-1)如果为1则计数，然后无论是否计数继续执行x&(x-1)的操作，直到 x为0；

原理：

假设 x 是“10000001”，第1次：

1 0 0 0 0 0 0 1 x
& 1 0 0 0 0 0 0 0 x-1
1 0 0 0 0 0 0 0

第2次：

1 0 0 0 0 0 0 0 x
& 0 1 1 1 1 1 1 1 x-1
0 0 0 0 0 0 0 0

再比如：

x是“10101010”,第1次：

1 0 1 0 1 0 1 0 x
& 1 0 1 0 1 0 0 1 x-1
1 0 1 0 1 0 0 0

第2次：

1 0 1 0 1 0 0 0 x
& 1 0 1 0 0 1 1 1 x-1
1 0 1 0 0 0 0 0

第3次：

1 0 1 0 0 0 0 0 x
& 1 0 0 1 1 1 1 1 x-1
1 0 0 0 0 0 0 0

第4次：

1 0 0 0 0 0 0 0 x
& 0 1 1 1 1 1 1 1 x-1
0 0 0 0 0 0 0 0 
public class Test1 {

    public static void main(String[] args) {

        long count1in0 = 0b00101010010100000000011111;

        int count = 0;

        while (count1in0 != 0) {

            count1in0 &= (count1in0 - 1);

            count++;

        }

        System.out.println(count);

    }

}

10

时间复杂度是O(n)，但这里的n是整个二进制数中1的个数，少了很多



时间复杂度为O(1)的归并算法

思路：

假设输入16位的二进制数a

a
b0 = (a >> 0) & 01 01 01 01 01 01 01 01 相邻2位里1的个数
b1 = (a >> 1) & 01 01 01 01 01 01 01 01
c = b0 + b1
d0 = (c >> 0) & 0011 0011 0011 0011 相邻4位里1的个数
d2 = (c >> 2) & 0011 0011 0011 0011
e = d0 + d2
f0 = (e >> 0) & 00001111 00001111 相邻8位里1的个数
f4 = (e >> 4) & 00001111 00001111
g = f0 + f4
h0 = (g >> 0) & 0000000011111111 相邻16位里1的个数
h8 = (g >> 8) & 0000000011111111
i = h0 + h8
x 1 1 0 0 0 1 1 1
相邻2位里1的个数 2 0 1 2
相邻4位里1的个数 2 3
相邻8位里1的个数 5

预计算哈希表存储个数

提前算好存储，用的时候像字典一样使用。

总结

应用

实际“n位二进制中1的个数”有个称呼叫“汉明重量”，在RAS加密和解密的过程中就有大量求解汉明重量的情况，里面需要进行汉明重量计算的都是几百上千位的二进制数

取自“https://www.jihongchang.top/index.php?title=在0中找1&oldid=3499”