当前位置：首页 > article >正文

[特殊字符] 蓝桥杯 Java B 组之位运算（异或性质、二进制操作）

article 2025/2/25 2:03:38

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️⃣：位运算逐位检查

每次检查 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`