移位运算的求余机制详解
问题描述
移位运算: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(" - 使用位运算进行性能优化时要权衡可读性");
}
}
最终答案:
- 5 << 35:会进行35 % 32 = 3的模运算,结果等于5 << 3 = 40
- 5 << -2:会取-2的低5位,即(-2) & 0x1F = 30,结果等于5 << 30 = 1342177280
理解这些机制有助于正确使用位运算,避免常见的陷阱和错误。