陈留阳
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\sim 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\sim 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\times 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\times 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;
}

总结

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