位运算符 &、|、^ 的应用

1. 位与运算符 & 的应用

1.1 奇偶性判定

• 奇数二进制数末尾位为 1；
• 偶数二进制数末尾位为 0；

#include 

int main()
{
    int a = 16;
    int b = 1; 
    int flag = (a & b);
    if (flag) 
    {
        std::cout << " a 奇数" << std::endl;
    }
    else 
    {
        std::cout << " a 偶数" << std::endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1.2 取末五位

【例题1】给定一个数，求它的二进制表示的末五位，以十进制输出即可。

我们只需要末五位，剩下的位我们是不需要的，所以可以将给定的数 位与上 0b11111，这样一来就直接得到末五位的值了。

int main()
{
    int a = 654321;
    int b = 0b11111; 

    std::cout << "最后 5 位为 " << (a & b) << std::endl;
    return 0;
}
1
2
3
4
5
6
7
8

末 7 位，末 14 位，只需要将 0b11111 替换为对应的位数。

1.3 消除末尾五位

【例题3】给定一个 32 位整数，要求消除它的末五位。

消除末尾五位，即把后 5 位置为 0，剩下的位不变。

根据位运算的性质，我们需要数，它的高27位都为1，低五位都为 0，则这个数就是：
(11111111111111111111111111100000)

一般我们把它转成十六进制，每四个二进制位可以转成一个十六进制数，所以得到十六进制数为 0xffffffe0

int main()
{
    int a = 654321;
    int b = 0xffffffe0;

    std::cout << "消除后 5 位为 " << (a & b) << std::endl;
    return 0;
}
1
2
3
4
5
6
7
8

1.4 消除末尾连续1

【例题4】给出一个整数，现在要求将这个整数转换成二进制以后，将末尾连续的1都变成0，输出改变后的数（以十进制输出即可）。

假设某个数的二进制为 0b01110111，给这个数加 1 之后变为 0b01111000，所以将这两个数与的结果就是我们想要的。

int main()
{
    int a = 0b0110111;
    int b = a + 1;
    int ret = (a & b);
    std::cout << "ret is " << ret << std::endl;
    return 0;
}
1
2
3
4
5
6
7
8

1.5 2的幂判定

【例题5】请用一句话，判断一个正数是不是2的幂。

是不是 2 的幂，即是不是 2 的 N 次方，那么 2 的 N 次方一般都是这样的形式， 0b0010000，如果给这个数减去 1 得到为 0b0001111，然后两个结果相与，如果为 0 就表示为 2 的幂。

于是我们就知道了如果一个数 x 是 2 的幂，那么 x & (x-1) 必然为零。

int main()
{
    int a = 0b010001;
    int b = a - 1;
    int flag = (a & b);
    if (flag)
    {
        std::cout << "no "<< std::endl;
    }
    else
    {
        std::cout << "yes "<< std::endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

参考：
https://blog.csdn.net/WhereIsHeroFrom/article/details/118378449

2. 位或运算符 | 的应用

2.1 设置标记位

【例题1】给定一个数，判断它二进制低位的第 5 位，如果为 0，则将它置为 1。

如果第 5 位为 1，不用进行任何操作；如果第 5 位为 0，则置为 1。言下之意，无论第五位是什么，我们都直接置为 1即可，代码如下：

int main()
{
    int a = 0b010001;
  
    std::cout << (a | 0b10000) << std::endl;
    
    return 0;
}
1
2
3
4
5
6
7
8

2.2 置空标记位

【例题2】给定一个数，判断它二进制低位的第 5 位，如果为 1，则将它置为 0。

其它位不能变，所以位与上1；第5位要置零，所以位与上0；

int main()
{
    int a = 0b010001;
  
    std::cout << (a & 0b11111111111111111111111111101111) << std::endl;
    
    return 0;
}
1
2
3
4
5
6
7
8

我们利用位或，只能将第5位设置成1，怎么把它设置成0呢？

我们可以配合减法来用。分成以下两步：
  1）首先，强行将低位的第5位置成1；
  2）然后，强行将低位的第5位去掉；

int main()
{
    int a = 0b110000;
    int b = 0b10000;
    std::cout << ((a | 0b10000) - b) << std::endl;
    
    return 0;
}
1
2
3
4
5
6
7
8

2.3 低位连续零变一

【例题3】给定一个整数 x ，将它低位连续的 0 都变成 1。

假设 a = 0b110000 要变成 0b111111， 那么给 a -1 = 0b101111，只需要将 0b111111 和 0b101111 按位 或即可。

int main()
{
    int a = 0b110000;
    std::cout << (a | (a - 1)) << std::endl;
    
    return 0;
}
1
2
3
4
5
6
7

x | (x-1) 就是题目所求的 “低位连续零变一” 。

2.4 低位首零变一

【例题4】给定一个整数 x ，将它低位第一个 0 变成 1。

int main()
{
    int a = 0b110000;
    std::cout << (a | (a + 1)) << std::endl;
    
    return 0;
}
1
2
3
4
5
6
7

3. 位与运算符 ^ 的应用

异或特征：
1）两个相同的十进制数异或的结果一定为零。
2）任何一个数和 0 的异或结果一定是它本身。
3）异或运算满足结合律和交换律。

3.1 标记位取反

【例题1】给定一个数，将它的低位数起的第 4 位取反，0 变 1，1 变 0。

我们分析一下题目意思，如果第 4 位为 1，则让它异或上 0b1000就能变成 0；如果第 4 位 为 0，则让它异或上 0b1000就能变成 1，也就是无论如何都是异或上 0b1000，代码如下：

int main()
{
    int a = 0b110000;
    std::cout << (a | 0b1000) << std::endl;
    
    return 0;
}
1
2
3
4
5
6
7

3.2 变量交换

【例题2】给定两个数 a 和 b ，用异或运算交换它们的值。

int main()
{
    int a = 3;
    int b = 4;
    a = a ^ b;	// (1) 
    b = a ^ b; // (2) 
    a = a ^ b; // (3) 
    std::cout << a << b << std::endl;
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11

我们直接来看 (1) 和 (2) 这两句话，相当于b等于a ^ b ^ b，根据异或的几个性质，我们知道，这时候的b的值已经变成原先a的值了。
而再来看第 ( 3 ) (3) 句话，相当于a等于a ^ b ^ a，还是根据异或的几个性质，这时候，a的值已经变成了原先b的值。
从而实现了变量a和b的交换。

3.3 出现奇数次的数

【例题3】输入 n 个数，其中只有一个数出现了奇数次，其它所有数都出现了偶数次。求这个出现了奇数次的数。

根据异或的性质，两个一样的数异或结果为零。也就是所有出现偶数次的数异或都为零，那么把这 n 个数都异或一下，得到的数就一定是一个出现奇数次的数了。

3.4 丢失的数

【例题4】给定一个 n−1 个数，分别代表 1 到 n 的其中 n − 1 个，求丢失的那个数。

分别用 1 到 n-1 的数字和给定的数字进行异或操作，根据 a^a = 0, 找出所有异或结果都不为 0 的那个数。