lowbit原理

分为朴素版、化简版。

一，朴素版

适用条件

n为实数。

记忆方法

一个数a与上他的补码b，所得的数的二进制只保留了a的最后一位1，其他位全都是0.

公式

lowbit(x) = x & (~x + 1)；

原理

• 设第k位为最后一个1，1到 k - 1 位都是0（从左（低位）向右（高位））。

• 以52（0011 0100）为例， 它的lowbit(52) = 100 = 4。

  • ​ n 0011 0100
  • ~n 1100 1011
  • ~n + 1 1100 1100

• 

• 这里k前面的高位取反之后就没有动过了，后面的0取反变成了1之后加上1又变成了0。x & (~x + 1)只有只有第k位还是1。

二，化简版

公式

lowbit(x) = x & (- x);

适用条件

只能用于n是正数的情况中，因为正数 + 上个 负号变成了负数，负数的补码就是它的源码取反+1。式子是由这个推导出来的

原理

根据计算机中补码的知识推导公式。

• x是个正数，那么-x就是个负数，负数的补码是取反+1
  • 所以 -x = ~x + 1。
  • 所以 ~x = -x - 1。带入原式 x & (~x + 1) => x & (-x)。

三，求某个数二进制中1的个数

• 每次让该数减去lowbit(x)---最后一位1，减了多少次就是有多少个1。

#include <bits/stdc++.h>

using namespace std;

int main()
{

    int x, s = 0;
    for (int i = x; i >= 0; i -= i & (-i)) s ++;
    cout << s << '\n';

    return 0;
}