查看“在0中找1”的源代码

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

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

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

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



=== 与运算和右移的解 ===

==== 思路： ====

===== 位运算的与操作： =====
……1<sub>(2)</sub>&1<sub>(2)</sub>=……1<sub>(2)</sub>
{| class="wikitable"
| colspan="2" |……1
|-
|&
|1
|-
| colspan="2" |……1
|}



……0<sub>(2)</sub>&1<sub>(2)</sub>=……0<sub>(2)</sub>
{| class="wikitable"
| colspan="2" |……0
|-
|&
|1
|-
| colspan="2" |……0
|}





===== 右位移 =====
>>
{| class="wikitable"
|1
|1
|1
|0
|}
→
{| class="wikitable"
|0
|1
|1
|1
|}

==== 代码实现示例 ====
<syntaxhighlight lang="java">
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);

    }

}
</syntaxhighlight><syntaxhighlight lang="console">
10
</syntaxhighlight>时间复杂度O(n)，n是0、1一共有多少位。


=== x&x-1的解法 ===
思路：

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

原理：

假设 x 是“10000001”，第1次：
{| class="wikitable"
|
|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次：
{| class="wikitable"
|
|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次：
{| class="wikitable"
|
|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次：
{| class="wikitable"
|
|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次：
{| class="wikitable"
|
|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次：
{| class="wikitable"
|
|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
!
|}
<syntaxhighlight lang="java">
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);

    }

}
</syntaxhighlight><syntaxhighlight lang="console">
10
</syntaxhighlight>时间复杂度是O(n)，但这里的n是整个二进制数中1的个数，少了很多





=== 时间复杂度为O(1)的归并算法 ===
思路：

假设输入16位的二进制数a
{| class="wikitable"
|a
|
|-
|b0 = (a >> 0) & 01 01 01 01 01 01 01 01 
| rowspan="2" |相邻2位里1的个数
|-
|b1 = (a >> 1) & 01 01 01 01 01 01 01 01
|-
|c = b0 + b1
|
|-
|d0 = (c >> 0) & 0011 0011 0011 0011
| rowspan="2" |相邻4位里1的个数
|-
|d2 = (c >> 2) & 0011 0011 0011 0011
|-
|e = d0 + d2
|
|-
|f0 =  (e >> 0) & 00001111 00001111
| rowspan="2" |相邻8位里1的个数
|-
|f4 =  (e >> 4) & 00001111 00001111
|-
|g = f0 + f4
|
|-
|h0 = (g >> 0) & 0000000011111111
| rowspan="2" |相邻16位里1的个数
|-
|h8 = (g >> 8) & 0000000011111111
|-
|i = h0 + h8
|
|}
{| class="wikitable"
!x
!1
!1
!0
!0
!0
!1
!1
!1
|-
!相邻2位里1的个数
! colspan="2" |2
! colspan="2" |0
! colspan="2" |1
! colspan="2" |2
|-
!相邻4位里1的个数
! colspan="4" |2
! colspan="4" |3
|-
!相邻8位里1的个数
! colspan="8" |5
|}

=== 预计算哈希表存储个数 ===
提前算好存储，用的时候像字典一样使用。

=== 总结 ===

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