Day 6：位运算（异或性质、二进制操作）
📖 一、位运算简介
位运算是计算机底层优化的重要手段，利用二进制操作可以大大提高运算速度。常见的位运算包括：
- 与（&）：
a & b，如果两个二进制位都为1，结果为1，否则为0。 - 或（|）：
a | b，如果两个二进制位中至少有一个为1，结果为1，否则为0。 - 异或（^）：
a ^ b，如果两个二进制位不同，结果为1，否则为0。 - 取反（~）：
~a，按位取反，0变1，1变0。 - 左移（<<）：
a << n，将a的二进制表示向左移动n位，相当于a * 2^n。 - 右移（>>）：
a >> n，将a的二进制表示向右移动n位，相当于a / 2^n（保留符号位）。 - 无符号右移（>>>）：不保留符号位，即高位补
0。
📖 二、只出现一次的数字（Single Number）
🔹 1. 题目描述
给定一个非空整数数组，除了某个数字只出现一次以外，其他数字均出现两次。请找出这个只出现一次的数字。
示例
输入: nums = [4, 1, 2, 1, 2]
输出: 4
🔹 2. 思路与分析
- 利用异或运算
^- 性质1：
a ^ a = 0，任意数与自身异或为0。 - 性质2：
a ^ 0 = a，任意数与0异或仍是自身。 - 性质3：异或满足交换律和结合律，即
a ^ b ^ c = a ^ c ^ b，顺序无关。 - 性质4：
a ^ b ^ b = a，某个数字b出现偶数次，它们会相互抵消。
- 性质1：
因此，将所有数字进行异或操作，所有成对出现的数字都会抵消为 0，最终结果就是那个只出现一次的数字。
🔹 3. 代码实现（只出现一次的数字）
public class SingleNumber {
public int findSingleNumber(int[] nums) {
int result = 0;
for (int num : nums) {
result ^= num; // 利用异或运算找出唯一的数
}
return result;
}
public static void main(String[] args) {
SingleNumber solution = new SingleNumber();
int[] nums = {4, 1, 2, 1, 2};
System.out.println("只出现一次的数字: " + solution.findSingleNumber(nums)); // 输出 4
}
}
🔹 4. 代码讲解
result ^= num：将数组中的所有数字进行异或。- 成对的数字会被消除，只剩下唯一出现一次的数字。
✅ 时间复杂度：O(n)，只需遍历一次数组。
✅ 空间复杂度：O(1)，只使用一个变量存储结果。
📖 三、二进制中 1 的个数（Hamming Weight）
🔹 1. 题目描述
编写一个函数，计算一个整数的二进制表示中 1 的个数。
示例
输入: n = 9 (1001)
输出: 2
🔹 2. 思路与分析
方法 1️⃣：位运算逐位检查
- 每次检查
n的最低位是否为1（n & 1）。 - 右移
n一位（n >>= 1），直到n变为0。
方法 2️⃣：n & (n - 1) 高效算法
- 性质：
n & (n - 1)可以移除n最右边的1，这样1的个数就等于操作n & (n - 1)多少次。
🔹 3. 代码实现（方法 1：逐位检查）
public class HammingWeight {
public int countOnes(int n) {
int count = 0;
while (n != 0) {
count += (n & 1); // 检查最低位是否为1
n >>= 1; // 右移一位
}
return count;
}
public static void main(String[] args) {
HammingWeight solution = new HammingWeight();
int n = 9; // 二进制: 1001
System.out.println("二进制中 1 的个数: " + solution.countOnes(n)); // 输出 2
}
}
🔹 4. 代码实现（方法 2：n & (n - 1)）
public class HammingWeightOptimized {
public int countOnes(int n) {
int count = 0;
while (n != 0) {
n &= (n - 1); // 清除最低位的1
count++;
}
return count;
}
public static void main(String[] args) {
HammingWeightOptimized solution = new HammingWeightOptimized();
int n = 9; // 二进制: 1001
System.out.println("二进制中 1 的个数: " + solution.countOnes(n)); // 输出 2
}
}
🔹 5. 代码讲解
方法 1：
- 时间复杂度 O(log n)，因为
n的二进制长度最多为log n。 - 空间复杂度 O(1)。
方法 2：
- 时间复杂度 O(k)，其中
k是n中1的个数，比 O(log n) 更快。 - 空间复杂度 O(1)。
n & (n - 1) 计算次数等于 1 的个数，比 O(log n) 更快。
📖 四、位运算总结
1. 常用位运算技巧
| 运算 | 作用 |
|---|---|
a & 1 | 判断 a 是否为奇数 |
| `a | (1 << k)` |
a & ~(1 << k) | 将 a 的第 k 位置 0 |
a ^ (1 << k) | 翻转 a 的第 k 位 |
n & (n - 1) | 清除 n 的最低位 1 |
n & (-n) | 获取 n 的最低位 1 |
2. 位运算的常见应用
- 判断奇偶数：
n & 1 == 1（奇数），n & 1 == 0（偶数）。 - 求
n的二进制中1的个数。 - 交换两个数：
a = a ^ b; b = a ^ b; a = a ^ b;（不使用额外空间）。 - 判断
n是否是 2 的幂：n > 0 && (n & (n - 1)) == 0。
🎯 练习建议
- 理解异或运算的性质，练习 "只出现一次的数字"。
- 熟练掌握
n & (n - 1)，用于清除最低位1的优化技巧。 - 多做位运算相关题目，包括位掩码、二进制操作。
