位运算在算法中很有用,速度可以比四则运算快很多。
在学习位运算之前应该知道十进制如何转二进制,二进制如何转十进制。这里说明下简单的计算方式
33
可以看成是 32 + 1
,并且 33
应该是六位二进制的(因为 33
近似 32
,而 32
是 2
的五次方,所以是六位),那么 十进制 33
就是 100001
,只要是 2
的次方,那么就是 1
否则都为 0
100001
同理,首位是 2^5
,末位是 2^0
,相加得出 33
10 << 1 // -> 20
左移就是将二进制全部往左移动,10
在二进制中表示为 1010
,左移一位后变成 10100
,转换为十进制也就是 20
,所以基本可以把左移看成以下公式 a * (2 ^ b)
10 >> 1 // -> 5
算数右移就是将二进制全部往右移动并去除多余的右边,10
在二进制中表示为 1010
,右移一位后变成 101
,转换为十进制也就是 5
,所以基本可以把右移看成以下公式 int v = a / (2 ^ b)
右移很好用,比如可以用在二分算法中取中间值
13 >> 1 // -> 6
每一位都为 1,结果才为 1
8 & 7 // -> 0 // 1000 & 0111 -> 0000 -> 0
其中一位为 1,结果就是 1
8 | 7 // -> 15 // 1000 | 0111 -> 1111 -> 15
每一位都不同,结果才为 1
8 ^ 7 // -> 15 8 ^ 8 // -> 0 // 1000 ^ 0111 -> 1111 -> 15 // 1000 ^ 1000 -> 0000 -> 0
从以上代码中可以发现按位异或就是不进位加法
面试题:两个数不使用四则运算得出和
这道题中可以按位异或,因为按位异或就是不进位加法,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) }
本文作者:毛超颖
本文链接:
版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!