哈尔滨网站制作费用网上营销

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 出现偶数次，它们会相互抵消。

因此，将所有数字进行异或操作，所有成对出现的数字都会抵消为 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️⃣：位运算逐位检查

1. 每次检查 n 的最低位是否为 1（n & 1）。
2. 右移 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); // 检查最低位是否为1n >>= 1; // 右移一位}return count;}public static void main(String[] args) {HammingWeight solution = new HammingWeight();int n = 9; // 二进制: 1001System.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); // 清除最低位的1count++;}return count;}public static void main(String[] args) {HammingWeightOptimized solution = new HammingWeightOptimized();int n = 9; // 二进制: 1001System.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. 位运算的常见应用

1. 判断奇偶数：n & 1 == 1（奇数），n & 1 == 0（偶数）。
2. 求 n 的二进制中 1 的个数。
3. 交换两个数：a = a ^ b; b = a ^ b; a = a ^ b;（不使用额外空间）。
4. 判断 n 是否是 2 的幂：n > 0 && (n & (n - 1)) == 0。

---

🎯 练习建议

1. 理解异或运算的性质，练习 "只出现一次的数字"。
2. 熟练掌握 n & (n - 1)，用于清除最低位 1 的优化技巧。
3. 多做位运算相关题目，包括位掩码、二进制操作。