位运算
为什么需要位运算
机器里的数字表示方式和存储格式就是二进制。
计算机大部分都是高电位和低电位,它本身任何一个整型或者十进制的数,在计算机里面的数字表示方式和存储形式都是二进制
4(d):0100
8(d):01000
5(d):0101
6(d):0110
十进制转二进制:余数短除法除以二
一直往下除,直到商为 0 为止。把每个新的商数除以二,然后把余数写在被除数的右边。直到商数为 0 为止。
位运算符
含义 | 运算符 | 示例 |
---|---|---|
左移 | << | 0011 => 0110 |
右移 | >> | 0110 => 0011 |
按位或:只要一个二进制为1,与出来就是1 | | | 0011 | 1011 => 1011 |
按位与:只要一个二进制为0,与出来就是0 | & | 0011 & 1011 => 0011 |
按位取反 | ~ | 0011 => 1100 |
按位异或(相同为零不同为一):相异就是 1,相同就是 0 | ^ | 0011 ^ 1011 => 1000 |
异或
异或:相同为 0,不同为 1。也可用 “不进位加法” 来理解。
异或操作的特点:
x ^ 0 => x
x ^ 1s => ~x // 1s = ~0
x ^ (~x) => 1s
x ^ x => 0
c = a ^ b => a ^ c = b,b ^ c = a // 交换两个数
a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c // associative
指定位置的位运算
- 将 x 最右边的 n 位清零:
x & (~0 << n)
- 获取 x 的第 n 位值(0 或者 1):
(x >> n) & 1
- 获取 x 的第 n 位的幂值:
x & (1 << n)
- 仅将第 n 位置为 1:
x | (1 << n)
- 仅将第 n 位置为 0:
x & (~(1 << n))
- 将 x 最高位至第 n 位(含)清零:
x & ((1 << n) - 1)
位运算要点
- 判断奇偶
x % 2 == 1
=>x & 1 == 1
x % 2 == 0
=>x & 1 == 0
- x >> 1 => x / 2
x = x / 2
=>x = x >> 1
mid = (left + right) / 2
=>mid = (left + right) >> 1
- x = x & (x - 1) 清零最低位的 1
- x & -x => 得到最低位的 1
- x & ~x => 0
- !!~(x) 判断下标是否存在
- !!~“xx”.indexOf(x)
相关题目
// 位1的个数
/**
* @param {number} n - a positive integer
* @return {number}
*/
var hammingWeight = function(n) {
let sum = 0;
while (n != 0) {
sum++;
n &= (n - 1);
}
return sum;
};
// 2的幂
// 这个数的表示形式,有且仅有二进制位是 1
/**
* @param {number} n
* @return {boolean}
*/
var isPowerOfTwo = function(n) {
return n > 0 && (n & (n - 1)) == 0;
};
// 颠倒二进制位
/**
* @param {number} n - a positive integer
* @return {number} - a positive integer
*/
var reverseBits = function(n) {
let ans = 0;
for (let i = 0; i < 32; i++) {
ans = (ans << 1) + (n & 1);
n >>= 1;
}
return ans >>> 0;
};
// 比特位计数
// 位运算 + DP
/**
* @param {number} n
* @return {number[]}
*/
var countBits = function(n) {
const ans = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
ans[i] = ans[i & (i - 1)] + 1;
}
return ans;
};