位运算

近4年初赛考察：

	题号	题型	分值
2021	第16题	阅读程序	10.5分
	第17题		14分
2022	第16题		10.5分

难易度：中等

2024年备考建议

站在出题人的视角，位运算在普及组也是属于不是很容易在复赛中考察的内容，但是放在初赛的阅读程序中却能很方便的提高区分度，即会位运算和不会的。也能通过位运算的考察，来考察学生对于二进制的理解，又很容易和编解码这类题做结合，简直不要太方便。所以命题者爱出，就要求大家掌握得很牢固。

除了位运算的一般用法，还要求掌握一些位运算的经典用法，比如lowbit运算，这样考场见到不用现场算，现场总结规律，就会得心应手。

作用于整数类型的运算对象，对二进制数位进行运算。

位与：& 当且仅当两个运算对象都为1时，该位为1

1 & 1 = 1 1 & 0 = 0 0 & 1 = 0 0 & 0 = 0

eg: 255 & 128 = 128

位或：| 当且仅当两个运算对象都为0时，该位为0

1 | 1 = 1 1 | 0 = 1 0 | 1 = 1 0 | 0 = 0

eg: 255 | 128 = 255

位取反：~ 将1置为0，将0置为1

~ 1 = 0 ~ 0 = 1

eg: ~ 128 = 127

位异或：^ 当且仅当两个运算对象中只一个为1时，该位为1

1 ^ 1 = 0 1 ^ 0 = 1 0 ^ 1 = 1 0 ^ 0 = 0

eg: 255 ^ 128 = 127

左移： <<

将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃，右边补0）。

左边二进制位丢弃不包括1时, 左移1位相当于​乘以2​。

eg: 3 << 2 = 12 (1100)

右移： >>

将一个数的各二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃.

右移1位相当于​除以2​（整数除法）。

eg: 7 >> 1 变成 3，也就是111 >> 1 变成了 11。

⚡快问快答

单选题

1、18^125^125=（）

• A 127
• B 143
• C 18
• D 125

位运算的性质

• x ^ x = 0 : 自己与自己做异或一定为0
• x ^ 0 = x : 一个数与0做异或还是它本身

位运算的应用：

Info

位运算的应用较多，写法种类也有多种。下面的应用，建议大家只是在本地都要运行一遍，加深记忆。

此外考场上难免会有不知道的位运算应用，这个时候，手算，对比，找规律，就是最好的方式。

• 取末位(x & 1) 可用来判断奇数、偶数
• 操作x的第j位（从右向左数，最右边是第0位）

x | (1 << j)  //将 x 的第 j 位设置为1

x & ~(1 << j) //将 x 的第 j 位设置为0

x ^ (1 << j)  //将 x 的第 j 位取反

(x >> j) & 1  //取 x 的第 j 位

• 交换两个数: a ^= b ^= a ^= b;
• lowbit 运算

int lowbit(int x) {
  // 计算 x 的二进制中，最低位的 1 以及后面所有 0 组成的数。
  // lowbit(0b01011000) == 0b00001000
  //          ~~~~^~~~
  // lowbit(0b01110010) == 0b00000010
  //          ~~~~~~^~
  return x & -x;  // CSP中考过lowbit另一种写法 x&(x^(x-1))
}

• 计算1的个数

// 求 x 的二进制中1的个数
int popcount(int x) {
    int cnt = 0;
    while (x) {
        cnt++;
        x -= x & -x;
    }
    return cnt;
}

• 枚举子集 给定n个元素，问这n个元素组成的每一个集合的所有子集。(n≤15)

for (int S=1; S<(1<<n); ++S){
    for (int S0=(S-1)&S; S0; S0=(S0-1)&S)
        //do something.
}

测试程序

这里给出一个可以用来直观展示位运算运算数和运算结果的程序，当你对位运算不熟悉的时候，可以拷贝这段代码，在本地稍加改造后运行。

#include <bits/stdc++.h>
using namespace std;
int f(int a, int b){	
	return a | (1 << b);
}
void otp(int x){
	for (int i = 31; i >= 0; i--) printf("%d", (x >> i) & 1);
}
int main(){
	int a, b; scanf("%d%d", &a, &b);
	int c = f(a, b); 
	printf("a = 0b"); otp(a);
	printf("\nb = 0b"); otp(b);
	printf("\nc = 0b"); otp(c);
}

• 思考题：下面4种操作的含义是什么？

x & (x + 1); 
x & (x - 1);
x | (x + 1);
x | (x - 1);

历年真题

1、填空题

01 #include <iostream>
02
03 using namespace std;
04
05 int main()
06 {
07     unsigned short x, y;
08     cin >> x >> y;
09     x = (x | x << 2) & 0x33;
10     x = (x | x << 1) & 0x55;
11     y = (y | y << 2) & 0x33;
12     y = (y | y << 1) & 0x55;
13     unsigned short z = x | y << 1;
14     cout << z << endl;
15     return 0;
16 }

假设输入的 x、y 均是不超过 15 的自然数，完成下面的判断题和单选题：

判断题

16.删去第 7 行与第 13 行的 unsigned，程序行为不变。（ ）

17.将第 7 行与第 13 行的 short 均改为 char，程序行为不变。（ ）

18.程序总是输出一个整数“0”。（ ）

19. 当输入为“2 2”时，输出为“10”。（ ）

20. 当输入为“2 2”时，输出为“59”。（ ）

21.当输入为“13 8”时，输出为（ ）。

A. “0”

B. “209”

C. “197”

D. “226”

答题须知 1.判题时不忽略大小写，如答案为B，而你输入的答案为b，则会被判错！

2.判题时不会忽略你输入答案的前后空格，如答案为B，而你输入的答案为空格B空格，则会被判错！

3.判断题A代表正确、B代表错误

单选题

2、为了统计一个非负整数的二进制形式中 1 的个数，代码如下：

int CountBit(int x)
{
	int ret = 0;
	while (x)
	{
		ret++;
		___________;
	}
	return ret;
}

则空格内要填入的语句是（ ）。

A. x >>= 1

B. x &= x - 1

C. x |= x >> 1

D. x <<= 1

3、二进制数11 1011 1001 0111和01 0110 1110 1011进行按位与运算的结果是( )。 (原题为“逻辑与”，但是根据题意应当是按位与。)

A. 01 0010 1000 1011

B. 01 0010 1001 0011

C. 01 0010 1000 0001

D. 01 0010 1000 0011