通过一道题来回顾下位运算
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
示例:
1
2
3
4
5
6
7
8
9
10
| 输入: x = 1, y = 4
输出: 2
解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。
|
答案：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| var hammingDistance = function(x, y) {
var count = 0;
while(x !== 0 || y !== 0) {
if((x & 1) !== (y & 1)) {
++count;
}
x = x >> 1;
y = y >> 1;
}
return count;
};
|
思路其实很简单：遍历两个数值，位数不相同那么 +1
负值如何用二进制表示
通过3个步骤得到：
- 确定绝对值的二进制表示（如-18，先确定18的二进制表示）
- 找到每一位数值的补数，也就是，每个0变1，1变0
- 给结果+1
有符号的整数
有符号的整数：第32位是符号位，如0表示正，1表示负；使用剩余的31位表示数值大小。
位运算规则
1
2
3
4
5
| & : 按二进制位进行 与运算，相同位同时为 1 时结果为 1，否则为 0
| : 按二进制位进行 或运算，相同位有一个为 1 时结果为 1，否则为 0
^ : 按二进制位进行 异或运算，相同位相同时结果为 0，否则为 1
>> : 右移运算是将一个二进制位的操作数按指定移动的位数向右移动，移出位被丢弃，左边移出的空位用符号位来补
<< : 左移运算是将一个二进制位的操作数按指定移动的位数向左移位，移出位被丢弃，右边的空位一律补 0
|
将-5右移1位
1
2
3
| var x = -5;
x >>= 1;
// -3
|
发生了如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| // 如：-5
// 1.找到5
000...101
// 2.找补数
111...010
// 3.补数+1,得到-5
111...011
// 4.右移1位
1111..101
// 5.减一
1111..100
// 6.取反，-3（符号位跟以前一样）
0000..011
|