Java基础
位运算

位运算

字节、字、位、比特

1位 = 1比特， 1字节 = 8位，1字=2字节， 1Byte=8bit 1B = 8bit， 1KB = 1024B

位：计算机最小存储单位，简记为b，也成为比特bit，计算机中用0和1来表示数据，一个0或1就代表1位。

比特（bit）：也是二进制数字中的位，信息量的最小单位。

字节（Byte）：计算存储容量的计量单位，一个字节等于八位。习惯上用B表示。

字：计算机进行数据处理时，一次存取、加工和传送的数据长度称为字（word），一个字通常由一个或多个（一般是字节的整数位）字节构成。如286微机的字由2个字节组成；486微机的字由4个字节组成。

位移运算

Java中有三个位移运算：

  • <<：左移：正数高位丢弃，低位补0，负数符号位保持不变
  • >>：右移：正数低位丢弃，高位补0；负数高位补1
  • >>>：无符号右移：低位丢弃，高位补0，符号位也会跟着一起移动
1
2
3
4
5
6
System.out.println(2 << 1);     // 4
System.out.println(2 >> 1);     // 1
System.out.println(2 >>> 1);    // 1
System.out.println(-2 << 1);    // -4
System.out.println(-2 >> 1);    // -1
System.out.println(-2 >>> 1);   // 2147483647

原码、反码、补码

原码，利用二进制中的第一位来表示符号位，0表示正数，1表示负数。

反码，正数的反码和原码一样，负数的反码就是在原码的基础上符号位保持不变，其他位取反。

补码，补码是为了解决反码的问题，正数的补码和原码、反码一样，负数的补码就是反码+1。

十进制 原码 反码 补码
2 0000 0010 0000 0010 0000 0010
-2 1000 0010 1111 1101 1111 1110

计算机在进行运算时是不会去管符号位的，计算时用到的时补码，让符号位也参与运算，最后将运算得到的结果再转换成源码即可。

负数位移运算

-2用原码表示为10000000 00000000 00000000 00000010

-2用反码表示为11111111 11111111 11111111 11111101

-2用补码表示为11111111 11111111 11111111 11111110

-2 << 1，表示-2的补码左移一位后为11111111 11111111 11111111 11111100，该补码对应的反码为

1
2
3
11111111 11111111 11111111 11111100
- 1
= 11111111 11111111 11111111 11111011

该反码对应的原码为：符号位不变，其他位取反，为10000000 00000000 00000000 00000100，表示-4。所以-2 << 1 = -4。

-2 >> 1，表示-2的补码右移一位后（高位补1）为11111111 11111111 11111111 11111111，该补码对应的反码为

1
2
3
11111111 11111111 11111111 11111111
- 1
= 11111111 11111111 11111111 11111110

该反码对应的原码为：符号位不变，其他位取反，为10000000 00000000 00000000 00000001，表示-1。所以-2 >> 1 = -1。

无符号右移

在对补码进行移动时，符号位是固定不动的，而无符号右移是指在进行移动时，符号位也会跟着一起移动。比如-2 >>> 1。

-2用原码表示为10000000 00000000 00000000 00000010

-2用反码表示为11111111 11111111 11111111 11111101

-2用补码表示为11111111 11111111 11111111 11111110

-2的补码右移1位为：01111111 11111111 11111111 11111111

右移后的补码对应的反码、原码为：01111111 11111111 11111111 11111111 ，因为现在的符号位为0表示正数，正数的原、反、补码都相同，所以-2 >>> 1 = 2147483647

~（取反运算）

1
2
3
4
5：    00000000 00000000 00000000 00000101
~5：   11111111 11111111 11111111 11111010 // 补码形式
       11111111 11111111 11111111 11111001 // 反码
       10000000 00000000 00000000 00000110 // 原码

基本应用

交换内容
1
2
3
4
5
void swap(int a, int b) {
    a ^= b;
    b ^= a;
    a ^= b;
}
判断奇偶
1
(a & 1) == 0
求平均数
1
2
3
int average(int x, int y) {
    return (x & y) + ((x ^ y) >> 1);
}
获取大于等于i的最接近的2的幂
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 获取数据二进制的最高位，低位全部置0
public static int highestOneBit(int i) {
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    return i - (i >>> 1);
}

highestOneBit((number - 1) << 1)
    
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}