lowbit 运算

Lowbit(x) 表示求x在二进制下位最低的1连同后面的0所组成的数字。
举个例子：6的二进制表示是110₍₂₎，那么lowbit(6)=10₍₂₎=2，也就是lowbit(6)=2。

int lowbit(int x){
    return x&(-x);
}
等同于：
int lowbit(int x){
    return x&((~x)+1);
}

即 lowbit(x)=x&((~x)+1)=x&(-x) 。

lowbit 运算配合 Hash 可以找出整数二进制表示下所有是 1 的位，所花费的时间与 1 的个数同级。 为达该目的，只需不断把 n 赋值为 n – lowbit(n)，直至 n = 0。
例如，n = 9 = (1001)₂，则 lowbit(9) = 1。把 n 赋值为 9 – lowbit(9) = 8 = (1000)₂，则 lowbit(8) = 8 = (1000)₂。此时 8 – lowbit(8) = 0，停止循环。在整个过程中减掉了 1 和 8 = (1000)₂ 两个数，它们恰好是 n 每一位上的 1 后面补 0 得到的数值。取 1 和 8 的对数 log2¹ 和 log2⁸，即可得知 n 的第 0 位和第 3 位是 1。 因为 C++ math.h 库的 log 函数是以 e 为底的实数运算，并且复杂度常数较大，所以需要预处理一个数组，通过 Hash 的方法代替 log 运算。
当 n 较小时，最简单的方法是直接建立一个数组 H，令 H[2^k] = k，程序如下：

const int N=1<<20;
int H[N+10];
for(int i=0;i<=20;i++) H[1<<i]=i;//预处理
while(cin>>n){
    while(n>0) {
	cout<<H[n&-n]<<' ';
	n-=n&-n; //即n-lowbit(n)
    }
    cout<<endl;
}

稍微复杂但效率更高的方法是建立一个长度为 37 的数组 H，令 H[2^k mod 37] = k。这里利用了一个小的数学技巧：∀k ∈ [0,35] , 2
^k mod 37 互不相等，且恰好取遍1 ~ 36。需要之后的程序为：

int H[37];
for(int i=0;i<36;i++) H[(1ll<<i)%37]=i;
while(cin>>n) {
    while(n > 0) {
	cout<<H[n&-n]<<' ';
	n-=n&-n;  //即n-lowbit(n)
    }
    cout<<endl;
}

值得指出的是，lowbit 运算也是树状数组中的一个基本运算。

GCC编译器还提供了一些内置函数，可以高效计算 lowbit 以及二进制数中 1 的个数。不过，这些函数并非 C 语言标准，有的函数更是与机器或编译器版本有关。另外，在部分竞赛中禁止使用下划线开头的库函数，所说这些内置函数尽量不要随便使用。

int __builtin_ctz(unsigned int x)
int __builtin_ctzll(unsigned long long x)
计算输入数x的二进制表示下最低位的1后面有多少个0。

int __builtin_popcount(unsigned int x)
int __builtin_popcountll(unsigned long long x)
计算输入数x的二进制表示下有多少位1。