Day7 位运算与复杂度综合（重制版·10题）

范围：常用位运算结论、无符号整数边界和循环次数分析；不涉及图搜索。

第 1 题

执行 int x=44; cout<<(x&(x-1));，输出为（ {{ select(1) }} ）。

• $40$
• $42$
• $43$
• $44$

第 2 题

表达式 40 & -40 的十进制值是（ {{ select(2) }} ）。

• $1$
• $4$
• $8$
• $32$

第 3 题

数组 7,4,7,9,4 中只有一个数出现一次，其余均出现两次。将所有元素按位异或，结果是（ {{ select(3) }} ）。

• $0$
• $4$
• $7$
• $9$

第 4 题

对正整数 x，判断它是否为 $2$ 的整数次幂的正确条件是（ {{ select(4) }} ）。

• (x & (x-1)) == 0
• (x | (x-1)) == 0
• (x & 1) == 0
• (x ^ (x-1)) == 0

第 5 题

假设 unsigned char 占 $8$ 位，执行 unsigned char x=250; x=x+10; cout<<(int)x;，输出为（ {{ select(5) }} ）。

• $0$
• $4$
• $6$
• $260$

第 6 题

下面程序段中 cnt++ 的执行次数关于 $n$ 的时间复杂度是（ ）。

for (int i=1; i<=n; i*=2)
    for (int j=0; j<i; ++j) cnt++;

{{ select(6) }}

• $O(\log n)$
• $O(n)$
• $O(n\log n)$
• $O(n^2)$

程序：逐次删除最低位的 1

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int cnt = 0, sum = 0;
    while (n) {
        sum += n & -n;
        n &= n - 1;
        ++cnt;
    }
    cout << cnt << " " << sum;
    return 0;
}

第 7 题

输入 13 时，程序输出（ {{ select(7) }} ）。

• 2 12
• 3 13
• 3 7
• 4 13

第 8 题

循环执行次数等于原始输入的（ {{ select(8) }} ）。

• 二进制位数
• 二进制中 $1$ 的个数
• 最大二进制位权
• 十进制位数

第 9 题

输入 16 时，程序输出（ {{ select(9) }} ）。

• 1 16
• 4 16
• 5 31
• 16 1

第 10 题

若对每个 $1\le x\le n$ 都执行一次上述 while 循环，总时间复杂度的上界是（ {{ select(10) }} ）。

• $O(\log n)$
• $O(n)$
• $O(n\log n)$
• $O(n^2)$