Picker Ready Go

# 算法基础

# 位运算

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

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

# 左移 <<

10 << 1 // -> 20
1

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

# 算数右移 >>

10 >> 1 // -> 5
1

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

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

13 >> 1 // -> 6
1

# 按位操作

# 按位与

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

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

# 按位或

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

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

# 按位异或

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

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

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

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

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

← 数据结构 →