在0中找1

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

题目

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

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

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

与运算和右移的解

思路：

位运算的与操作：

……1₍₂₎&1₍₂₎=……1₍₂₎

……1
&	1
……1

……0₍₂₎&1₍₂₎=……0₍₂₎

……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