在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的个数，少了很多