C++ 中的 lowbit

技术分享 2年前 (2024-07-12) 0 999+

关注

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) 
由于使用宏定义，一定要记得打括号，位运算的优先级是最低的