位运算

1. 基本操作

左移

A = 1100  B = 2
A << B = 110000

右移

算术右移: 带符号的右移

逻辑右移: 不带符号的右移

A = 11111111111111111111111110000001
B = 2
A >> B = 11111111111111111111111111100000
A >>> B = 00111111111111111111111111100000

与操作

A = 001010
B = 101100
A & B = 001000

或操作

A = 001010
B = 101100
A | B = 101110

非操作

二进制表示每一位进行取反操作，如果对应的二进制位为 0，结果位为 1，否则为 0.

 A = 00000000000000000000000000001010
~A = 11111111111111111111111111110101

异或操作

二进制表示的每一位进行异或操作，如果对应的二进制位不同，结果位为 1，否则为 0.

A = 001010
B = 101100
A ^ B = 100110

2. 使用位运算进行权限管理

使用左移（<<）创建权限

const test1 = 1 << 0 // 以8位二进制表示：00000001
const test2 = 1 << 1 // 00000010
const test3 = 1 << 2 // 00000100
const test4 = 1 << 3 // 00001000
const test5 = 1 << 4 // 00010000
const test6 = 1 << 5 // 00100000

使用按位或（|）分配权限

const user1 = test1 // 00000001
const user2 = test1 | test2 // 00000011
const user3 = test1 | test2 | test3 // 00000111
const user4 = test1 | test3 | test4 // 00011001
const user5 = test6 | test3 | test4 | test5 // 00111100

使用按位与（&）校验权限

console.log((user1 & test1) > 0) // true;
console.log((user5 & test6) > 0) // true;
console.log((user5 & test1) > 0) // false;
console.log((user3 & test2) > 0) // true;

3. 有用小技巧

1. 消去最后一位的 1

x & (x - 1) 用于消去 x 最后一位的 1

x = 1100
x - 1 = 1011
x & (x - 1) = 1000

应用

1. 用 O(1) 时间检测整数 n 是否是 2 的幂次
2. 计算在一个 32 位的整数的二进制表式中有多少个 1。
3. 如果要将整数 A 转换为 B，需要改变多少个 bit 位？

2. 异或运算的特性

• 交换律：A ^ B = B ^ A

• 结合律：A ^ (B ^ C) = (A ^ B) ^ C

• 恒等律：A ^ 0 = A

• 归零律：A ^ A = 0

应用

1. 数组中，只有一个数出现一次，剩下都出现两次，找出出现一次的数

3. 最后一位 1 的位置

x & -x 用于取最后一位 1 的位置

x = 00001100
-x = 11110100
x & -x = 00000100

4. 负数的二进制表示

负数的二进制表示分为三步：

1. 把这个负数的绝对值转换为二进制，即求原码
2. 把原码取反，即求反码
3. 把反码加 1，即求补码

例如: 把 -5 转换为二进制

1. 求原码：即把-5 的绝对值 5 转换为二进制 为 00000101
2. 求反码：为 11111010
3. 求补码：为 11111011

5. 参考

• 位运算面试题大总结