几个有趣的位运算操作
利用或操作|和空格将英文字符转换成小写
1
2
('a' | ' ') = 'a'
('A' | ' ') = 'a'
利用与操作&和下划线将英文字符转换成大写
1
2
('b' & '_') = 'B'
('B' & '_') = 'B'
利用异或操作^和空格进行英文字符大小写互换
1
2
('d' ^ ' ') = 'D'
('D' ^ ' ') = 'd'
二进制中1的个数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
输入：n
输出：1 的个数
样例：
输入：5
输出：3
思路：利用n&(n-1)来消除二进制中1的最后一位统计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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
while (cin >> n) {
int res = 0;
while (n) {
res++;
n = n & (n - 1); // 消除n的二进制中的最后一个1
}
cout << res << endl;
}
return 0;
}
// 统计从1~num每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。、
/**
* 时间复杂度：O(nk)
*/
vector<int> countBits(int num) {
vector<int> res;
for (int i = 0; i <= num; i++) {
int cnt = 0;
int n = i;
while (n) { // 统计每一个数字的二进制中1的个数
n = n & (n - 1);
cnt++;
}
res.push_back(cnt);
}
return res;
}
/**
* x可以看成是x’左移一位再加上新添进来的一位的结果
* 时间复杂度：O(n)
*/
vector<int> countBits(int num) {
vector<int> res(num + 1);
for (int i = 1; i <= num; i++) res[i] = res[i >> 1] + (i & 1);
return res;
}
颠倒二进制位
颠倒给定的 32 位无符号整数的二进制位。
输入：00000010100101000001111010011100 // 对应的无符号整数
输出：00111001011110000010100101000000 // 对应的无符号整数
思路：从右至左，对于每一位进行颠倒，通过n&1获取每一位，然后向右移动到相应的位置和之前的结果相加。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
int main() {
uint32_t n;
while (cin >> n) {
uint32_t res = 0, power = 31;
while (n) {
// 将最后一位移动到对应的位置与之前的结果相加
res += (n & 1) << power;
// 更新最后一位
n = n >> 1;
// 更新当前位移到的步数
power--;
}
cout << res << endl;
}
return 0;
}
缺失数字
给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。LeeCode268
思路：0-n中缺失一个数字，说明这n个序列中必定有n存在。我们将其余的数字的值和索引对应，然后分别将值和索引进行异或操作，如果索引和值可以对应上就会通过异或抵消，最终没被抵消掉的数就是缺失的数字。技巧是将初始值设置为n。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
while (cin >> n) {
int nums[n];
for (int i = 0; i < n; i++) cin >> nums[i];
int res = n;
for (int i = 0; i < n; i++) {
res ^= nums[i] ^ i;
}
cout << res << endl;
}
return 0;
}
只出现一次的数字I
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。LeeCode136
思路：对所有元素进行异或操作，剩余的数字就是出现一次的数字，因为出现两次的数字会被抵消
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
while (cin >> n) {
int nums[n];
for (int i = 0; i < n; i++) cin >> nums[i];
int res = 0;
for (int i = 0; i < n; i++) {
res ^= nums[i];
}
cout << res << endl;
}
return 0;
}
只出现一次的数字II
一个整型数组nums里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。面试题56数组中数字出现的次数
思路：前面讲到，数组中只有一个数字出现一次，可以通过异或运算求得，我们对这个思路扩展，考虑将数组分成两部分，每一部分中只有一个数字出现了一次，其余数字都出现了两次，然后可以利用异或运算分别求得每一部分中只出现一次的数字。（1）首先将所有数字进行异或运算，因为数组里面有两个数字只出现了一次，所以它们异或的结果一定不为0，即某一位一定为1，我们以这一位是否为1来划分数组，就可以保证每一部分中只有一个数字只出现了一次，因为相同的数字它们的位是一样的，所以会被分到相同的组里面；（2）对每一部分分别进行异或运算，即可求得只出现一次的数字。
参考代码
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
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
while (cin >> n) {
vector<int> nums(n);
for (int i = 0; i < n; i++) cin >> nums[i];
int n1 = 0, n2 = 0;
int t = 0;
for (auto n : nums) t ^= n; // 异或得到一个不为零的数字
int idx = 0;
while (!(t & 1)) { // 寻找划分标志位
t >>= 1;
idx++;
}
// 对每一部分分别进行异或
for (auto n : nums) {
if ((n >> idx) & 1)
n1 ^= n;
else
n2 ^= n;
}
cout << n1 << ' ' << n2 << endl;
}
return 0;
}
只出现一次的数字III
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。LeeCode137
思路：有限状态自动机 + 位运算 参考题解
参考代码
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
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
while (cin >> n) {
vector<int> nums(n);
for (int i = 0; i < n; i++) cin >> nums[i];
// 高逼格的代码 看不懂。。。。
// int ones = 0, twos = 0;
// for (auto n : nums) {
// ones = ones ^ n & ~twos;
// twos = twos ^ n & ~ones;
// }
// cout << ones << endl;
// 通俗版本
int m[32] = {0}; // 记录每一位1出现的次数
for (auto n : nums) {
// 统计每一位1出现的次数
for (int i = 0; i < 31; i++) {
if ((n >> i) & 1) m[i]++;
}
}
int res = 0;
// 生成只出现一次的数字
for (int i = 31; i >= 0; i--) {
res = res << 1;
res += m[i] % 3; // 判断当前位是1还是0
}
}
return 0;
}
不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。LeeCode371，剑指offer
思路：考虑采用位运算来做加法，通过实验发现，位运算做加法和正常加法一样，都是先不考虑进位做加法，再把进位的结果加上去。发现位运算的不进位加法等价于两个数异或的结果，位运算的进位只有两个数对应位全是1时才进位，可以通过两个数的与操作然后左移一位得到.
(1) 两数字做异或运算得到不进位的和； (2) 两个数字做与运算然后左移一位得到进位的结果。 (3) 将上面两个结果相加，直到没有进位停止。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b;
while (cin >> a >> b) {
int res = 0, carry = 0;
res = a ^ b; // 不进位的和
carry = (unsigned int)(a & b) << 1; // 进位的和
int n1 = res, n2 = carry;
while (n2) {
res = n1 ^ n2;
carry = (unsigned int)(n1 & n2) << 1;
n1 = res, n2 = carry;
}
cout << res << endl;
}
return 0;
}
