理解按位操作符

理解按位操作符

2019-07-18

快速了解按位操作符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
System.out.println("<< 左移位运算符：左移时，无论是正数还是负数，低位补 0");
System.out.println("左移运算符可以做这种运算： x << y = x * 2^y");
System.out.println("5\t\t->\t" + Integer.toBinaryString(5));
System.out.println("5<<1\t =\t" + (5<<1));
System.out.println("5<<1\t->\t" + Integer.toBinaryString(5<<1));
System.out.println("-5\t\t->\t" + Integer.toBinaryString(-5));
System.out.println("-5<<2\t =\t" + (-5<<2));
System.out.println("-5<<2\t->\t" + Integer.toBinaryString(-5<<2));

System.out.println("\n>> 右移位运算符：右移时，正数高位补0；负数高位补1。");
System.out.println("5\t\t->\t" + Integer.toBinaryString(5));
System.out.println("5>>1\t =\t" + (5>>1));
System.out.println("5>>1\t->\t" + Integer.toBinaryString(5>>1));
System.out.println("-5\t\t->\t" + Integer.toBinaryString(-5));
System.out.println("-5>>2\t =\t" + (-5>>2));
System.out.println("-5>>2\t->\t" + Integer.toBinaryString(-5>>2));

System.out.println("\n>>> 无符号右移位运算符：右移时，无论正负高位补0。");
System.out.println("5\t\t->\t" + Integer.toBinaryString(5));
System.out.println("5>>>1\t =\t" + (5>>>1));
System.out.println("5>>>1\t->\t" + Integer.toBinaryString(5>>>1));
System.out.println("-5\t\t->\t" + Integer.toBinaryString(-5));
System.out.println("-5>>>2\t =\t" + (-5>>>2));
System.out.println("-5>>>2\t->\t" + Integer.toBinaryString(-5>>>2));

System.out.println("\n& 按位与运算符：二进制中两个同时为1才为1，否则为0。（从低位对齐）");
System.out.println("5\t->\t" + Integer.toBinaryString(5));
System.out.println("3\t->\t" + Integer.toBinaryString(3));
System.out.println("5&3\t =\t" + (5&3));
System.out.println("5&3\t->\t" + Integer.toBinaryString(5&3));


System.out.println("\n| 按位或运算符：二进制中有一个1即为1，否则为0。（从低位对齐）");
System.out.println("5\t->\t" + Integer.toBinaryString(5));
System.out.println("3\t->\t" + Integer.toBinaryString(3));
System.out.println("5|3\t =\t" + (5|3));
System.out.println("5|3\t->\t" + Integer.toBinaryString(5|3));

System.out.println("\n^ 按位异或运算符：二进制两个不同则为1，相同为0。（从低位对齐）");
System.out.println("5\t->\t" + Integer.toBinaryString(5));
System.out.println("3\t->\t" + Integer.toBinaryString(3));
System.out.println("5^3\t =\t" + (5^3));
System.out.println("5^3\t->\t" + Integer.toBinaryString(5^3));

System.out.println("\n~ 按位非运算符：按位取反。（从低位对齐） 由于 ~ 是一元运算符不可以与 = 连用，其他都可以。");
System.out.println("5\t->\t" + Integer.toBinaryString(5));
System.out.println("~5\t =\t" + (~5));
System.out.println("~5\t->\t" + Integer.toBinaryString(~5));

结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
<< 左移位运算符：左移时，无论是正数还是负数，低位补 0
左移运算符可以做这种运算： x << y = x * 2^y
5	->	101
5<<1	 =	10
5<<1	->	1010
-5	->	11111111111111111111111111111011
-5<<2	 =	-20
-5<<2	->	11111111111111111111111111101100

>> 右移位运算符：右移时，正数高位补0；负数高位补1。
5	->	101
5>>1	 =	2
5>>1	->	10
-5	->	11111111111111111111111111111011
-5>>2	 =	-2
-5>>2	->	11111111111111111111111111111110

>>> 无符号右移位运算符：右移时，无论正负高位补0。
5	->	101
5>>>1	 =	2
5>>>1	->	10
-5	->	11111111111111111111111111111011
-5>>>2	 =	1073741822
-5>>>2	->	111111111111111111111111111110

& 按位与运算符：二进制中两个同时为1才为1，否则为0。（从低位对齐）
5	->	101
3	->	11
5&3	 =	1
5&3	->	1

| 按位或运算符：二进制中有一个1即为1，否则为0。（从低位对齐）
5	->	101
3	->	11
5|3	 =	7
5|3	->	111

^ 按位异或运算符：二进制两个不同则为1，相同为0。（从低位对齐）
5	->	101
3	->	11
5^3	 =	6
5^3	->	110

~ 按位非运算符：按位取反。（从低位对齐） 由于 ~ 是一元运算符不可以与 = 连用，其他都可以。
5	->	101
~5	 =	-6
~5	->	11111111111111111111111111111010

基础补充

真值

1 和 -1 的二进制表示：

1
2
+ 00000001 # +1
- 00000001 # -1

原码

计算机只能存储 0 和 1 ，不能存储正负，所以一个数的最高位存放符号，正数为 0，负数为 1，用后面七位来表示真值的绝对值：

1
2
0 0000001 # +1
1 0000001 # -1

由于10000000表示为 -0 ,这个没有意义，所以这个数字被用来表示 -128，所以负数就比整数多一个。

反码

反码的表示方法是：正数不变，负数是在其原码的基础上，符号位不变，其余位取反：

1
2
0 0000001 # +1
1 1111110 # -1

反码实际上是原码和补码之间的过渡码。

补码

补码的作用主要是为了简化运算，将减法变为加法而发明的数学表示法，其表示方法是：正数不变，负数是在其反码的基础上+1：

1
2
0 0000001 # +1
1 1111111 # -1

二进制表示方法：

1
2
3
4
5
6
7
[+1] = [0000 0001]原 
     = [0000 0001]反
     = [0000 0001]补
--------------------
[-1] = [1000 0001]原
     = [1111 1110]反
     = [1111 1111]补

灵活使用

按位与 &

特性：

  1. n & 0 = 0
  2. n & -1 = n

例子：

  1. 判断一个数的奇偶性。

    1
    2
    3
    4
    // 偶数最低位为0，奇数最低位为1
    // condition: n & 1 == 0
    System.out.println(1&1); // 1
    System.out.println(2&1); // 0

  2. 判断一个数是否是2的整数幂。

    1
    2
    3
    4
    // 2的整数幂为 100...  2的整数幂 - 1 为 111...
    // condition: n & (n - 1) == 0
    System.out.println(4 & (4 - 1)); // 0
    System.out.println(5 & (5 - 1)); // 4

按位或 |

特性：

  1. n | 0 = n
  2. n | -1 = -1

按位异或 ^

特性：

  1. n ^ 0 = n
  2. n ^ -1 = ~n
  3. n ^ n = 0

例子：

  1. 不使用临时变量交换两个数。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    //  公式：
    //  如果 a ^ b = c
    //  则有 a ^ c = b, b ^ c = a

    int a = 111;
    int b = 222;

    a ^= b;
    b ^= a;
    a ^= b;

    System.out.println(a); // 222
    System.out.println(b); // 111

  2. 找到数组中出现奇数次的数。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    // 在一个非空数组中找到唯一一个出现奇数次的数
            
    int[] arr = {1,2,3,1,2};
    int res = 0;

    for (int i : arr) {
      res ^= i;
    }

    System.out.println(res);

    // 任何一个数 异或自己都是0，所以可以较快的找到唯一一个奇数。

按位非 ~

特性：

~n = -(n + 1)

左移 <<

1
2
3
4
5
6
7
8
9
10
// 获得 int 型最大值
System.out.println(~(1 << 31));
System.out.println((1 << 31) - 1); // 括号不能去掉，因为 << 运算优先级低

// 获得 int 型最小值
System.out.println(1 << 31);

// n 乘以 2 的 8 次方
System.out.println(5 << 8);
System.out.println(5 * Math.pow(2, 8));

右移 >>

事实上，右移和左移相反， x >> y 表示 x / (2 ^ y) （乘除替换了一下）。

最后

位操作还有很多奇技淫巧，有空时再补充一些。

参考

深入理解按位操作符