前言
本文分三个部分
-
有趣的位运算
-
算法比较常用的 n & (n - 1)
-
算法例题
位运算符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
左移 << 0011 -> 0110
右移 >> 0110 -> 0011
按位或 | 0011
-----> 1011
1011
按位与 & 0011
-----> 0011
1011
按位取反 ~ 0011 -> 1100
按位异或 ^ 0011
-----> 1000
1011
|
XOR 异或
1
2
3
4
5
6
7
|
异或: 相同为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的第n位值 (0 或者 1)
获取x的第n位的幂值
仅将第n位置为1
仅见第n位置为0
将x最高位至第n位 (含)清零
将第n位至第0位
1
|
x & (~((1 << (n-1))-1))
|
判断奇偶
1
2
|
x % 2 == 1 ---> (x & 1) == 1
x % 2 == 0 ---> (x & 1) == 0
|
x » 1 —> x / 2
1
|
即 x = x/2; ---> x = x >> 1;
|
得到最低位的1
X & ~X -> 0
将英文字符串转为大小写
1
2
3
4
5
6
7
8
9
10
|
大写变小写、小写变大写 : 字符 ^= 32;
大写变小写、小写变小写 : 字符 |= 32;
小写变大写、大写变大写 : 字符 &= -33;
/*
以上操作能够产生奇特效果的原因在于 ASCII 编码
字符其实就是数字，恰巧这些字符对应的数字通过位运算就能得到正确的结果，有兴趣的读者可以查 ASCII 码表自己算算，本文就不展开讲了
*/
|
判断两个数是否异号
1
2
3
4
5
|
int x = -1, y = 2;
bool f = ((x ^ y) < 0); // true
int x = 3, y = 2;
bool f = ((x ^ y) < 0); // false
|
交换两个数
1
|
int a = 1, b = 2;a ^= b;b ^= a;a ^= b;
|
加1
减1
1
2
|
int n = 2;n = ~-n;
// 现在 n = 1
|
算法常用操 n&(n-1)
1
|
这个操作是算法中常见的，作用是消除数字 n 的二进制表示中的最后一个 1
|
例题1 - 二进制中的1的个数
LCR 133. 位 1 的个数 - 力扣（LeetCode）
1
2
3
|
思路详解：
`就是让你返回 n 的二进制表示中有几个 1
因为 n & (n - 1) 可以消除最后一个 1，所以可以用一个循环不停地消除 1 同时计数，直到 n 变成 0 为止
|
1
2
3
4
5
6
7
8
|
int hammingWeight(uint32_t n) {
int res = 0;
while (n != 0) {
n = n & (n - 1);
res++;
}
return res;
}
|
题目推荐
例题1 - 插入
-
题目url
-
解题思路
- 先将N的第i ~ j位全部置零；
- 在将M左移i位，使之对其上一步中N置零的位，直接相加即可。
-
示例代码
-
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public:
int insertBits(int N, int M, int i, int j) {
for (int k = i; k <= j; ++ k)
{ //举例说明： (1 << 3) 表示 00001000，取反后得 11110111
// N &= (11110111) 表示将 N 的第3位置零了
N &= ~(1 << k);
}
return N + (M << i);
}
};
|
例题2 - 翻转数位
-
题目url
-
方法1 - 位运算
-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
/*
在遍历num每一位时，追踪当前1序列的长度和上一段1序列的长度；
当遇到比特位为0时，分两种情况讨论：
1、若下一个比特位为1，那么preLen = curLen；
2、若下一个比特位为0，那么preLen = 0，我们不能合并这两个1序列
*/
class Solution {
public:
int reverseBits(int num) {
if (~num == 0) return 32; //全是1的情况，若不特判会输出33
int curLen = 0, preLen = 0；
int maxLen = 1; //最少也能翻转1位
for (int i = 0; i < 32; ++ i) {
if ((num & 1) == 1) {
curLen ++ ;
}
else {
preLen = ((num & 2) == 0) ? 0 : curLen; //判断下一比特位是否为0
curLen = 0;
}
maxLen = max(maxLen, preLen + curLen + 1);
num >>= 1;
}
return maxLen;
}
};
|