0x07 lowbit运算
[toc]
1. 什么是lowbit运算
二进制只有两种状态，0和1。对于一个整数，在二进制中的表示也是由许多0和1表示的。而lowbit运算，就是求出二进制数字最低的一个1。如00100100这个二进制数字，最低位的1就是00000100。
lowbit运算的公式为lowbit(n) = n & (~n + 1) = n & -n。该运算的时间复杂度为O(1)。
2. lowbit运算的证明
对于整数n，假设n最低的1在第x位，那么n[x + 1, log2n]位都将是0，其中log2n是n在二进制中的最大位数。那么如果对n取反，n[1, x - 1]都将变成之前的相反位，n[x]将从1变成0，n[x + 1, log2n]将从全0变成1。
这时给~n加1，就会从最后一位到x+1位一直进位，最终进到第x位，这时n[x, log2n]又变成了之前的状态，而x之前都是取反的状态。再与一下，就求出了这个最低位的1。
3. 求数字中有多少位1
求数字中多少位1可以通过lowbit运算快速做出来，只要不断lowbit运算，再减去最低位1，直到为0即可。虽然时间复杂度相对于直接对二进制中每一位统计的方法还是O(log2n)，但是因为大O表示法是求时间复杂度的上界，如果是时间复杂度下界，就是Ω(1)的。
最后更新:
May 29, 2022