成都移动网站建设_鄂州网站开发_seo关键词优化的技巧和方法_网站关键词快速排名优化

时间:2025/9/25 15:52:53来源：https://blog.csdn.net/T_Y_F_/article/details/143996022 浏览次数:0次

`n & (n - 1)` 将 `n` 的最低位 1 清零的原理详解

n & (n - 1) 是位运算中一个经典的技巧，用于快速清除一个整数 n 的二进制表示中最低位的 1。这一操作常用于以下场景：

统计一个数的二进制中有多少个 1。
判断一个数是否是 2 的幂。
处理位操作相关的算法。

以下从二进制表示和运算过程的角度，详细解释其原理。

1. 核心概念

二进制表示：
- 一个数 n 的二进制表示由若干个 0 和 1 组成。
- 最低位的 1 指的是从右往左第一个出现的 1。
n - 1 的特点：
- 在二进制中，n - 1 会将从最低位的 1 开始，包括该位及其右侧的所有位反转。
按位与（&）操作：
- 只有对应位都为 1 时，结果才为 1，否则为 0。

2. 原理分析

假设一个整数 `n` 的二进制形式：

$\text{高位} 1 0 \cdots 1 0 \cdots \text{低位} 1)$

这里，n 的最低位 1 在某个位置（从右往左数），例如在第 $k$ 位。

(1) `n - 1` 的二进制变化

当我们计算 n - 1 时，从最低位的 1 开始，以下变化发生：

最低位的 1 变为 0。
该位右侧的所有位反转（0 变 1，1 变 0）。
该位左侧的位保持不变。

示例 1：

假设 n = 12，二进制为 1100：

n - 1 = 11，二进制为 1011。

示例 2：

假设 n = 18，二进制为 10010：

n - 1 = 17，二进制为 10001。

(2) `n & (n - 1)` 的结果

对 n 和 n - 1 进行按位与操作：

最低位的 1 被清除（变为 0）：
- 因为在 n - 1 中，最低位的 1 被变为 0，按位与结果必然为 0。
其他位保持不变：
- 在 n 中，最低位 1 左边的高位没有被影响。
- 在 n - 1 中，最低位 1 右边的位全部变为 1，所以按位与的结果为 0。

示例 1：

n = 12，二进制为 1100，n - 1 = 1011：
$KaTeX parse error: \hline valid only within array environment$
结果为 8，二进制为 1000，最低位的 1 已被清除。

示例 2：

n = 18，二进制为 10010，n - 1 = 10001：
$KaTeX parse error: \hline valid only within array environment$
结果为 16，二进制为 10000，最低位的 1 已被清除。

3. 数学证明

设 n 的最低位 1 出现在第 $k$ 位，即：
$\cdot 2^{k} + 2^{k-1} + \cdots + 2^{0}$
其中，x 表示第 $k + 1$ 位及其左边的高位。

n - 1 的变化：
- $2^{k}$ 的值变为 $0$ 。
- $2^{k-1} + \cdots + 2^{0}$ 的值被反转。
因此：
$\cdot 2^{k} - 1$
按位与操作：
- 按位与只保留了 $\cdot 2^{k}$ 部分，即高位部分。
- 最低位的 $1$ 消失，其余低位变为 $0$ 。
结果为：
$\& (n - 1) = x \cdot 2^{k}$

这证明了最低位的 1 被清除。

4. 实际应用场景

4.1 判断一个数是否是 2 的幂

原理：如果一个数是 2 的幂，它的二进制表示中只有一个 1。
条件：n > 0 && (n & (n - 1)) == 0

示例代码：

public class PowerOfTwo {public static boolean isPowerOfTwo(int n) {return n > 0 && (n & (n - 1)) == 0;}public static void main(String[] args) {System.out.println(isPowerOfTwo(16)); // 输出 trueSystem.out.println(isPowerOfTwo(18)); // 输出 false}
}

4.2 统计二进制中 1 的个数

原理：每次执行 n & (n - 1)，清除一个最低位的 1，直到 n 变为 0。
时间复杂度：执行次数等于 1 的个数，平均为 $O(\log n)$ 。

示例代码：

public class CountOnes {public static int countOnes(int n) {int count = 0;while (n != 0) {n &= (n - 1); // 清除最低位的 1count++;}return count;}public static void main(String[] args) {System.out.println(countOnes(15)); // 输出 4（1111）System.out.println(countOnes(18)); // 输出 2（10010）}
}