位运算

位运算在算法中很有用，速度可以比四则运算快很多。

在学习位运算之前应该知道十进制如何转二进制，二进制如何转十进制。这里说明下简单的计算方式

  • 十进制 33 可以看成是 32 + 1 ，并且 33 应该是六位二进制的（因为 33 近似 32，而 32 是 2 的五次方，所以是六位），那么 十进制 33 就是 100001 ，只要是 2 的次方，那么就是 1否则都为 0
  • 那么二进制 100001 同理，首位是 2^5 ，末位是 2^0 ，相加得出 33

左移 <<

  1. 10 << 1 // -> 20

左移就是将二进制全部往左移动，10 在二进制中表示为 1010 ，左移一位后变成 10100 ，转换为十进制也就是 20，所以基本可以把左移看成以下公式 a * (2 ^ b)

算数右移 >>

  1. 10 >> 1 // -> 5

算数右移就是将二进制全部往右移动并去除多余的右边，10 在二进制中表示为 1010 ，右移一位后变成 101 ，转换为十进制也就是 5，所以基本可以把右移看成以下公式 int v = a / (2 ^ b)

右移很好用，比如可以用在二分算法中取中间值 

  1. 13 >> 1 // -> 6

按位操作

按位与

每一位都为 1，结果才为 1

  1. 8 & 7 // -> 0
  2. // 1000 & 0111 -> 0000 -> 0

按位或

其中一位为 1，结果就是 1

  1. 8 | 7 // -> 15
  2. // 1000 | 0111 -> 1111 -> 15

按位异或

每一位都不同，结果才为 1

  1. 8 ^ 7 // -> 15
  2. 8 ^ 8 // -> 0
  3. // 1000 ^ 0111 -> 1111 -> 15
  4. // 1000 ^ 1000 -> 0000 -> 0

从以上代码中可以发现按位异或就是不进位加法

面试题：两个数不使用四则运算得出和

这道题中可以按位异或，因为按位异或就是不进位加法，8 ^ 8 = 0 如果进位了，就是 16 了，所以我们只需要将两个数进行异或操作，然后进位。那么也就是说两个二进制都是 1 的位置，左边应该有一个进位 1，所以可以得出以下公式 a + b = (a ^ b) + ((a & b) << 1) ，然后通过迭代的方式模拟加法

  1. function sum(a, b) {
  2.     if (a == 0) return b
  3.     if (b == 0) return a
  4.     let newA = a ^ b
  5.     let newB = (a & b) << 1
  6.     return sum(newA, newB)
  7. }