“在0中找1”的版本间的差异

来自姬鸿昌的知识库
跳到导航 跳到搜索
第305行： 第305行：
 
!
 
!
 
|}
 
|}
 +
<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>

2022年11月14日 (一) 04:05的版本

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
取自“https://www.jihongchang.top/index.php?title=在0中找1&oldid=3494”