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 有什么作用呢？最主要的作用是用于维护树状数组，该算法可能会有一点点抽象，大家感兴趣可以参阅这篇博客：树状数组 | 维护区间和 别看了还没写好 。现在，我会给大家介绍几个 lowbit 的小用法。

1. 求奇偶性

我们都知道，在需要求一个数 $a$ 的奇偶性时可以使用 (bool)a & 1 ，返回 true 为奇数， 否则为偶数。但如果你觉得这种方法不够装逼的话，我们还可以使用 a & -a == 1 语句，同样是返回 true 为奇数，否则为偶数。

2. 关于 $2$ 的幂相关判断

有点关于二进制的题目非常友善，会提出譬如 “判断 $n$ 的二进制01串表示中存在几个数字 $1$” “判断数字 $n$ 是否是 $2$ 的幂” 这样有趣的判断。这个时候，我们可以动动脑筋，尝试用 lowbit 以使用 $O(1)$ 的复杂度解决。上面两个例子分别可以使用函数

int getone(int n) {
    int ans = 0;
    while (n) n -= n & -n, ans++;
    return ans;
}

和宏定义 #define pow_of_two(n) (n & -n == n) 解决

如果你对这方面感兴趣，不妨订阅一下我的博客，我以后会分享更多有趣且有用的算法知识