0%

《算法很美》——位运算的奇巧淫技

寒假前报名了蓝桥杯,和同学一起参加了蓝桥杯 《算法很美》的课程,于是开了个新坑,学习一些基本的算法知识。

位操作

摘自维基百科

取反(NOT)

取反是一元运算符,对一个个二进制数的每一位执行逻辑反操作,是数字1成为0,数字0成为1。例如:

NOT 0111 = 1000

在C/C++程序设计语言中,取反操作通过波浪线“~”来表示。

按位或(OR)

按位或处理两个长度相同的二进制数,两个相应的二进位中只要有一个为1,该位的结果值为1。例如:

0010 OR 1000 = 1010

在C/C++程序设计语言中,按位或操作通过单竖线“|”来表示。

按位异或(XOR)

按位异或对等长二进制模式或二进制数的每一位执行逻辑异或操作。操作结果是如果某位不同则改为为1,否则改为为0。例如:

0101 XOR 0011 = 0110

在C/C++程序设计语言中,按位异或的运算符是“^”。

按位与(AND)

按位与处理两个长度相同的二进制数,两个相应的二进位都为1,改为的结果值才为1,否则为0。例如:

0101 AND 0011 = 0001

在C/C++程序设计语言中,按位与的运算符是“&”。

移位

移位是一个二元运算符,用来将一个二进制数的每一位全部都向一个方向移动指定为,溢出的部分将被舍弃,而孔雀的部分填入0。例如:

0001 << 3 = 1000

1010 >> 2 = 0010

在C/C++程序设计语言中,移位的运算符是“<<”与“>>”。

应用

1. 判断奇偶数

题目

任给一个整数n,判断该数是否为奇数。

定义判断

  • 可以被2整除的数是偶数,不可被2整除的数是奇数
1
2
3
4
5
6
7
8
bool IsOdd(int n)
{
if (n % 2 == 0)
{
return false;
}
return true;
}

使用位运算“&”

  • 奇数的二进制形式最后一位是1,偶数则为0
  • 按位与处理两个长度相同的二进制数,两个相应的二进位都为1,改为的结果值才为1,否则为0

因此,任意一个整数n与整数1进行操作时,若n二进制形式最低为为1则结果为1,否则为0。

1
2
3
4
5
6
7
8
bool IsOdd(int n)
{
if (n & 1)
{
return true;
}
return false;
}

验证程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>

using namespace std;

bool IsOdd(int n);

int main()
{
int n;
cout << "请输入一个整数:" << endl;
cin >> n;
if (IsOdd(n))
{
cout << n << "是奇数。" << endl;
}
else
{
cout << n << "不是奇数。" << endl;
}
return 0;
}

2.找出唯一成对的数

题目

1-n这n个数放在含有(n+1)个元素的数组中,只有唯一的一个元素值重复,其它的均只出现一次。每个数组元素只能访问一次,设计一个算法,将它找出来。如果不使用存储空间,能否设计一个算法实现?

计数(需要辅助空间)

可以记下每个数字出现的次数,然后找到出现两次的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int PairNumber(int *arr, int n)
{
int *bucket = new int[n];
memset(bucket, 0, n * sizeof(bucket[0]));

//记录下每个数出现的次数,保存到对应下标下
for (int i = 0; i <= n; i++)
{
bucket[arr[i]]++;
}

//遍历查找出现两次的数
for (int i = 0; i < n; i++)
{
if (bucket[i] == 2)
{
return i;
}
}
return -1;
}

异或去除重复(偶数次)项

  • 两个相同的数进行异或,结果是0
  • 如果对一系列数进行异或,可以消除掉重复出现偶数次的数
  • 将原数组的数异或一边后,再与1-n异或一边,则重复出现两次的数被异或了三次,其余的数被异或了两次被消去,因此最终结果就是原数组中出现两次的数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int PairNumber(int *arr, int n)
{
int ret = 0;

//遍历异或原数组
for (int i = 0; i <= n; i++)
{
ret ^= arr[i];
}

//与1-n异或
for (int i = 1; i <= n; i++)
{
ret ^= i;
}
return ret;
}

验证程序

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
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cstring>

using namespace std;

int PairNumber(int *arr, int n);

int main()
{
int n;
cout << "请输入n:" << endl;
cin >> n;

//构造长度为(n+1)的数组
int *arr = new int[n + 1];
for (int i = 0; i < n; i++)
{
arr[i] = i + 1;
}
srand((int)time(NULL));
arr[n] = (int)(rand() * 1.0 / RAND_MAX * (n - 1) + 1);

//打乱数组
for (int i = 0; i <= n; i++)
{
swap(arr[i], arr[(int)(rand() * 1.0 / RAND_MAX * n)]);
}

//输出结果
cout << "原数组为:" << endl;
for (int i = 0; i <= n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
cout << "重复出现的数为:" << PairNumber(arr, n) << endl;
return 0;
}

3.找出落单的数

题目

一个长度为(2×n+1)的数组里除了某一个数字之外,其它的数字都出现了两次,请写出程序找出这个只出现了一次的数字。

异或去重

思路与上题类似,通过遍历异或消去重复出现两次的数。

1
2
3
4
5
6
7
8
9
int SingleNumber(int *arr, int n)
{
int ret = 0;
for (int i = 0; i < n; i++)
{
ret ^= arr[i];
}
return ret;
}

验证程序

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
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int SingleNumber(int *arr, int n);

int main()
{
int n;
cout << "请输入n:" << endl;
cin >> n;

//构造长度为(2×n+1)的数组
srand((int)time(NULL));
int *arr = new int[2 * n + 1];
for (int i = 0; i < n; i++)
{
arr[i] = arr[i + n] = rand();
}
arr[2 * n] = rand();

//打乱数组
int len = 2 * n + 1;
for (int i = 0; i < len; i++)
{
swap(arr[i], arr[(int)(rand() * 1.0 / RAND_MAX * len)]);
}

//输出结果
cout << "原数组为:" << endl;
for (int i = 0; i < len; i++)
{
cout << arr[i] << " ";
}
cout << endl;
cout << "出现一次的数为:" << SingleNumber(arr, len) << endl;
return 0;
}

4.找出两个落单的数

题目

一个长度为(2×n+2)的数组里除了某两个个数字之外,其它的数字都出现了两次,请写出程序找出这两个只出现了一次的数字。

三次异或

可知如果用0和所有的数都异或一遍,可以的到没有重复的两个数异或的结果。

因为这两个数并不相同,所以得到的结果必定不是0,即所得结果二进制中必定存在至少一个1。

根据异或的性质可知,这两个数在这一位的数一定不相同,一个是1,而另一个是0。那么,如果将所有该位是1的数与所有该位都是0的数分别异或,所得结果就是这两个数。

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
pair<int, int> SingleNumbers(int *arr, int n)
{
int first = 0, second = 0;
int temp = 0;
for (int i = 0; i < n; i++)
{
temp ^= arr[i];
}
int flag = 0;
for (int i = 0;; i++)
{
if (temp & (1 << i))
{
flag = 1 << i;
break;
}
}
for (int i = 0; i < n; i++)
{
if (arr[i] & flag)
{
first ^= arr[i];
}
else
{
second ^= arr[i];
}
}
return make_pair(first, second);
}

验证程序

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 <iostream>
#include <cstdlib>
#include <ctime>
#include <utility>

using namespace std;

pair<int, int> SingleNumbers(int *arr, int n);

int main()
{
int n;
cout << "请输入n:" << endl;
cin >> n;

//构造长度为(2×n+2)的数组
srand((int)time(NULL));
int *arr = new int[2 * n + 2];
for (int i = 0; i < n; i++)
{
arr[i] = arr[i + n] = rand();
}
arr[2 * n] = rand();
arr[2 * n + 1] = arr[2 * n] + rand();

//打乱数组
int len = 2 * n + 2;
for (int i = 0; i < len; i++)
{
swap(arr[i], arr[(int)(rand() * 1.0 / RAND_MAX * len)]);
}

//输出结果
cout << "原数组为:" << endl;
for (int i = 0; i < len; i++)
{
cout << arr[i] << " ";
}
cout << endl;
pair<int, int> ans = SingleNumbers(arr, len);
cout << "出现一次的数为:" << ans.first << "与" << ans.second << endl;
return 0;
}

5.二进制中1的个数

题目

给定一个整数n,输出该数二进制表示中1的个数。

与做法之一

  • 两个二进制数按位与,若相同位相同,则结果为1,否则为0

让一个只有最低位为1的二进制与原数与,然后不断左移,如果结果不为0则说明该位是1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int CountOneinBit(int n)
{
int size = sizeof(n) * CHAR_BIT;
int ret = 0, temp = 1;
for (int i = 0; i < size;i++)
{
if(n&temp)
{
ret++;
}
temp <<= 1;
}
return ret;
}

与做法之二

与做法一类似,但是改为将原数右移和1进行与运算

1
2
3
4
5
6
7
8
9
10
11
12
13
int CountOneinBit(int n)
{
int ret = 0;
for (int i = 0; n; i++)
{
if (1 & n)
{
ret++;
}
n >>= 1;
}
return ret;
}

与做法之三

  • 对于整数n,n&(n-1)的结果是消除掉n二进制形式的最后一个。

不断消除整数二进制形式的最后一个1,直到原数变成0,则消除的次数就是1的个数

1
2
3
4
5
6
7
8
9
10
int CountOneinBit(int n)
{
int ret = 0;
for (int i = 0; n; i++)
{
n = n & (n - 1);
ret++;
}
return ret;
}

验证程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>

using namespace std;

int CountOneinBit(int n);

int main()
{
int n;
cout << "请输入一个整数n:" << endl;
cin >> n;
cout << n << "的二进制形式中1的个数是:" << CountOneinBit(n) << endl;
return 0;
}

6.判断一个整数是否为2的整数次方

题目

使用一条语句判断一个整数是否为2的整数次方

与做法

易知如果一个数的二进制形式中只有一个1,则符合题意,考虑上题第三种解法,可得:

1
2
3
4
bool IsIntegerPowerof2(int n)
{
return !(n & (n - 1));
}

验证程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>

using namespace std;

bool IsIntegerPowerof2(int n);

int main()
{
int n;
cout << "请输入一个整数n:" << endl;
cin >> n;
cout << n;
if (!IsIntegerPowerof2(n))
{
cout << "不";
}
cout << "是2的整数次幂。" << endl;
return 0;
}

7.将整数的奇偶位互换

题目

将一个整数n的二进制形式下的奇数位与偶数位互换。

拆分,移位,异或

具体思路如下图:

将奇位与偶位拆分开,通过移位后再次组合在一起

1
2
3
4
5
6
int SwapOddEven(int n)
{
int even = n & 0xaaaaaaaa;//10101010....
int odd = n & 0x55555555;//01010101....
return (even >> 1) ^ (odd << 1);
}

验证程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>

using namespace std;

int SwapOddEven(int n);

int main()
{
int n;
cout << "请输入一个整数n:" << endl;
cin >> n;
cout << n << "的奇偶位互换后是" << SwapOddEven(n) << endl;
return 0;
}

8.出现k次与出现1次

题目

数组中只有一个数出现了1次,其它的数都出现了k次,请输出只出现了1次的数。

k进制不进位加法

  • k个相同的k进制数之和为0

老实说这个解法不算很简洁,但是很独特。将所有的数转化为k进制,然后进行不进位加法,则最终的结果就是只出现了一次的数的k进制,再转回去就好。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
const int maxn = 1e3 + 10;

//将两个k进制数进行不进位相加
string noCrashSum(string kRadix1, string kRadix2, int k)
{
reverse(kRadix1.begin(), kRadix1.end());
reverse(kRadix2.begin(), kRadix2.end());
int len = max(kRadix1.length(), kRadix2.length());
while (kRadix1.length() < len)
{
kRadix1 += "0";
}
while (kRadix2.length() < len)
{
kRadix2 += "0";
}
string ret;
for (int i = 0; i < len; i++)
{
ret += ((kRadix1[i] - '0' + kRadix2[i] - '0') % k + '0');
}
reverse(ret.begin(), ret.end());
return ret;
}

//计算长度为n的k进制数组的不进位和
string noCrashSum(string kRadixs[], int n, int k)
{
string ret;
for (int i = 0; i < n; i++)
{
ret = noCrashSum(ret, kRadixs[i], k);
}
return ret;
}

//将十进制整数n转化为k进制字符串
string ToString(int n, int k)
{
string ret = "";
do
{
ret += (n % k + '0');
n /= k;
} while (n);
return ret;
}

//将k进制数kRadix转化为十进制整数
int ToInt(string kRadix, int k)
{
reverse(kRadix.begin(), kRadix.end());
int ret = 0;
for (int i = 0; i < kRadix.length(); i++)
{
ret = ret * k + (kRadix[i] - '0');
}
return ret;
}

//求在长度n的数组中,只出现一次的数
int SingleNumber(int *arr, int n, int k)
{
string kRadixs[maxn];
for (int i = 0; i < n; i++)
{
kRadixs[i] = ToString(arr[i], k);
}
string kRadixAns = noCrashSum(kRadixs, n, k);
return ToInt(kRadixAns, k);
}

验证程序

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <array>
#include <algorithm>
#include <ctime>
#include <cstdlib>

using namespace std;

const int maxn = 1e3 + 10;

//将两个k进制数进行不进位相加
string noCrashSum(string kRadix1, string kRadix2, int k);

//计算长度为n的k进制数组的不进位和
string noCrashSum(string kRadixs[], int n, int k);

//将十进制整数n转化为k进制字符串
string ToString(int n, int k);

//将k进制数kRadix转化为十进制整数
int ToInt(string kRadix, int k);

//求在长度n的数组中,只出现一次的数
int SingleNumber(int *arr, int n, int k);

int main()
{
int n, k;
cout << "Tip: n × k < " << maxn << endl;
cout << "请输入一个n:" << endl;
cin >> n;
cout << "请输入一个k:" << endl;
cin >> k;
int len = n * k + 1;

//生成数组
int *arr = new int[len];
srand(time(NULL));
for (int i = 0; i < n; i++)
{
int value = rand();
for (int j = 0; j < k; j++)
{
arr[i + n * j] = value;
}
}
arr[len - 1] = rand();

//打乱数组
for (int i = 0; i < len; i++)
{
swap(arr[i], arr[(int)(rand() * 1.0 / RAND_MAX * len)]);
}

cout << "原数组为:" << endl;
for (int i = 0; i < len; i++)
{
cout << arr[i] << " ";
}
cout << endl;

cout << "出现一次的数是:" << SingleNumber(arr, len, k) << endl;
return 0;
}

总结

本次课程的内容就像是题目所说的“奇巧淫技”,本来对位运算了解并不多,也不怎么会用,而这次见识到的这些神奇的操作则是刷新了我对位运算的看法,体会到了算法的神奇巧妙之处。

如果帮到了你的话,可以考虑请我喝咖啡