你好

位运算以及补码重点

[toc]

ℹ️前言

在leetcode算法open in new window中我提到了很多关于位运算的技巧，进行了一次总结

🎈乘以 2 的幂

x = x << 1; // x = x * 2
x = x << 6; // x = x * 64

对于两个数a，b，计算a 和 b 的中间值，如果计算a+b除以2，可能会出现a+b溢出，所以你可以：

var c = ((b - a) >> 2) + a

🎈除以 2 的幂

x = x >> 1; // x = x / 2
x = x >> 3; // x = x / 8

🎈交换没有临时变量的整数

a ^= b; // int temp = b
b ^= a; // b = a
a ^= b; // a = temp

image-20220925161607882

🎈增量/减量（较慢但有利于混淆）

i = -~i; // i++
i = ~-i; // i--

推断：println(~-2)

  • 先得到 -2 的原码：10000000 00000000 00000000 00000010
  • 再得到 -2 的反码：11111111 11111111 11111111 11111101
  • 再得到 -2 的补码：11111111 11111111 11111111 11111110
  • 补码求反：00000000 00000000 00000000 00000001

注意这个补码求反是所有位数都求反，所以结果是(2--)==1

image-20220925161741820

🎈标志翻转

i = ~i + 1; // or
i = (i ^ -1) + 1; // i = -i

🎈如果除数是 2 的幂，则进行模运算

x = 131 & (4 - 1); // x = 131 % 4

🎈检查整数是偶数还是奇数

(i & 1) == 0; // (i % 2) == 0

🎈相等检查

(a^b) == 0; // a == b

🎈绝对值

x < 0 ? -x : x; // abs(x)
(x ^ (x >> 31)) - (x >> 31) // abs(x)

🎈等号检查（两个整数都是 pos 或 neg）

a ^ b >= 0; // a * b > 0

🎈圆角、天花板、地板

(x + 0.5) >> 0; // round(x)
(x + 1) >> 0; // ceil(x)
x >> 0; // floor(x)

💡Java中的二进制补充

必背

  1. 二进制最高位是符号位（🐶旋转90度）
  2. 0 是表示正数，1 是表示负数
  3. 正数的原码、反码、补码都一样
  4. $$负数的反码 = 符号位不变，其他位取反$$
  5. $$负数的补码 = 它的反码 + 1$$
  6. 0 的反码、补码都是0
  7. java没有无符号数，换言之，Java中的数都是有符号的
  8. 当计算机运算时，都是以补码的方式来运算的
  9. 当我们看运算结果的时候，要看他的原码

所以当我们计算一个位运算的时候，进行了下面几步（注意是32位）：

public static void main(String[] args) {
    System.out.println(2&3);
}
  • 先得到 2 的补码 ==>
    • 先得到 2 的原码 ：00000000 00000000 00000000 00000010
    • 再得到 2 的补码 ：00000000 00000000 00000000 00000010
  • 再得到 3 的补码 ==>
    • 先得到 3 的原码 ：00000000 00000000 00000000 00000011
    • 再得到 3 的补码 ：00000000 00000000 00000000 00000011
  • 按位与 ==>
    • 00000000 00000000 00000000 00000010
    • 00000000 00000000 00000000 00000011
    • 00000000 00000000 00000000 00000010 （运算后的补码还需要转化为原码 ==> 符号位是0，说明是正数，推出原码 == 补码）
  • 结果00000000 00000000 00000000 00000010转为十进制：2

java逻辑右移

⚡上面的都是算术运算符，但是java也是有无符号右移的，运算规则是：低位溢出，高位补0）

⚠️ 特别说明：Java是没有 <<< 符号（无符号左移），只有 >>> 无符号右移

比较：

  • >>右移运算符，有符号。右边超出截掉，左边补上符号位
  • >>>右移运算符，无符号，左边补0

案例：

byte a=~127;
System.out.println(a);
a=(byte)(a>>>2);
System.out.println(a);

结果如下：

-128
-32

分析：

首先,~127的二进制数为10000000,(~127是取反运算）

但是JAVA在对不足32位的数(byte,char,short)进行移位运算时候,都会先转成int(32位)，所以此时a为11111111111111111111111110000000

移位之后,(00)111111111111111111111111100000

但是你在此a=(byte)(a>>>2); 强制转成byte型,将对结果进行截断

此时a为11100000,就是32了