Bit Hacks

前言
术语
位运算符
两个数求平均
两个数交换
只出现一次的数字
写在最后

前言

先讲个笑话：这世界上有 10 种人，懂二进制的人和不懂二进制的人
众所周知，计算机数据采用二进制形式存储，分别用高低电平表示 1 和 0。
在位运算之前，咱们先说原码、反码、补码。

术语

原码
设机器字长为 n，那么一个数的原码就是一个 n 位的二进制数。计算机为了区分正负数，将最高位设为符号位，正数为 0，负数为 1。
正数的原码、反码、补码都一样。
0 分正0和负0，原码和反码有两个。
反码
对于负数，反码是在原码的基础上，保持符号位不变，其他位按位取反。
补码
同样只针对负数，补码是在反码的基础上加1。
补码还可以这么理解，符号位不变，从低位开始，直到遇到第一个 1，除该位和符号位以外的其他位都按位取反。
但这样其实有个问题，负 0 的补码表示形式变了。就当作个加深理解的非正式技巧把。
其实还有个移码，符号位取反的补码，不是你们家亲戚。

为什么会有原码、反码、补码?
由于原码分正负，在计算机设计之初，如果考虑让计算机辨别原码符号位进行运算，则会出现加法和减法，基础电路设计会变得十分复杂。大佬们就想办法把符号位一起纳入运算，减法变换成加法。

反码的出现把硬件问题给转到软件上来，轻松解决了原码的减法问题。
以机器字长 n=8 为例，计算十进制的表达式：1-1=0
1 - 1 = 1 + (-1) = [0000 0001]_原 + [1000 0001]_原= [0000 0001]_反 + [1111 1110]_反 = [1111 1111]_反 = [1000 0000]_原 = -0

但是反码还是有个问题，0 会有两种表达形式：正0和负0.
于是补码出现了，解决了 0 的符号及两个编码问题
1 - 1 = 1 + (-1) = [0000 0001]_原 + [1000 0001]_原 = [0000 0001]_补 + [1111 1111]_补 = [0000 0000]_补=[0000 0000]_原

0 的问题解决了，空出来的负0在补码里成了-2ⁿ
(-1) + (-127) = [1000 0001]_原 + [1111 1111]_原 = [1111 1111]_补 + [1000 0001]_补 = [1000 0000]_补
所以补码在原码和反码的基础上表达范围还多出一个最小值 [-2ⁿ, 2ⁿ-1]

位运算符

& 按位与，注意与逻辑与或非的区别
| 按位或
^ 按位异或
~ 取反
<< 左移，低位补 0，高位溢出则舍弃高位
>> 右移，负数高位补 1，非负数高位补 0
>>> 无符号右移，高位补0
C 语言没有无符号右移，可用 ((unsigned int)x)>>1 来实现

两个数求平均

方法一，直接将两数相加再除 2：

// java
public static int average(int x, int y) {
    return (x + y) >> 1;
}

但是，这种方法有个弊端，在实际编程语言中表示数的范围有上限，可能发生整数溢出：

// java
public static void main(String... args) {
    int result = average(Integer.MAX_VALUE, Integer.MAX_VALUE);
    System.out.printf("result=%d%n", result); // result=-1

    int result = average(Integer.MIN_VALUE, Integer.MIN_VALUE);
    System.out.printf("result=%d%n", result); // result=0
}

稍加优化，如果两个数一正一负则直接相加再除 2，否则两数相减、差值除 2、再与被减数相加：

// java
public static int average(int x, int y) {
    if ((Integer.signum(a) * Integer.signum(b)) < 0) {
        return (x + y) >> 1;
    } else {
        return x + ((y - x) >> 1);
    }
}

方法二，预先对两个数分别除 2，同时通过按位与修正低位数字，保证在两个整数都为奇数时，结果仍然正确：

// java
public static int average(int x, int y) {
    return (x >> 1) + (y >> 1) + (x & y & 1);
}

该方法还被申请了专利，已于 2016 年过期。所以该方法又称为 2016 专利法。

方法三，SWAR（SIMD within a register），其中 SIMD - Single Instruction Multiple Data 单指令多数据流，参考 SIMD指令集：

// java
public static int average(int x, int y) {
    return (a & b) + (a ^ b) / 2; // 变体 (a ^ b) + (a & b) * 2
}

两个数交换

方法一，增加临时变量：

// c
void swap(int x, int y)
{
  int temp = x;
  x = y;
  y = temp;
}

这种方法的弊端就是临时变量占用内存开销。

方法二，采用加减法或者乘除法：

// c
// 加减法
void swap(int x, int y)
{
  x += y;
  y = x - y;
  x -= y;
}

// 乘除法
void swap(int x, int y)
{
  x *= y;
  y = x / y;
  x /= y;
}

这种方法的弊端是有溢出风险。

方法三，采用异或：

// c
void swap(int x, int y)
{
  x ^= y;
  y ^= x;
  x ^= x;
}

这种方法的代码看起来甚是清爽，但是暗藏杀机看出来了吗?
异或最大的问题是如果两个值相等，异或为 0。这种方案在x和y相等的情况下失效。当然，解决也很简单，在代码开头加上判断：

// c
void swap(int x, int y)
{
  if(x == y) return;
  x ^= y;
  y ^= x;
  x ^= x;
}

以上三种方法都有一个问题，那就是函数的值传递问题，如果在 main 函数里调用以上的 swap 函数，传递过来的其实是实参的值，swap 函数交换的只是形参，对实参没有任何影响(C 语言、Java 语言都一样)。所以，一般在 C 语言里边交换函数会这么写：

// c
void swap(int *x, int *y)
{
  int temp = *x;
  *x = *y;
  *y = temp;
}

或者这么写:

// c
void swap(int *x,int *y){     
    (*x) ^= (*y) ^= (*x) ^= (*y);     
}  

采用指针传递地址，完美地解决了函数值传递的问题。
还可以采用宏定义：

// c
#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))

当然，还有很多其他方法

只出现一次的数字

这是一道 LeetCode 上的题：
给定一个整型数组，除了一个元素外每个元素均出现两次，找出单独的这个元素。

// java
int singleNumber(int[] nums){  
    int value = 0;  
    for(int i : nums) value ^= i;
    return value;  
}  

如果是 Java 8 还可以这么写:

// java 8 及以上
int singleNumber(int[] nums){
    return Arrays.stream(nums).reduce(0, (x,y)-> x^y);
}

不推荐用 Java 8 的方式，运行速度慢了许多倍。

写在最后

一些位运算资料：

LeetCode的 Bit Manipulation 专题
斯坦福 Sean Eron Anderson 教授收集的位运算技巧 http://graphics.stanford.edu/~seander/bithacks.html
大家可以在他的文章里找茬，10 刀奖励，如果直接捐给慈善的话 20 刀。
《算法心得》（Hacker’s Delight），JDK 里的很多位运算骚操作都来自该书。

目录

前言

术语

位运算符

两个数求平均

两个数交换

只出现一次的数字

写在最后