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

来自姬鸿昌的知识库
跳到导航 跳到搜索
第84行： 第84行：
 
10
 
10
 
</syntaxhighlight>时间复杂度O(n)，n是0、1一共有多少位。
 
</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
 +
!
 +
|}

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

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