#CSPJCSMN12. 普及组程序专项-位运算

普及组程序专项-位运算

CSP-J/S 位运算核心操作专项训练（10题）

题目1：与运算(&)基础应用

#include <iostream>
using namespace std;

int main() {
    int a = 12;  // 二进制1100
    int b = 10;  // 二进制1010
    int result = a & b;
    
    cout << a << " & " << b << " = " << result << endl;
    cout << "二进制: ";
    for (int i = 3; i >= 0; i--) {
        cout << ((result >> i) & 1);
    }
    return 0;
}

判断题

  1. 第6行的a & b计算的是两个数的按位与结果。 ( )
  2. 按位与运算的规则是：对应位都为1时结果位才为1。 ( )
  3. 12 & 10的结果是8（二进制1000）。 ( )

选择题 4. 对于任意整数x，x & 0的结果是（ ）。
A. x
B. 0
C. 1
D. -1

  1. 第9行的(result >> i) & 1的作用是（ ）。
    A. 将result右移i位
    B. 提取result的第i位值
    C. 计算2的i次方
    D. 判断result的奇偶性

题目2：异或运算(^)的性质

#include <iostream>
using namespace std;

int main() {
    int x = 7;   // 二进制0111
    int y = 4;   // 二进制0100
    
    cout << "x ^ y = " << (x ^ y) << endl;
    cout << "x ^ x = " << (x ^ x) << endl;
    cout << "x ^ 0 = " << (x ^ 0) << endl;
    cout << "x ^ y ^ y = " << (x ^ y ^ y) << endl;
    
    return 0;
}

判断题

  1. 异或运算满足交换律：a ^ b = b ^ a。 ( )
  2. 任何数与自身异或结果为0。 ( )
  3. 异或运算满足结合律。 ( )

选择题 4. 7 ^ 4的计算结果是（ ）。
A. 3
B. 4
C. 7
D. 11

  1. 下列哪个等式总是成立？（ ）
    A. a ^ b = a | b
    B. a ^ b = a & b
    C. a ^ b ^ b = a
    D. a ^ b = ~(a ^ b)

题目3：取反运算(~)与补码

#include <iostream>
using namespace std;

int main() {
    unsigned char a = 5;    // 二进制00000101
    unsigned char b = ~a;
    
    cout << "a = " << (int)a << endl;
    cout << "~a = " << (int)b << endl;
    cout << "~a + 1 = " << (int)(b + 1) << endl;
    
    int c = 0;
    cout << "~c = " << ~c << endl;
    
    return 0;
}

判断题

  1. 取反操作(~)会将所有二进制位翻转。 ( )
  2. 对于无符号字符，~5的结果是250。 ( )
  3. ~0的结果是-1（对于有符号整数）。 ( )

选择题 4. 假设是8位无符号整数，~0的结果是（ ）。
A. 0
B. 1
C. 255
D. 256

  1. 对于有符号整数x，-x的位运算表示是（ ）。
    A. ~x
    B. ~x + 1
    C. x ^ 0xFFFFFFFF
    D. x & 0xFFFFFFFF

题目4：移位运算(<<, >>)应用

#include <iostream>
using namespace std;

int main() {
    int a = 13;  // 二进制1101
    
    cout << "a = " << a << endl;
    cout << "a << 1 = " << (a << 1) << endl;
    cout << "a << 2 = " << (a << 2) << endl;
    cout << "a >> 1 = " << (a >> 1) << endl;
    cout << "a >> 2 = " << (a >> 2) << endl;
    
    // 特殊案例
    int b = -8;
    cout << "-8 >> 1 = " << (b >> 1) << endl;
    
    return 0;
}

判断题

  1. 左移1位相当于乘以2（在无溢出的情况下）。 ( )
  2. 右移1位对于正整数相当于除以2并向下取整。 ( )
  3. 对于负数，右移操作是算术右移（符号位扩展）。 ( )

选择题 4. 13 << 2的计算结果是（ ）。
A. 26
B. 39
C. 52
D. 65

  1. 表达式1 << n的结果是（ ）。
    A. n
    B. 2n
    C. 2^n
    D. n^2

题目5：x & (x-1)技巧应用

#include <iostream>
using namespace std;

int countOnes(int n) {
    int count = 0;
    while (n) {
        n = n & (n - 1);
        count++;
    }
    return count;
}

bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

int main() {
    cout << "countOnes(7) = " << countOnes(7) << endl;
    cout << "countOnes(8) = " << countOnes(8) << endl;
    cout << "isPowerOfTwo(8) = " << isPowerOfTwo(8) << endl;
    cout << "isPowerOfTwo(7) = " << isPowerOfTwo(7) << endl;
    return 0;
}

判断题

  1. n & (n-1)可以将n的最低位的1变为0。 ( )
  2. 如果n & (n-1) == 0，则n是2的幂。 ( )
  3. countOnes函数统计n的二进制表示中1的个数。 ( )

选择题 4. 对于n=12（二进制1100），n & (n-1)的结果是（ ）。
A. 4
B. 8
C. 11
D. 13

  1. 这个算法统计1的个数的时间复杂度是（ ）。
    A. O(1)
    B. O(log n)
    C. O(n)
    D. O(二进制中1的个数)

题目6：lowbit操作(x & -x)

#include <iostream>
using namespace std;

int lowbit(int x) {
    return x & -x;
}

void printLowbit(int n) {
    cout << n << " 的二进制: ";
    for (int i = 7; i >= 0; i--) {
        cout << ((n >> i) & 1);
    }
    cout << ", lowbit = " << lowbit(n) << endl;
}

int main() {
    printLowbit(12);  // 00001100
    printLowbit(10);  // 00001010
    printLowbit(8);   // 00001000
    printLowbit(7);   // 00000111
    return 0;
}

判断题

  1. lowbit操作返回x最低位的1所代表的数值。 ( )
  2. 对于任意正整数x，lowbit(x)一定是2的幂。 ( )
  3. 如果x是奇数，lowbit(x)总是1。 ( )

选择题 4. lowbit(12)的结果是（ ）。
A. 1
B. 2
C. 4
D. 8

  1. 表达式x & -x的原理基于（ ）。
    A. 补码表示法
    B. 原码表示法
    C. 反码表示法
    D. 移码表示法

题目7：检查特定位((s>>i) & 1)

#include <iostream namespace std;

bool checkBit(int s, int i) {
    return (s >> i) & 1;
}

void printBinary(int n) {
    for (int i = 7; i >= 0; i--) {
        cout << checkBit(n, i);
    }
    cout << endl;
}

int main() {
    int s = 89;  // 二进制01011001
    
    cout << s << " 的二进制: ";
    printBinary(s);
    
    cout << "第0位: " << checkBit(s, 0) << endl;
    cout << "第2位: " << checkBit(s, 2) << endl;
    cout << "第4位: " << checkBit(s, 4) << endl;
    cout << "第6位: " << checkBit(s, 6) << endl;
    
    return 0;
}

判断题

  1. (s >> i) & 1可以检查s的第i位是否为1。 ( )
  2. 位编号从0开始，0是最低位。 ( )
  3. 表达式(s >> i) & 1等价于(s & (1 << i)) != 0。 ( )

选择题 4. 对于s=89（二进制01011001），第4位的值是（ ）。
A. 0
B. 1
C. 4
D. 8

  1. 要检查s的第i位是否为0，正确的表达式是（ ）。
    A. (s >> i) & 1 == 0
    B. ~((s >> i) & 1)
    C. (s >> i) | 0
    D. (s << i) & 1

题目8：设置特定位(S | (1<<i))

#include <iostream>
using namespace std;

int setBit(int s, int i) {
    return s | (1 << i);
}

int clearBit(int s, int i) {
    return s & ~(1 << i);
}

int toggleBit(int s, int i) {
    return s ^ (1 << i);
}

int main() {
    int s = 5;  // 二进制0101
    
    cout << "原数: " << s << " (0101)" << endl;
    cout << "设置第2位: " << setBit(s, 2) << " (0111)" << endl;
    cout << "清除第0位: " << clearBit(s, 0) << " (0100)" << endl;
    cout << "切换第1位: " << toggleBit(s, 1) << " (0111)" << endl;
    
    return 0;
}

判断题

  1. s | (1 << i)将s的第i位置1。 ( )
  2. s & ~(1 << i)将s的第i位清0。 ( )
  3. s ^ (1 << i)在s的第i位为0时置1，为1时清0。 ( )

选择题 4. 将数字5（二进制0101）的第3位置1，结果是（ ）。
A. 5
B. 7
C. 13
D. 15

  1. 下列哪组操作可以将s的第i位设置为b（b为0或1）？（ ）
    A. s = (s & ~(1 << i)) | (b << i)
    B. s = s | (b << i)
    C. s = s ^ (b << i)
    D. s = s & (b << i)

题目9：综合应用1 - 子集枚举

#include <iostream>
using namespace std;

int main() {
    int n = 3;  // 集合有3个元素
    int total = 1 << n;  // 2^3 = 8个子集
    
    cout << "集合 {1,2,3} 的所有子集：" << endl;
    for (int mask = 0; mask < total; mask++) {
        cout << "{ ";
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {  // 检查第i位是否为1
                cout << (i + 1) << " ";
            }
        }
        cout << "}" << endl;
    }
    
    return 0;
}

判断题

  1. 1 << n计算2的n次方，表示子集总数。 ( )
  2. mask的二进制表示中，1表示选择对应元素。 ( )
  3. 循环会生成所有可能的子集，包括空集。 ( )

选择题 4. 当n=3时，循环变量mask的取值范围是（ ）。
A. 0-2
B. 0-3
C. 0-7
D. 0-8

  1. 条件mask & (1 << i)检查的是（ ）。
    A. mask的第i位是否为1
    B. mask是否等于i
    C. mask是否能被2^i整除
    D. mask是否大于2^i

题目10：综合应用2 - 状态压缩

#include <iostream>
using namespace std;

int main() {
    // 状态压缩示例：3个开关的状态
    int state = 0;  // 初始全关，二进制000
    
    // 打开第0个和第2个开关
    state |= (1 << 0);  // 设置第0位
    state |= (1 << 2);  // 设置第2位
    
    cout << "当前状态: " << state << " (二进制";
    for (int i = 2; i >= 0; i--) {
        cout << ((state >> i) & 1);
    }
    cout << ")" << endl;
    
    // 检查第1个开关是否打开
    if (state & (1 << 1)) {
        cout << "开关1已打开" << endl;
    } else {
        cout << "开关1已关闭" << endl;
    }
    
    // 切换第2个开关状态
    state ^= (1 << 2);
    cout << "切换后状态: " << state << endl;
    
    return 0;
}

判断题

  1. 状态压缩使用整数的二进制位表示多个布尔状态。 ( )
  2. state |= (1 << i)可以打开第i个开关。 ( )
  3. state ^= (1 << i)可以切换第i个开关的状态。 ( )

选择题 4. 初始state=0，执行state |= (1<<0); state |= (1<<2);后，state的值是（ ）。
A. 1
B. 3
C. 5
D. 7

  1. 要关闭第i个开关，正确的操作是（ ）。
    A. state |= (1 << i)
    B. state &= ~(1 << i)
    C. state ^= (1 << i)
    D. state = state >> i
  1. 评测队列
  2. 服务状态
  3. Online User
  4. Language
  5. 兼容模式
  6. 主题
  2. 陕ICP备2025061476号
  3. Powered by BitWorld DD