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

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函数有两种实现方法：

1.

x&(x^(x-1))

2.

x&-x

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

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

(110)₂-1=(101)₂

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

我们把这个数与原数异或，就会造成：第一个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运算找出lowbit(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;
}

lowbit运算的应用

关于lowbit运算，最著名的应用应该算是树状数组。但是lowbit的神妙远远不止树状数组，在很多二进制和位运算的相关题目中，都有lowbit运算的影子。甚至，在状态压缩DP中，lowbit也扮演着一份不可忽视的角色。