移位运算的求余机制详解

问题描述

移位运算:5 << 35,会首先进行35 % 32的求余运算吗?如果是这样,那么5 << -2的结果是多少呢?

详细解答

核心概念

Java中的移位运算确实会进行模运算(求余运算)来处理移位位数,但具体规则取决于操作数的类型:

  • int类型:移位位数对32取模(因为int是32位)
  • long类型:移位位数对64取模(因为long是64位)

基础验证

1. 正数移位的模运算

public class ShiftOperationBasics {
    public static void main(String[] args) {
        System.out.println("=== 正数移位的模运算 ===");

        int value = 5;

        // 正常移位
        System.out.println("5 << 2 = " + (value << 2));        // 20
        System.out.println("5 << 3 = " + (value << 3));        // 40

        // 大于32的移位 - 会进行模32运算
        System.out.println("5 << 35 = " + (value << 35));      // 等同于 5 << (35 % 32) = 5 << 3 = 40
        System.out.println("35 % 32 = " + (35 % 32));          // 3

        // 验证等价性
        int shift35 = value << 35;
        int shift3 = value << 3;
        System.out.println("5 << 35 == 5 << 3: " + (shift35 == shift3));  // true

        // 更多验证
        System.out.println("5 << 64 = " + (value << 64));      // 等同于 5 << (64 % 32) = 5 << 0 = 5
        System.out.println("5 << 100 = " + (value << 100));    // 等同于 5 << (100 % 32) = 5 << 4 = 80

        demonstrateModuloLogic();
    }

    public static void demonstrateModuloLogic() {
        System.out.println("\n=== 模运算逻辑演示 ===");

        int[] shifts = {32, 33, 64, 65, 100};
        int value = 1;

        for (int shift : shifts) {
            int actualShift = shift % 32;
            int result = value << shift;
            int expectedResult = value << actualShift;

            System.out.printf("%d << %d = %d (等同于 %d << %d = %d)%n", 
                             value, shift, result, value, actualShift, expectedResult);
        }
    }
}

2. 负数移位的处理

public class NegativeShiftAnalysis {
    public static void main(String[] args) {
        System.out.println("=== 负数移位分析 ===");

        int value = 5;

        // 问题中的例子:5 << -2
        System.out.println("5 << -2 = " + (value << -2));

        // 分析过程
        System.out.println("-2的二进制表示: " + Integer.toBinaryString(-2));
        System.out.println("-2 % 32 = " + (-2 % 32));

        // Java中负数的模运算结果仍为负数
        int effectiveShift = (-2) % 32;
        System.out.println("有效移位位数: " + effectiveShift);

        // 但是移位运算会把负数当作很大的正数处理
        // -2的二进制在int中是:11111111111111111111111111111110
        // 只取低5位(因为2^5=32),即:11110 = 30
        int actualShift = (-2) & 0x1F;  // 0x1F = 31,取低5位
        System.out.println("实际移位位数(取低5位): " + actualShift);
        System.out.println("5 << 30 = " + (value << 30));

        // 验证
        System.out.println("验证:5 << -2 == 5 << 30: " + ((value << -2) == (value << 30)));

        analyzeNegativeShiftMechanism();
    }

    public static void analyzeNegativeShiftMechanism() {
        System.out.println("\n=== 负数移位机制详解 ===");

        int value = 1;
        int[] negativeShifts = {-1, -2, -3, -32, -33};

        for (int shift : negativeShifts) {
            // Java移位运算的实际处理方式
            int maskedShift = shift & 0x1F;  // 取低5位
            int result = value << shift;
            int expectedResult = value << maskedShift;

            System.out.printf("1 << %d = %d", shift, result);
            System.out.printf(" (等同于 1 << %d = %d)", maskedShift, expectedResult);
            System.out.printf(" [%d & 0x1F = %d]%n", shift, maskedShift);
        }

        // 展示位运算细节
        demonstrateBitMasking();
    }

    public static void demonstrateBitMasking() {
        System.out.println("\n=== 位掩码细节 ===");

        int[] values = {-2, -1, 30, 31, 32, 33};

        for (int value : values) {
            int masked = value & 0x1F;
            System.out.printf("%-3d的二进制: %s", value, 
                             String.format("%32s", Integer.toBinaryString(value)).replace(' ', '0'));
            System.out.printf(" & 0x1F = %2d%n", masked);
        }
    }
}

深入机制分析

1. int和long的差异

public class IntVsLongShift {
    public static void main(String[] args) {
        System.out.println("=== int vs long 移位差异 ===");

        // int类型移位(模32)
        int intValue = 5;
        System.out.println("int类型移位:");
        System.out.println("5 << 35 = " + (intValue << 35));    // 模32
        System.out.println("35 % 32 = " + (35 % 32));

        // long类型移位(模64)
        long longValue = 5L;
        System.out.println("\nlong类型移位:");
        System.out.println("5L << 35 = " + (longValue << 35));  // 不模64,因为35 < 64
        System.out.println("5L << 65 = " + (longValue << 65));  // 模64,等同于 5L << 1
        System.out.println("65 % 64 = " + (65 % 64));

        // 验证long类型的掩码机制
        demonstrateLongShiftMask();
    }

    public static void demonstrateLongShiftMask() {
        System.out.println("\n=== long类型掩码机制 ===");

        long value = 1L;
        int[] shifts = {63, 64, 65, 128, 129};

        for (int shift : shifts) {
            // long类型移位使用低6位(因为2^6=64)
            int maskedShift = shift & 0x3F;  // 0x3F = 63
            long result = value << shift;
            long expectedResult = value << maskedShift;

            System.out.printf("1L << %d = %d", shift, result);
            System.out.printf(" (等同于 1L << %d = %d)", maskedShift, expectedResult);
            System.out.printf(" [%d & 0x3F = %d]%n", shift, maskedShift);
        }
    }
}

2. 右移位运算

public class RightShiftAnalysis {
    public static void main(String[] args) {
        System.out.println("=== 右移位运算分析 ===");

        int positiveValue = 80;   // 正数
        int negativeValue = -80;  // 负数

        // 算术右移(>>)
        System.out.println("=== 算术右移(>>)===");
        System.out.println("80 >> 2 = " + (positiveValue >> 2));       // 20
        System.out.println("-80 >> 2 = " + (negativeValue >> 2));      // -20

        // 逻辑右移(>>>)
        System.out.println("\n=== 逻辑右移(>>>)===");
        System.out.println("80 >>> 2 = " + (positiveValue >>> 2));     // 20
        System.out.println("-80 >>> 2 = " + (negativeValue >>> 2));    // 很大的正数

        // 大移位数的右移
        System.out.println("\n=== 大移位数的右移 ===");
        System.out.println("80 >> 35 = " + (positiveValue >> 35));     // 等同于 80 >> 3
        System.out.println("-80 >> 35 = " + (negativeValue >> 35));    // 等同于 -80 >> 3

        // 负移位数的右移
        System.out.println("\n=== 负移位数的右移 ===");
        System.out.println("80 >> -2 = " + (positiveValue >> -2));     // 等同于 80 >> 30
        System.out.println("-80 >> -2 = " + (negativeValue >> -2));    // 等同于 -80 >> 30

        explainRightShiftMechanism();
    }

    public static void explainRightShiftMechanism() {
        System.out.println("\n=== 右移机制解释 ===");

        int value = -80;
        System.out.println("-80的二进制: " + Integer.toBinaryString(value));

        // 算术右移保持符号位
        for (int i = 1; i <= 4; i++) {
            int result = value >> i;
            System.out.printf("-80 >> %d = %d (二进制: %s)%n", 
                             i, result, Integer.toBinaryString(result));
        }

        System.out.println();

        // 逻辑右移用0填充
        for (int i = 1; i <= 4; i++) {
            int result = value >>> i;
            System.out.printf("-80 >>> %d = %d (二进制: %s)%n", 
                             i, result, Integer.toBinaryString(result));
        }
    }
}

实际应用示例

1. 位操作优化

public class BitOperationOptimization {
    public static void main(String[] args) {
        System.out.println("=== 位操作优化应用 ===");

        // 快速乘除法
        demonstrateFastArithmetic();

        // 位掩码操作
        demonstrateBitMasking();

        // 循环移位
        demonstrateRotation();
    }

    public static void demonstrateFastArithmetic() {
        System.out.println("1. 快速乘除法:");

        int value = 15;

        // 乘以2的幂次
        System.out.println("15 * 8 = " + (value * 8) + " vs 15 << 3 = " + (value << 3));
        System.out.println("15 * 16 = " + (value * 16) + " vs 15 << 4 = " + (value << 4));

        // 除以2的幂次
        value = 80;
        System.out.println("80 / 4 = " + (value / 4) + " vs 80 >> 2 = " + (value >> 2));
        System.out.println("80 / 8 = " + (value / 8) + " vs 80 >> 3 = " + (value >> 3));

        // 注意:负数除法和右移的差异
        value = -80;
        System.out.println("-80 / 4 = " + (value / 4) + " vs -80 >> 2 = " + (value >> 2));
    }

    public static void demonstrateBitMasking() {
        System.out.println("\n2. 位掩码操作:");

        // 提取特定位
        int rgb = 0xFF5722;  // 橙色的RGB值

        int red = (rgb >> 16) & 0xFF;
        int green = (rgb >> 8) & 0xFF;
        int blue = rgb & 0xFF;

        System.out.printf("RGB(0x%06X) -> R:%d, G:%d, B:%d%n", rgb, red, green, blue);

        // 构造RGB值
        int newRgb = (red << 16) | (green << 8) | blue;
        System.out.printf("重构RGB: 0x%06X%n", newRgb);
    }

    public static void demonstrateRotation() {
        System.out.println("\n3. 循环移位:");

        int value = 0b11110000111100001111000011110000;
        System.out.println("原始值: " + Integer.toBinaryString(value));

        // 左循环移位
        int leftRotated = rotateLeft(value, 4);
        System.out.println("左循环4位: " + Integer.toBinaryString(leftRotated));

        // 右循环移位
        int rightRotated = rotateRight(value, 4);
        System.out.println("右循环4位: " + Integer.toBinaryString(rightRotated));
    }

    public static int rotateLeft(int value, int distance) {
        // 循环左移:高位移出的部分移到低位
        return (value << distance) | (value >>> (32 - distance));
    }

    public static int rotateRight(int value, int distance) {
        // 循环右移:低位移出的部分移到高位
        return (value >>> distance) | (value << (32 - distance));
    }
}

2. 实际问题解决

public class PracticalProblems {
    public static void main(String[] args) {
        System.out.println("=== 实际问题解决 ===");

        // 问题1:判断数字是否为2的幂
        testPowerOfTwo();

        // 问题2:计算整数的二进制中1的个数
        testBitCount();

        // 问题3:交换两个数字(不使用临时变量)
        testBitSwap();
    }

    public static void testPowerOfTwo() {
        System.out.println("1. 判断是否为2的幂:");

        int[] numbers = {1, 2, 3, 4, 8, 15, 16, 32};

        for (int num : numbers) {
            // 2的幂的特点:二进制中只有一个1
            // n & (n-1) == 0 且 n > 0
            boolean isPowerOfTwo = (num > 0) && ((num & (num - 1)) == 0);
            System.out.printf("%d 是2的幂: %b (二进制: %s)%n", 
                             num, isPowerOfTwo, Integer.toBinaryString(num));
        }
    }

    public static void testBitCount() {
        System.out.println("\n2. 计算二进制中1的个数:");

        int[] numbers = {7, 15, 255, -1};

        for (int num : numbers) {
            int count = countBits(num);
            int javaCount = Integer.bitCount(num);
            System.out.printf("%d 的二进制中有 %d 个1 (Java内置方法: %d)%n", 
                             num, count, javaCount);
        }
    }

    public static int countBits(int n) {
        int count = 0;
        while (n != 0) {
            count++;
            n &= (n - 1);  // 清除最低位的1
        }
        return count;
    }

    public static void testBitSwap() {
        System.out.println("\n3. 位运算交换数字:");

        int a = 15, b = 25;
        System.out.printf("交换前: a = %d, b = %d%n", a, b);

        // 使用异或交换(不需要临时变量)
        a ^= b;  // a = a ^ b
        b ^= a;  // b = b ^ (a ^ b) = a
        a ^= b;  // a = (a ^ b) ^ a = b

        System.out.printf("交换后: a = %d, b = %d%n", a, b);

        // 注意:这种方法在a和b是同一个变量时会出错
        System.out.println("警告:当a和b指向同一变量时,异或交换会导致值变为0");
    }
}

常见陷阱和误区

public class CommonMistakes {
    public static void main(String[] args) {
        System.out.println("=== 常见陷阱和误区 ===");

        // 陷阱1:移位溢出
        trapOverflow();

        // 陷阱2:符号扩展
        trapSignExtension();

        // 陷阱3:移位优先级
        trapOperatorPrecedence();
    }

    public static void trapOverflow() {
        System.out.println("陷阱1:移位溢出");

        int maxInt = Integer.MAX_VALUE;
        System.out.println("Integer.MAX_VALUE = " + maxInt);
        System.out.println("MAX_VALUE << 1 = " + (maxInt << 1));  // 溢出变成负数

        // 大移位数导致意外结果
        int small = 1;
        System.out.println("1 << 31 = " + (small << 31));        // Integer.MIN_VALUE(负数)
        System.out.println("1 << 32 = " + (small << 32));        // 等同于 1 << 0 = 1
    }

    public static void trapSignExtension() {
        System.out.println("\n陷阱2:符号扩展");

        byte b = -1;
        System.out.println("byte -1 的值: " + b);

        // byte提升为int时会符号扩展
        int promoted = b;
        System.out.println("提升为int: " + promoted);
        System.out.println("二进制表示: " + Integer.toBinaryString(promoted));

        // 移位时的符号扩展
        System.out.println("(-1) >> 1 = " + (promoted >> 1));   // 算术右移
        System.out.println("(-1) >>> 1 = " + (promoted >>> 1)); // 逻辑右移
    }

    public static void trapOperatorPrecedence() {
        System.out.println("\n陷阱3:运算符优先级");

        int a = 4, b = 2;

        // 错误:移位运算符优先级低于加法
        System.out.println("a + b << 1 = " + (a + b << 1));     // (a + b) << 1 = 6 << 1 = 12
        System.out.println("a + (b << 1) = " + (a + (b << 1))); // a + (b << 1) = 4 + 4 = 8

        // 比较运算符优先级也高于移位
        boolean result1 = a << 1 > b;     // (a << 1) > b
        boolean result2 = a < b << 1;     // a < (b << 1)

        System.out.println("(4 << 1) > 2 = " + result1);        // 8 > 2 = true
        System.out.println("4 < (2 << 1) = " + result2);        // 4 < 4 = false
    }
}

总结

关键点回顾

public class Summary {
    public static void main(String[] args) {
        System.out.println("=== 移位运算总结 ===");

        // 1. 模运算规则
        System.out.println("1. 模运算规则:");
        System.out.println("   int类型: 移位数 & 0x1F (模32)");
        System.out.println("   long类型: 移位数 & 0x3F (模64)");

        // 2. 回答原问题
        System.out.println("\n2. 原问题答案:");
        System.out.println("   5 << 35 = " + (5 << 35) + " (等同于 5 << 3)");
        System.out.println("   5 << -2 = " + (5 << -2) + " (等同于 5 << 30)");

        // 3. 验证计算过程
        System.out.println("\n3. 计算过程:");
        System.out.println("   35 & 0x1F = " + (35 & 0x1F));
        System.out.println("   (-2) & 0x1F = " + ((-2) & 0x1F));

        // 4. 实用建议
        System.out.println("\n4. 实用建议:");
        System.out.println("   - 避免移位数超过数据类型位数");
        System.out.println("   - 注意负数的符号扩展");
        System.out.println("   - 小心运算符优先级");
        System.out.println("   - 使用位运算进行性能优化时要权衡可读性");
    }
}

最终答案

  1. 5 << 35:会进行35 % 32 = 3的模运算,结果等于5 << 3 = 40
  2. 5 << -2:会取-2的低5位,即(-2) & 0x1F = 30,结果等于5 << 30 = 1342177280

理解这些机制有助于正确使用位运算,避免常见的陷阱和错误。

powered by Gitbook© 2025 编外计划 | 最后修改: 2025-07-28 18:05:38

results matching ""

    No results matching ""