【位运算】二进制中1的个数（lowbit运算）-526互联

lowbit的概念

我们知道，任何一个正整数都可以被表示成一个二进制数。如：

(2)₁₀=(10)₂

(4)₁₀=(100)₂

那么定义一个函数f(x) = lowbit(x)，输入一个十进制数，返回二进制中最低一位的1所表示的值，如lowbit(4)=4

先了解原码补码反码

原码：是最简单的机器数表示法。用最高位表示符号位，‘1’表示负号，‘0’表示正号。其他位存放该数的二进制的绝对值
举例

1010 ：最高位为‘1’,表示这是一个负数，其他三位为‘010’，
即（0*2^2）+（1*2^1）+（0*2^0）=2（‘^’表示幂运算符）
所以1010表示十进制数（-2）
同理 0010表示十进制数（2）

0001+0010=0011 （1+2=3）ok

0000+1000=1000 （+0+（-0）=-0） ok

0001+1001=1010 （1+（-1）=-2）no

由此引出了反码的概念来解决1 + -1 = -2的问题
反码：正数的反码还是等于原码，负数的反码就是他的原码除符号位外，按位取反。
举例

若以带符号位的四位二进制数为例：
3是正数，反码与原码相同，则可以表示为0011
-3的原码是1011，符号位保持不变，低三位（011）按位取反得（100）所以-3的反码为1100

0001（1 ）+1110 (- 1)=1111（-7）no 正确答案为0

1110（-1）+1101（-2）=1011（-4）no 正确答案为-3

1110（-1）+1100（-3）=1010（-5）no 正确答案为-4

细心的你可能发现，除了第一个,其他计算错误的结果差值只是相差了1

由此引出了补码的概念来解决问题
补码：正数的补码等于他的原码，负数的补码等于反码+1。也等于正数反码+1。

可能有小伙伴疑惑为什么 0001（1 ）+1110 (- 1)=1111（-7）no 正确答案为0
如果这个+1不是会错误吗??
哈哈，显然不是
机器码的位数在操作系统中是固定位，假设只有4位
源码 1 : 0001 -1:1001
补码 1 ：0001 -1:1110 + 1 = 1111
补码相加 1 + -1 = 0001 + 1111 = 10000，因为保留4位，所以最终结果为0000
nice~~完美

负数的补码等于反码+1，也等于正数反码+1。
1. -1 ：1001 -> 1111
2. -1 : (1: 0001)的反码 1110 + 1 -> 1111

lowbit函数有两种实现方法：

x&(x^(x-1))

x&-x

我们先来解释第一个，还是先拿(6)₁₀举例

(6)₁₀-(1)₁₀=(5)₁₀

(110)₂-1=(101)₂

我们发现，根据小学数学减法运算的借位原则（滑稽），对一个二进制数进行减1，那么会出现从这个这个数的最后一个1开始到最后的所有数都取反，即构成一个 $01111 \dots$ 的串。

我们把这个数与原数异或，就会造成：第一个1以后的数（包括第一个1）全部取1.其他的位全部取0.即构成一个由一堆0后面跟一堆1的串。

那么再把原式做一个与运算，那么除了原来的那个1（对应位都是1）为1，其他位全是0，完成任务。

现在来解释第二个，依旧拿(6)₁₀举例子

根据计算机的补码的性质，补码等于原码的反码+1

-x = ~x + 1

例子：

x = (9)₁₀= 0 1001

-x = 1 0110 + 1 = 1 0111

再做与操作，得0 0001，这样就得到第一个1

用lowbit运算统计1的个数

我们可以使用lowbit运算统计一个整数的二进制形式下1的个数。

实现原理很简单啦，就是：我们先用lowbit运算找出 $l o w b i t (x)$ ，然后用原数减去这个数，依次循环，直到为0为止。

这也是树状数组的实现原理。

#include <iostream>

using namespace std;

int lowbit(int x){
    return x & -x;
    //-x = ~x + 1 //(x取反加1)
}

int main(){
    int n;
    cin >> n;

    while(n --){
        int x;
        cin >> x;
        int res = 0;
        while(x) {
            x -= lowbit(x);
            res ++;
        }
        cout << res << " ";
    }
    return 0;
}