有趣的位运算

编程中逻辑运算是再常见不过了，针对二进制的逻辑运算是位运算（bitwise-operations），使用位运算经常可以实现一些非常geek的操作。

取反（NOT）

1变0，0变1

    NOT 0111
      = 1000

取反可以用于翻转，比如对于一个无符号的8位整数，表示范围是0-255

    a = 100, 则~a = 155，也就是255-100=155

符号取反，正数变成负数，负数变成正数

    a = 7, ~a+1 = -7

本来求补码符号位不参与，但是这里取反+1正数正好变成负数的补码表示

与（AND）

两个都是1则取1，否则为0

      0101 (decimal 5)
  AND 0011 (decimal 3)
   =  0001 (decimal 1)

按位与经常用作标志位或者掩码

因为二进制的最后一个为0是偶数，1为奇数，所以

if (0 == a & 1) {
  //偶数
}

ip地址掩码确定网络号
255.255.255.0 & 192.168.1.3

或（OR）

只要有1则为1，否则为0

   0001 (decimal 1)
OR 0010 (decimal 2)
 = 0011 (decimal 3)

按位或可以用于组合标志位，比如提取分量后用来组合

异或 （XOR）

相同则为0，不同则为1

    0101 (decimal 5)
XOR 0011 (decimal 3)
  = 0110 (decimal 6)

最经典就是不使用第三个变量来交换a,b的值

a = 5; b=3;
a ^= b
b = a ^ b
a ^= b

一个无序数组有一个唯一的数，其它都是2个数，如何找出唯一的那个数？如[1,2,3,2,3]
因为x ^ x = 0, x ^ 0 = x, x ^ y ^ z = x ^ (y ^ z),所以依次把每个数xor运算最后就可以得到唯一的一个数

移位 （SHIFT）

左移一位表示乘 2，右移一个表示 除2

  00010111 (decimal +23) LEFT-SHIFT
= 00101110 (decimal +46)

  10010111 (decimal −105) RIGHT-SHIFT
= 11001011 (decimal −53)

可以用来进行2、4、8的整除

位运算应用例子

1. 判断n是否是2的幂

n & (n-1) == 0

2. 高低字节交换

对于一个无符号的16位数

unsigned short a = 12345;
a = a >> 8 | (a & 0x00FF) << 8); //14640

3. 颠倒给定的 32 位无符号整数的二进制位

00000010100101000001111010011100 => 00111001011110000010100101000000

function reverseBits(n: number): number {
    let ret = 0
    //对于有符号不能用n>0判断
	for(let i = 0; i < 32 && n != 0; i++) {
        ret |= (n & 1) << (31-i)
        n >>>= 1
    }
    return ret >>> 0
};

4. 无符号整数中位数为1的个数 (汉明重量)

function hammingWeight(n: number): number {
    let ret = 0;
    while (n) {
        n &= n - 1;
        ret++;
    }
    return ret;
}

n & n-1 每次会把n的最后一位1变成0
更有o(1)的算法可以体会位运算的强大

function hammingWeight(n: number): number {
    n = n - ((n >>> 1) & 0x55555555);
    n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
    n = (n + (n >>> 4)) & 0x0f0f0f0f;
    n = n + (n >>> 8);
    n = n + (n >>> 16);
    return n & 0x3f;
 }