C++ 中的 lowbit

lowbit
的定义

首先了解
lowbit
的定义

\(lowbit(n)\)
，为
\(n\)
的二进制原码中最低的一位
\(1\)
以及其后面的
\(0\)
所表示的数

举个简单的例子：

将
\(10\)
使用二进制表示为
\(1010\)

其中最低位的
\(1\)
为第2位（
\(_{10}1_0\)
，从右往左数）

此时
\(lowbit(10)\)
使用二进制表示为
\(10\)
，即
\(2\)
. （有关进制转换详见
进制与进制转换
）

lowbit
的计算

如何计算
\(lowbit(n)\)
呢？

lowbit
的特殊情况

由于
lowbit
会将除最低位
\(1\)
以外所有的位
\(1\)
改为
\(0\)
，
lowbit
将只会对位
\(1\)
的位数高于1的二进制数产生影响，所以位
\(1\)
只有1位的二进制数和
\(0\)
处理后将得到原数据，即：

\[lowbit(2^n) = 2^n ~~~ ( n >= 0)
\]

\[lowbit(0) = 0
\]

方法一：递归

先暂时假定
\(n\)
为正整数

将
\(n\)
转换为二进制，可得：
\(00...00x...xxx\)
(
\(x\)
为
\(0\)
或
\(1\)
)

此时
\(n · 2\)
转换为二进制可得：
\(00...00x...xxx · 10 ~＝~ 00...0xx...xx0\)

假设
\(n\)
转为二进制后，末尾有
\(m\)
个连续位
\(0\)
（显然，此时
\(lowbit(n) ~ = ~ 2^m\)
）

因此，
\(n · 2\)
转为二进制后，末尾有
\(m + 1\)
个连续位
\(0\)
（此时
\(lowbit(n · 2) ~ = ~ 2^{m + 1} ~ = ~ 2^m · 2\)
）

于是我们得到了：

\[lowbit(n · 2) = lowbit(n) · 2
\]

此时
\(n · 2\)
表示为二进制是
\(00...0xx...xx0\)
，怎么样，有没有什么想法？

将
\(n · 2\)
加上
\(1\)
，得：
\(00...0xx...xx0 + 1 ~ = ~ 00...0xx...xx1\)

显然：

\[lowbit(2n + 1) ~ = ~ 1
\]

观察
\(n\)
的二进制形式：
\(00...00x...xxx\)

对比
\(-n\)
的二进制形式：
\(10...00x...xxx\)
（在原码中，我们一般使用第一位存储符号，
\(0\)
为正，
\(1\)
为负）

很明显，
\(lowbit(n) ~ = ~ lowbit(-n)\)

无论
\(n\)
的符号为负还是为正，奇偶性都一致，因此，我们在上面推导出来的公式对负整数仍然成立

综上所述，任意奇数的
lowbit
值都为
\(1\)
，任意偶数的
lowbit
值都为其乘
\(0.5\)
得到的值的
lowbit
值乘
\(2\)

通过这种思路，我们可以编写一个递归函数计算
\(n\)
的
lowbit
值，遇到奇数直接返回
\(1\)
，遇到偶数辄除以
\(2\)
后继续计算

写成伪代码是这样的：

int lowbit(int n) {
    if (n % 2 == 1) return 1;  // Odd
    else return lowbit(n / 2) * 2;  // Even
}

方法二：公式

在方法一中，我们使用了深度优先搜索，时间复杂度可能有点高，我们当然可以使用记忆化数组降低复杂度，但，我们是否可以推导出一个公式直接计算，将复杂度降低为
\(O(1)\)
呢？

当然是可行的。还是观察
\(n\)
的二进制形式：
\(00...00x...xxx\)
（假定
\(n\)
为非负整数）

还是对比
\(-n\)
的二进制形式：
\(10...00x...xxx\)

如果对
\(10...00x...xxx\)
每一位取反（符号位除外），我们就得到了
\(-n\)
的反码：
\(11...11(-x)...(-x)(-x)(-x)\)

此时
\(-n\)
末尾的
\(0\)
全部变为
\(1\)
，而最低位的
\(1\)
也难逃变为
\(0\)
的命运

如果我们现在将其加上
\(1\)
，我们将得到
\(-n\)
的补码：
\(11...11(-x)...(-x)(-x)(-x) + 1\)
，反码末尾的
\(1\)
将重新变为
\(0\)
，而最低位
\(0\)
将重新变为
\(1\)
，其他位不变，仍然是取反的状态，此时如果将
\(-n\)
的补码与
\(n\)
原码进行按位与的运算（
\(n\)
与
\(-n\)
的原码只有符号位的不同），由于除符号位、最低位
\(1\)
及其后面的位
\(0\)
，其他位都进行了取反，这些位将被赋值为
0 & 1
或
1 & 0
，即
\(0\)
，而符号位也会赋值为
0 & 1
，只剩最低位
\(1\)
及其后面的位
\(0\)
分别被赋值为
1 & 1
和
0 & 0
，即
\(1\)
和
\(0\)
，最后结果为
\(lowbit(n)\)
（或者说
\(lowbit(-n)\)
）

那么
\(n\)
的反码、补码呢？上文所述的只是负数的反码与补码的计算方式，实际上，正数的原码、反码、补码都是一样的（对于原码、反码、补码，本博文已经进行了必要的解释，但如果你对其感兴趣，想知道其详细解释，可参考这篇博文：
二进制｜原码、反码、补码
）

众所周知，
C++
中，数字是使用补码表示的，因此，我们可以将
\(n\)
的补码视为
\(n\)
的原码，在
C++
中进行运算。于是，我们得到了
\(n\)
的原码和
\(-n\)
的补码

上文中，我们提到了将
\(n\)
的原码和
\(-n\)
的补码进行按位与运算可以得到
\(lowbit(n)\)
和
\(lowbit(-n)\)
，现在我们使用
\(n\)
的补码作为其原码（毕竟是一样的），可以得到：

\[lowbit(n) = -n ＆ n
\]

显然
\(n\)
是负数也不会造成影响

于是我们成功地得到了
lowbit
的计算公式，将算法的时间复杂度降低为
\(O(1)\)
，并简化了代码：

#define lowbit(n) (-n & n)

由于使用宏定义，一定要记得打括号，位运算的优先级是最低的

lowbit
的应用

lowbit
的应用也有很多，例如树状数组等，如果你对这方面感兴趣，不妨订阅一下我的博客，我以后会发布更多有趣且有用的算法知识