盘点一下那些好玩的位运算

发表于 | 分类于 |

程序中的所有数在计算机内存中都是以二进制的形式储存的，位运算即对数据的二进制直接操作，具有效率高的特点。在Java中，位运算有<<(左移),>>(右移),>>>(无符号右移),&(且),|(或),^(异或),~(取反),其中~(按位取反)是单目操作，其他都为双目运算。因为直接的位运算极其高效，通过合理的应用位运算能极大的提高程序的效率。

求两个正整数的平均数

计算两个整数的平均数，正常的做法是(a + b) / 2，但是考虑到如果a + b > Integer.MAX_VALUE的情况，可能会出现溢出的情况，数值的溢出不会抛出异常信息，但得到的结果却不是我们想要的，譬如: (Integer.MAX_VALUE + 100) / 2的结果为-1073741774。这个时候，位运算就能派上用场了。所谓求平均，就是两个对象共有的部分加它们各自有的部分之和的一半，这么一来位运算的思路就很明显了：

1
2
3
public static int average(int a, int b) {
    return (a & b) + ((a ^ b) >>> 1);
}

即先通过&操作获取两数的共有的部分，使用^操作获取它们各自有的部分之和，通过>>>无符号右移一位达到取一半的作用，它们之和就是这两数的平均数了。如果追求精度，可以把>>> 1操作换成/ 2.0,修改其返回类型为double.

不使用临时变量的交换

先上代码：

1
2
3
4
5
6
7
int a = 3;  // 0011
int b = 5;  // 0101
System.out.println("a=" + a + ", b=" + b);  // a=3, b=5
a ^= b; // a = a^b = 0011^0101 = 0110;
b ^= a; // b = b^a = 0101^0110 = 0011;
a ^= b; // a = a^b = 0110^0011 = 0101;
System.out.println("a=" + a + ", b=" + b);  // a=5, b=3

^异或运算是去两个位数上不同的情况为结果为1,否则为0,即两个相同的数异或操作结果是0,譬如1^1=0,0^0=0,0^1=1,1^0=1.第一步a=a^b是将a、b两数的不同位数提取出来,暂存于a,即a=0011^0101; // 0110,第二步操作b = b^(a);可以看成是将a的值赋值给b，即将第一步和第二步合起来其实是b=a^b^b,这里的b在这里参与了两次异或运算，由于x^x=0,同样，第三步和第一步合并的操作为：a=(a^b)^(b),注意这里的第二个b其实已经成了之前的a，也就是说基于第二步，第三步和第一步的合并操作其实是：a=a^b^a，即就是将之前的b值赋值给了a.

找出成对数组中不成对的元素

参见找出成对数组中不成对的元素。

计算绝对值

在JDK的Math工具类中，Math.abs(a)的实现是return (a<0) ? -a:a;,遇到a=Integer.MIN_VALUE的情况时，其返回结果为-2147483648,这显然不是我们期待的值，为啥呢？这得追溯到计算机存储数值的编码方式，其中有原码、反码和补码。int类型有32bit,太长，我们采用byte类型举例。
对于有符号位，二进制的最高位(bit)表示的是符号位，即0表示正数，1表示负数，譬如2的原码为0000 0010,-2的原码为1000 0010,那如果2+(-2)的原码计算式什么呢：

1
0000 0010 + 1000 0010 = 1000 0100

结果为-4？！这明显不对，这时候就需要引入反码来解决这种情况。反码编码方式规定：正数的反码与原码相同，负数则符号位不变，其余位按位取反。使用反码计算2+(-2)：

1
0000 0010 + 1111 1101 = 1111 1111

反码表示的1111 1111是什么，转为原码为1000 0000,就是-0,-0是什么，0的表示不是0000 0000吗，同样是0怎么能有两个编码，然后为了解决这种情况，诞生了补码。补码的规定为：负数的补码就是对反码加一，而正数的补码不变，即正数的原码、反码、补码都是一样的。那-0的补码表示就成了1 0000 0000这个溢出位咋整——直接舍去，即0000 0000.为什么不把2+(-2)写成2-2，因为计算机只有加法，没有减法，这也是为什么会设计补码这种编码的一个原因。
再回到Math.abs(a),因为JDK的实现只是在原数上添加了一个符号位。Integer.MIN_VALUE在java中的定义是：

1
@Native public static final int MIN_VALUE = 0x80000000;

即它的补码表示：

1
1000 0000  0000 0000  0000 0000  0000 0000  // Integer.toBinaryString(Integer.MIN_VALUE)

如果取绝对值，则符号位变为0,然后后面位数取反：

1
0111 1111  1111 1111  1111 1111  1111 1111

再加一：

1
1000 0000  0000 0000  0000 0000  0000 0000

又回到Integer.MIN_VALUE本身了。其实也能理解，毕竟int类型的存值区间为-2147483648 ~ 2147483647,而 -2147483648的绝对值已经超过了int的存储范围。
回到使用位运算计算绝对值,根据之前对取绝对值的方法描述，使用long类型存储绝对值，这样就能获取到正确的绝对值了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * Math.abs(a)原方法修正
 */
public static long mathAbs(int a) {
    return (a<0) ? -(long)a : (long)a;
}
public static long abs(int a) {
    long x = a >> 31;
    return (a^x) - x;
}
public static void main(String[] args) {
    System.out.println(abs(Integer.MIN_VALUE)); // 2147483648
    System.out.println(mathAbs(Integer.MIN_VALUE)); // 2147483648
}

统计整数的二进制表示中1的个数

方法一较为暴力，直接从低位开始统计。第二种不知哪位大神写的，不明觉厉，性能上稍比第一种好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int countbit1(int a) {
    int count = 0;
    while(a > 0) {
        count ++;
        a &= a - 1;
    }
    return count;
}

public static int countbit2(int x) {
    x = x - ((x >> 1) & 0x5555_5555);
    x = (x & 0x3333_3333) + ((x >> 2) & 0x3333_3333);
    x = (x + (x >> 4)) & 0x0f0f_0f0f; 
    x = x + (x >> 8);
    x = x + (x >> 16); 
    return x & 0x0000_003f;
}