位运算总结

发表于 更新于 分类于 阅读次数：

二进制的一些概念

在二进制数里，最高位 0 表示正数，1 表示负数。

原码

一个正数，按照绝对值大小转换成的二进制数；一个负数按照绝对值大小转换成的二进制数，然后最高位补 1，称为原码。

1
2
 5 的原码是：00000000 00000000 00000000 00000101
-5 的原码是：10000000 00000000 00000000 00000101

反码

正数的反码与原码相同，负数的反码为对该数的原码除符号位外各位取反（即 0 变 1，1 变 0）。

1
2
正数 00000000 00000000 00000000 00000101 的反码还是 00000000 00000000 00000000 00000101
负数 10000000 00000000 00000000 00000101 的反码却是 11111111 11111111 11111111 11111010

补码

正数的补码与原码相同，负数的补码为该数的反码加 1。

负数 10000000 00000000 00000000 00000101 的反码是 11111111 11111111 11111111 11111010，那么补码为：

1
11111111 11111111 11111111 11111010 + 1 = 11111111 11111111 11111111 11111011

位运算基础

基本的位操作符有与、或、异或、取反、左移、右移这 6 种，它们的运算规则如下所示：

符号 描述 运算规则
& 与 两个位都为 1 时，结果才为 1
| 或 两个位只要有一位为 1，结果都为 1
^ 异或 两个位相同为 0，不同为 1
~ 取反 0 变 1，1 变 0
<< 左移 各二进位全部左移若干位，高位丢弃，低位补 0
>> 右移 各二进位全部右移若干位，对无符号数，高位补 0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补 0（逻辑右移）

注意

  1. 在这 6 种操作符，只有 ~ 取反是单目操作符，其它 5 种都是双目操作符。

  2. 位操作只能用于整型数据，对 float 和 double 类型进行位操作会被编译器报错。

  3. 对于移位操作，在微软的 VC6.0 和 VS2008 编译器都是采取算术称位即算术移位操作，算术移位是相对于逻辑移位，它们在左移操作中都一样，低位补 0 即可，但在右移中逻辑移位的高位补 0 而算术移位的高位是补符号位。如下面代码会输出 -4 和 3。

    1
    2
    System.out.println((15) >> 2); // 3
    System.out.println((-15) >> 2); // -4

    15 = 00000000 00000000 00000000 00001111（二进制），右移二位，高位补 0，得到

    00000000 00000000 00000000 00000011 即 3。

    -15 = 11111111 11111111 11111111 11110001（二进制），右移二位，最高位由符号位填充，得到

    11111111 11111111 11111111 11111100 即 -4。

  4. 位操作符的运算优先级比较低，因此应尽量使用括号来确保运算顺序。

  5. 位操作还有一些复合操作符，如 &=、|=、 ^=、<<=、>>=。

常用的位运算技巧

判断奇偶数

一个二进制数 x 的末位为 0 则该数为偶数，为 1 则为奇数，因此可以使用 (x & 1) 的结果来判断 x 的奇偶性，结果为 0，则 x 为偶数，结果为 1，则 x 为奇数。

如要求输出 0 到 10 之间的所有偶数：

1
2
3
4
5
for (int i = 0; i < 10; i++) {
    if ((i & 1) == 0) {
        System.out.println(i);
    }
}

交换两数

1
2
3
4
5
6
7
int a = 10;
int b = 20;
a ^= b;
b ^= a;
a ^= b;
System.out.println("a=" + a); // a=20
System.out.println("b=" + b); // b=10

分析：

第一步，a = a ^ b ①；

第二步，b = b ^ a，把 ① 代入得，b = b ^ (a ^ b)，由于 ^ 满足交换律，所以 b = b ^ b ^ a，根据「一个数和自己异或为 0，而 0 和任何数异或结果还是保持不变」的原理得，b = a ②；

第三步，a = a ^ b，将 ①、② 代入得，a = (a ^ b) ^ a 即 a = b ③。

从 ②、③ 得知，a 和 b 的值已经得到了交换。

变换符号

一个数 x 取反加 1 后就会变成 -x，即正数变为负数，负数变为正数。

1
2
3
4
5
6
int a = -5;
int b = 10;
a = ~a + 1;
b = ~b + 1;
System.out.println("a=" + a); // a=5
System.out.println("b=" + b); // b=-10

分析：

-5 = 11111111 11111111 11111111 11111011（二进制），取反再加 1 后变为：

00000000 00000000 00000000 00000101 = 5

注意：这里负数的取反是包括符号位的，不要和负数的反码混淆。

求绝对值

对于正数，绝对值就是它本身，对于负数，直接取反加 1 就得到正数了，所以先判断一个整数的符号再做处理。对于整数 a，它的最高位为 0 代表正数，为 1 代表负数，我们对 a 右移 31 位得到一个整数 i（i = a >> 31），i 值为 0 代表 a 为正数，为 -1 代表 a 为负数。

1
2
3
4
private int abs(int a) {
    int i = a >> 31;
    return i == 0 ? a : (~a + 1);
}

进一步分析，对于任意整数 a，和 0（32 个 0）异或都保持不变，和 -1（32 个 1）异或相当于取反，所以上面的返回值可以转换为：

1
return i == 0 ? (a ^ i) : ((a ^ i) + 1);

上面返回值再变换下得：

1
return i == 0 ? ((a ^ i) - 0) : ((a ^ i) + 1);

由于 i 的值非 0 即 -1，因此上面返回值可以精简为：

1
return (a ^ i) - i;

通过上面的分析，我们得出求一个整数的绝对值的精简方式，这种方式不需任何判断。

1
2
3
4
private int abs(int a) {
    int i = a >> 31;
    return (a ^ i) - i;
}

位操作与空间压缩

当我们要标记一个布尔型数组的状态为 true|false 时，我们通常的做法是这样的：

1
boolean[] flag = new boolean[100];

由于数组在内存上也是连续分配的一段空间，我们可以「认为」它是一个很长的整数，因此我们仅需用一个长度为 4（100 / 32 + 1）的整型数组即可完成上面的状态标记。

1
int[] b = new int[4]; // 每个 int 值有 32 位，各个位上为 0 代表 false，为 1 代表 true

由于 boolean 占 1 个字节，int 占 4 个字节，因此，用第二种方式所使用的空间仅为第一种的 1/6 左右。

以下是用筛素数法计算 100 以内的素数的示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private void printPrime() {
    int max = 100;
    boolean[] flag = new boolean[max];
    int[] primes = new int[max / 3 + 1];
    int index = 0;
    for (int i = 2; i < max; i++) {
        if (!flag[i]) {
            primes[index++] = i;
            for (int j = i; j < max; j += i) { // 素数的倍数必然不是素数
                flag[j] = true;
            }
        }
    }

    // 输出 100 以内所有素数
    for (int i = 0; i < index; i++) {
        System.out.print(primes[i] + " ");
    }
}
输出：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

如果是用长度为 4 的整型数组 b 来替代 flag 布尔型数组怎么做？两个关键点，第一，如何将一个整数的指定位上置为 1？第二，如何判断一个整数指定位上是 0 还是 1？

将整数 j 指定位上置为 1：

将 1 向左移位后和其相或来达到在指定位上置 1 的效果

1
2
3
4
5
6
7
private void setOne() {
    System.out.println();
    int j = 0;
    j |= (1 << 10);
    System.out.println(Integer.toBinaryString(j));
}
// 输出：10000000000

判断整数 j 指定位上是否为 1：

将 1 向左移位后和原数相与来判断指定位上是 0 还是 1（也可以将原数右移若干位再和 1 相与）

1
2
3
4
5
6
7
8
9
private void isOne() {
    int j = 1 << 10;
    if ((j & (1 << 10)) != 0) {
        System.out.println("指定位上为 1");
    } else {
        System.out.println("指定位上为 0");
    }
}
// 输出：指定位上为 1

再把这种思路扩展到一个整型数组上：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private void setOne2() {
    int max = 40;
    int[] b = new int[max / 32 + 1];
    for (int i = 0; i < max; i += 3) {
        b[i / 32] |= (1 << (i % 32)); // 每 3 个位设置为 1
    }

    for (int i = 0; i < max; i++) {
        if (((b[i / 32] >> i) & 1) == 1) { // 判断是否为 1
            System.out.print("1");
        } else {
            System.out.print("0");
        }
    }
}
// 输出：1001001001001001001001001001001001001001

现在可以将上面的筛素数法改成使用位操作压缩后的筛素数法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private void printPrime2() {
    int max = 100;
    int[] b = new int[max / 32 + 1];
    int[] primes = new int[max / 3 + 1];
    int index = 0;
    for (int i = 2; i < max; i++) {
        int x = b[i / 32] >> (i % 32); // 通过右移，逐位判断是 0 还是 1
        if ((x & 1) == 0) {
            primes[index++] = i;
            for (int j = i; j < max; j += i) {
                b[j / 32] |= (1 << (j % 32)); // 将指定位上设置为 1
            }
        }
    }
    // 输出 100 以内所有素数
    for (int i = 0; i < index; i++) {
        System.out.print(primes[i] + " ");
    }
}
输出：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97