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

【算法通关村 Day11】位运算

article 2025/2/28 22:16:20

位运算青铜挑战

位运算规则

位运算是直接对整数的二进制位进行操作的运算。在 Java 中，常用的位运算符有：&（与）、|（或）、^（异或）、~（取反）、<<（左移）、>>（算术右移）和>>>（逻辑右移）。

1. 按位与（`&`）

规则：只有两个相应的位都为1时，结果才为1，否则为0。

示例：

int a = 5;  // 二进制：0101
int b = 3;  // 二进制：0011
int result = a & b;  // 结果：0001 (即1)
System.out.println(result);  // 输出 1

2. 按位或（`|`）

规则：只要两个相应的位中有一个为1，结果就为1，否则为0。
示例：

int a = 5;  // 二进制：0101
int b = 3;  // 二进制：0011
int result = a | b;  // 结果：0111 (即7)
System.out.println(result);  // 输出 7

3. 按位异或（`^`）

规则：当两个相应的位相异（一个为0，另一个为1）时，结果为1；否则为0。

示例：

int a = 5;  // 二进制：0101
int b = 3;  // 二进制：0011
int result = a ^ b;  // 结果：0110 (即6)
System.out.println(result);  // 输出 6

4. 按位取反（`~`）

规则：反转二进制中的每一位，0变成1，1变成0。

示例：

int a = 5;  // 二进制：0101
int result = ~a;  // 结果：1010（对于32位系统，表示 -6）
System.out.println(result);  // 输出 -6

5. 左移（`<<`）

规则：将所有的位向左移动指定的位数，右边用0填充。每左移一位，相当于乘以2。

示例：

int a = 5;  // 二进制：0101
int result = a << 1;  // 结果：1010 (即10)
System.out.println(result);  // 输出 10

6. 算术右移（`>>`）

规则：将所有的位向右移动指定的位数，对于正数，左边补0，对于负数，左边补1（保留符号位）。

示例：

int a = 5;  // 二进制：0101
int result = a >> 1;  // 结果：0010 (即2)
System.out.println(result);  // 输出 2

int b = -5;  // 二进制：11111111111111111111111111111011
int result2 = b >> 1;  // 结果：11111111111111111111111111111101 (即-3)
System.out.println(result2);  // 输出 -3

7. 逻辑右移（`>>>`）

规则：将所有的位向右移动指定的位数，无论符号位如何，左边都补0。

示例：

int a = -5;  // 二进制：11111111111111111111111111111011
int result = a >>> 1;  // 结果：01111111111111111111111111111101 (即2147483645)
System.out.println(result);  // 输出 2147483645

&、| 和 ^ 运算符用于按位操作，针对两个整数的每一位。
~ 运算符用于取反，将一个整数的每一位反转。
<<、>> 和 >>> 运算符用于位移操作，其中 << 是左移，>> 是算术右移，>>> 是逻辑右移。

位运算技巧

1. 判断一个数是否是2的幂

原理：2的幂在二进制表示下只有一个1位，x & (x - 1) 的结果为0，表示x是2的幂。

示例：

int x = 8;
boolean isPowerOfTwo = (x & (x - 1)) == 0;
System.out.println(isPowerOfTwo);  // 输出 true

2. 交换两个数

原理：使用异或操作可以在不使用临时变量的情况下交换两个数。

示例：

int a = 5, b = 3;
a = a ^ b;
b = a ^ b;  // b = (a ^ b) ^ b = a
a = a ^ b;  // a = (a ^ b) ^ a = b
System.out.println("a: " + a + ", b: " + b);  // 输出 a: 3, b: 5

3. 提取二进制中最低的1位

原理：x & -x 可以提取二进制中最低的1位，常用于求解汉明重量或二进制最右边的1的位置。

示例：

int x = 12;  // 二进制：1100
int lowestBit = x & -x;  // 结果：4 (二进制：0100)
System.out.println(lowestBit);  // 输出 4

4. 清除最低的1位

原理：x & (x - 1) 会清除二进制中最低的1位。

示例：

int x = 12;  // 二进制：1100
x = x & (x - 1);  // 结果：8 (二进制：1000)
System.out.println(x);  // 输出 8

5. 检测某一位是否为1

原理：(x & (1 << n)) != 0 可以检查x的第n位是否为1。

示例：

int x = 5;  // 二进制：0101
int n = 2;  // 检查第2位（从0开始数）
boolean isBitSet = (x & (1 << n)) != 0;
System.out.println(isBitSet);  // 输出 true，因为第2位是1

位运算白银挑战

位运算高频算法题

1 位移的妙用

1.1 位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。详见leetcode191

public class HammingWeight {

    /**
     * 计算一个无符号整数的二进制表示中 '1' 的个数（汉明重量）。
     *
     * @param n 无符号整数
     * @return 二进制表示中 '1' 的个数
     */
    public int hammingWeight(int n) {
        int count = 0;
        // 循环直到 n 变为 0
        while (n != 0) {
            //  n & 1  等价于判断 n 的最低位是否为1。  
            //  如果是1，则count++
            count += (n & 1);

            // 无符号右移一位。  
            // 关键点：使用无符号右移（>>>）来确保最高位填充0，而不是符号位。
            // 这对于处理负数非常重要，因为Java中的整数是带符号的。
            n >>>= 1;  // 无符号右移一位，相当于除以2
        }
        return count;
    }

    public static void main(String[] args) {
        HammingWeight hw = new HammingWeight();

        // 示例用法
        int num1 = 11; // 二进制表示: 00000000000000000000000000001011
        int weight1 = hw.hammingWeight(num1);
        System.out.println("数字 " + num1 + " 的汉明重量是: " + weight1);  // 输出: 3

        int num2 = -3; // 二进制表示 (补码): 11111111111111111111111111111101  (32个1 - 2个1，所以2^32 - 3的二进制表示中1的个数)
        int weight2 = hw.hammingWeight(num2);
        System.out.println("数字 " + num2 + " 的汉明重量是: " + weight2);  // 输出: 31

        int num3 = 0;
        int weight3 = hw.hammingWeight(num3);
        System.out.println("数字 " + num3 + " 的汉明重量是: " + weight3); // 输出: 0
    }
}

1.2 比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数，返回一个长度为 n + 1 的数组 ans 作为答案。

public class CountingBits {

    /**
     * 计算 0 到 n (包含 n) 中每个数字的二进制表示中 '1' 的个数。
     *
     * @param n 整数 n
     * @return 一个长度为 n + 1 的数组，包含每个数字的汉明重量。
     */
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];  // 创建一个数组来存储结果，大小为 n + 1

        for (int i = 0; i <= n; i++) {
            ans[i] = hammingWeight(i); // 对每个数字 i，计算其汉明重量并存储在数组中
        }

        return ans;
    }

    // 辅助函数：计算一个数的汉明重量 (和之前hammingWeight函数一样)
    private int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            count += (n & 1);
            n >>>= 1;
        }
        return count;
    }

    // 更高效的动态规划方法
    public int[] countBitsDP(int n) {
        int[] ans = new int[n + 1];
        ans[0] = 0;  // 0 的汉明重量是 0

        for (int i = 1; i <= n; i++) {
            // i / 2  等价于 i >> 1 (右移一位)。  
            // i & 1 等价于 i % 2 (判断奇偶性)
            ans[i] = ans[i >> 1] + (i & 1);
        }

        return ans;
    }

    public static void main(String[] args) {
        CountingBits cb = new CountingBits();

        // 示例用法
        int n = 5;
        int[] result1 = cb.countBits(n);  // 使用基本方法
        System.out.print("数字 " + n + " 的 countBits 结果: ");
        for (int val : result1) {
            System.out.print(val + " ");
        }
        System.out.println(); // 输出: 0 1 1 2 1 2

        int[] result2 = cb.countBitsDP(n); // 使用动态规划方法
        System.out.print("数字 " + n + " 的 countBitsDP 结果: ");
        for (int val : result2) {
            System.out.print(val + " ");
        }
        System.out.println(); // 输出: 0 1 1 2 1 2
    }
}

1.3 颠倒无符号整数

颠倒给定的 32 位无符号整数的二进制位。详见leetcode190

public class ReverseBits {

    /**
     * 颠倒给定的 32 位无符号整数的二进制位。
     *
     * @param n 要颠倒位的无符号整数
     * @return 位颠倒后的无符号整数
     */
    public int reverseBits(int n) {
        int result = 0;

        // 遍历所有 32 位
        for (int i = 0; i < 32; i++) {
            // 1. 将 result 左移一位，为下一个最低有效位腾出空间
            result <<= 1;

            // 2. 获取 n 的最低有效位
            int bit = n & 1;

            // 3. 将 n 的最低有效位设置到 result 的最低有效位
            result |= bit;

            // 4. 将 n 右移一位，以便在下一次迭代中处理下一个位
            n >>>= 1;  // 使用无符号右移
        }

        return result;
    }

    // 优化后的方法，使用位运算和缓存
    private final int[] cache = new int[256]; // 缓存 8 位反转的结果

    public int reverseBitsOptimized(int n) {
        // 检查缓存是否已经初始化。只在第一次使用时初始化。
        if (cache[1] == 0) { // 假设 cache 未初始化时，cache[1] 为 0
            for (int i = 0; i < 256; i++) {
                cache[i] = reverseByte(i);
            }
        }

        // 将 32 位整数分解为 4 个 8 位字节，并使用缓存反转每个字节，然后组合结果
        return (cache[n & 0xff] << 24) |
               (cache[(n >>> 8) & 0xff] << 16) |
               (cache[(n >>> 16) & 0xff] << 8) |
               (cache[(n >>> 24) & 0xff]);
    }

    // 反转一个字节的位
    private int reverseByte(int b) {
        int result = 0;
        for (int i = 0; i < 8; i++) {
            result = (result << 1) | (b & 1);
            b >>>= 1;
        }
        return result;
    }


    public static void main(String[] args) {
        ReverseBits rb = new ReverseBits();

        // 示例用法
        int num = 43261596; // 00000010100101000001111010011100
        int reversedNum = rb.reverseBits(num);
        System.out.println("数字 " + num + " 的反转后的结果: " + reversedNum); // 输出: 964176192  (00111001011000010000101000000000)

        int optimizedReversedNum = rb.reverseBitsOptimized(num);
        System.out.println("数字 " + num + " 的优化反转后的结果: " + optimizedReversedNum); // 输出: 964176192
    }
}

public int reverseBits(int n) {
    int power = 31;
    int reversed = 0;
    while(power>=0){
        reversed += (n&1) << power;
        n = n >>> 1;
        power--;
    } 
    return reversed;
}

2 通过位运算实现四则运算

2.1 两整数之和

给你两个整数 a 和 b ，不使用运算符 + 和 - ，计算并返回两整数之和。详见leetcode371

public class SumWithoutPlus {

    /**
     * 不使用 + 和 - 运算符，计算两个整数的和。
     *
     * @param a 第一个整数
     * @param b 第二个整数
     * @return 两个整数的和
     */
    public int getSum(int a, int b) {
        // 使用位运算来模拟加法
        while (b != 0) {
            // 1. 计算进位 (carry): a & b
            //    & 运算符计算 a 和 b 中都为 1 的位。
            //    这些位需要产生进位。
            int carry = a & b;

            // 2. 计算没有进位的和 (sum): a ^ b
            //    ^ 运算符计算 a 和 b 中不同位的异或结果。
            //    这给出了没有考虑进位的和。
            a = a ^ b;

            // 3. 将进位左移一位，并将其分配给 b
            //    进位需要添加到下一位。
            //    左移一位等同于乘以 2，因为它将进位移动到下一位。
            b = carry << 1;
        }

        // 当进位为 0 时，a 包含最终的和
        return a;
    }

    public static void main(String[] args) {
        SumWithoutPlus swp = new SumWithoutPlus();

        // 示例用法
        int num1 = 1;
        int num2 = 2;
        int sum = swp.getSum(num1, num2);
        System.out.println(num1 + " + " + num2 + " = " + sum); // 输出: 1 + 2 = 3

        int num3 = -2;
        int num4 = 3;
        int sum2 = swp.getSum(num3, num4);
        System.out.println(num3 + " + " + num4 + " = " + sum2); // 输出: -2 + 3 = 1
    }
}

2.2 通过位运算实现乘法

递归乘法。写一个递归函数，不使用 * 运算符，实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。详见leetcode08.05

public class RecursiveMultiply {

    /**
     * 使用递归方法，不使用 * 运算符，计算两个正整数的乘积。
     *
     * @param a 第一个正整数
     * @param b 第二个正整数
     * @return 两个正整数的乘积
     */
    public int recursiveMultiply(int a, int b) {
        // 确保 a 始终是较小的数字，以减少递归调用次数
        if (a > b) {
            return recursiveMultiply(b, a);
        }

        // 基本情况：如果 a 为 0，则乘积为 0
        if (a == 0) {
            return 0;
        }

        // 基本情况：如果 a 为 1，则乘积为 b
        if (a == 1) {
            return b;
        }

        // 递归步骤：
        //   如果 a 是偶数：a * b = (a / 2) * 2 * b = (a / 2) * (b + b)
        //   如果 a 是奇数：a * b = (a - 1) * b + b
        if (a % 2 == 0) { // a 是偶数
            return recursiveMultiply(a / 2, b + b);  // 优化： b+b 可以替换为 b << 1
        } else { // a 是奇数
            return recursiveMultiply(a - 1, b) + b;
        }
    }


    // 更优化的版本，使用位运算
    public int recursiveMultiplyOptimized(int a, int b) {
        if (a > b) {
            return recursiveMultiplyOptimized(b, a);
        }

        if (a == 0) {
            return 0;
        }

        if (a == 1) {
            return b;
        }

        if ((a & 1) == 0) { // a 是偶数
            return recursiveMultiplyOptimized(a >> 1, b << 1);
        } else { // a 是奇数
            return recursiveMultiplyOptimized(a - 1, b) + b;
        }
    }


    public static void main(String[] args) {
        RecursiveMultiply rm = new RecursiveMultiply();

        // 示例用法
        int num1 = 3;
        int num2 = 5;
        int product = rm.recursiveMultiply(num1, num2);
        System.out.println(num1 + " * " + num2 + " = " + product); // 输出: 3 * 5 = 15

        int num3 = 7;
        int num4 = 8;
        int product2 = rm.recursiveMultiply(num3, num4);
        System.out.println(num3 + " * " + num4 + " = " + product2); // 输出: 7 * 8 = 56

        int num5 = 10;
        int num6 = 12;
        int product3 = rm.recursiveMultiplyOptimized(num5, num6);
        System.out.println(num5 + " * " + num6 + " = " + product3); // 输出: 10 * 12 = 120

    }
}

查看全文

http://www.kler.cn/a/565095.html