这是一个关于二进制位运算与数论性质的有趣证明。

1. 定义与背景

设一个二进制数 $x$ 的末尾有 $k$ 个连续的 $0$。以你的例子 $x = (1010100)_2$ 为例，它的末尾有 $2$ 个 $0$，即 $k=2$。 你提到的 “$100$” 实际上是指 $2^k$（即 $1$ 后面跟着 $k$ 个 $0$）。

2. 证明：为什么 $2^k$ 是 $x$ 的因子

在二进制表示法中，任何一个正整数 $x$ 都可以写成： $x = \sum_{i=0}^{n} a_i \cdot 2^i$ 其中 $a_i \in {0, 1}$。

如果 $x$ 的末尾有 $k$ 个 $0$，这意味着从第 $0$ 位到第 $k-1$ 位的所有系数 $a_i$ 都为 $0$。 因此，$x$ 可以表示为： $x = a_n 2^n + a_{n-1} 2^{n-1} + \dots + a_k 2^k$ 我们可以提取公因子 $2^k$： $x = 2^k \cdot (a_n 2^{n-k} + a_{n-1} 2^{n-k-1} + \dots + a_k 2^0)$

因为括号内的部分是一个整数，所以 $2^k$ 必然是 $x$ 的因子。 在你的例子中，$x = (1010100)_2$： $x = 1 \cdot 2^6 + 0 \cdot 2^5 + 1 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2$ $x = 2^2 \cdot (1 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0)$ $x = 4 \cdot (16 + 4 + 1) = 4 \cdot 21 = 84$ 这里 $2^2 = (100)_2 = 4$，显然 $4$ 是 $84$ 的因子。

3. 证明：为什么它是 2 的幂次方的“最大”因子

要证明 $2^k$ 是最大的 $2$ 的幂因子，只需要证明 $x / 2^k$ 是一个奇数。

观察提取公因子后的括号部分： $y = a_n 2^{n-k} + a_{n-1} 2^{n-k-1} + \dots + a_k$ 由于 $k$ 是从右往左数第一个出现 $1$ 的位置，所以 $a_k$ 必定等于 $1$。 那么： $y = (a_n 2^{n-k} + \dots) + 1$ 在二进制中，除了最后一项 $a_k \cdot 2^0 = 1$ 以外，前面的所有项都是 $2$ 的倍数（偶数）。 偶数 + 奇数 = 奇数。 既然 $y$ 是奇数，它就不再含有任何因子 $2$。 因此，$2^k$ 就是 $x$ 所能整除的 $2$ 的最高次幂。

4. 计算机科学中的应用：lowbit

在算法中，这个性质被广泛应用于树状数组（Binary Indexed Tree）。 我们使用 x & -x 来快速获取这个“$1$ 后面跟着 $k$ 个 $0$”的数值。

原理简述： 1. 设 $x$ 的二进制为 ...100...0（$k$ 个 $0$）。 2. -x 在计算机中以补码存储，等于 ~x + 1。 3. ~x 会把末尾的 $0$ 变 $1$，最后的 $1$ 变 $0$。 4. ~x + 1 会让末尾的 $1$ 重新进位，直到遇到原本第一个 $1$ 的位置。 5. 结果是 x & -x 只有原本最低位的 $1$ 被保留，其余位全变 $0$。

C++ 示例代码：

int get_lowbit(int x) {
    return x & -x;
}

// 对于 x = 84 (二进制 1010100) // get_lowbit(84) 将返回 4 (二进制 100)

总结

对于任何二进制数，其末尾的 $0$ 决定了它是 $2$ 的多少次方倍。 $x$ 的二进制末尾有几个 $0$，它就能被 $2$ 的几次方整除。 “$1$ 后面跟着这些 $0$”所代表的数，就是 $x$ 最大的 $2$ 的幂因子。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com