一些位运算的操作技巧

[kailbin]

Java 里面的位运算操作符有 与& 、或|、非~、异或^、左移<<、右移>>、无符号右移>>>

• 与&
  两个操作数同位相比，同1得1，否则得0
• 或|
  两个操作数同位相比，同0得0，否则得1
• 非~
  操作数，每位取反
• 异或^
  两个操作数同位相比，不同得1，相同得0
• 左移<<
  二进制位，低位向高位移动，低位补0
• 右移>>
  二进制位，高位向低位移动，高位补0
• 无符号右移>>>
  二进制位，高位向低位移动，高位正数补0、负数补1

左移乘2，右移除2

依次类推，左移2位乘4（*2*2）、左移3位乘8（*2*2*2）...

System.out.println(10 >> 1); // 5 （10 / 2 = 5）
System.out.println(10 << 1); // 20 (10 * 2 = 20)
System.out.println(-12 >> 2); // -3 (-12 / 4 = -3)
System.out.println(-13 << 3); // -52 (-13 * 4 = -52)

与运算计算奇数偶数

一个数的二进制位最低一位，如果是1则为奇数，如果是0则为偶数；数字1的二进制位，高位都是0，最低位是1；与1进行与运算&，结果高位都会变成0，最低位如果是奇数则1（同1得1），偶数则0（否则得0）

System.out.println((10 & 1) == 0); // true
System.out.println((11 & 1) == 0); // false
System.out.println((-10 & 1) == 0); // true
System.out.println((-11 & 1) == 0); // false

计算int类型的二进制表示形式

通过以上 右移除2 和 计算奇数偶数 的特性，可以使用以下方式算出一个整数的二进制形式：

public static String toBit(byte num) {
    return toBit(num, 8);
}

public static String toBit(int num, int size) {
    StringBuilder buf = new StringBuilder();
    for (int length = size - 1; length >= 0; length--) {
        buf.append((num >> length) & 1);
    }
    return buf.toString();
}

size的大小必须能够表示num的数字大小，例子:

System.out.println(toBit((byte) 1, 3)); // 001
System.out.println(toBit((byte) 2, 3)); // 010

异或运算的一些特性

1. a ^ 0 = a （任何数字和0异或 等于本身）
2. a ^ a = 0 （自己和自己异或 等于0）
3. a ^ b = b ^ a （满足交换律）
4. a ^ b ^ a = b （根据1、2、3的特性，a^b^a=a^a^b=0^b=b）
5. a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c (结合律，通过3和得出这条结论)
6. d = a ^ b ^ c → a = d ^ b ^ c
7. a ^ -1 = -a - 1

通过异或运算交换两个数

根据 异或运算的一些特性，不引用第三个变量也可以交换两个变量

int a = 1; // 0001
int b = 2; // 0010

a = b ^ a; // 临时变量
b = b ^ a; // b ^ a = b ^ (b ^ a) = 0 ^ a = a
a = a ^ b; // a ^ b = (b^a) ^ (b^(b^a))=a^a^b^b^b=b

Java位运算原理及使用讲解

判断两个数是否一个正数一个负数

( x ^ y ) < 0 // 同号小于0，异号则大于0

负数最高位是1正数0，两个同类型的数字相比，实际上比的还是最高位，一正一负异或得1，还是负数，小于0

计算绝对值

• 如果是负数 右移 31位 为 -1
• 如果是正数 右移 31位 为 0
• 任何数x与0异或 还是x
• 任何数x与-1异或为 -x-1
  根据以上特性，可以计算绝对值的方法如下：

public static int abs(int x) {
    return (x ^ (x >> 31)) - (x >> 31); //or: (x+y)^y
}

如果是正数，x >> 31 为 0，x ^ 0 还是x，则以上公式变为 x^0-0=x-0=x；

如果是负数，x >> 31 为 -1，x ^ -1为-x-1，则以上公式变为 (-x-1)-(-1)=-x；

非运算的特性

• -1 取非为 0 (~-1 == 0)
• 0 取非为 -1 (~0 == -1)

取消分支预判

题目是对数组中大于等于128的数字进行求和，大家发现，如果数组是有序的情况加，计算起来会比无序的情况下快很多，原因是分支带来了一定的性能损耗，原文 why is it faster to process a sorted array than an unsorted array

有人给出了以下解决方案，

int t = (data[index] - 128) >> 31;  // s1
sum += ~t & data[index];  // s2

s1取遍历到的每个数据减128，如果比128大相减后为正数，否则为负数，正数右移31位为0，负数为-1，则 t如果是0则大于或等于128，-1则小于128；通过s1可判断出data[index]是否大于等于128

0 & x = 0、-1 & x = x，则data[index]如果大于128，t为0，~t为-1，-1 & data[index] = data[index]

深入理解CPU的分支预测(Branch Prediction)模型

拓展阅读

• 斯坦福计算机系Bit Twiddling Hacks
• BitHacks--位操作技巧
• 位运算有什么奇技淫巧？