一道和位运算有关的高考数学题

发表于 更新于

题目

在做数学二轮复习的时候，碰到了这样一道数学题。

在这道数学题中，我们发现n被定义为若干个2的幂之和，很容易想到这是一个二进制和十进制之间的转换过程，而w(n)为这个二进制数的各项数位之和，带着这样的前置知识，我们接着做题。

PS：举例如下

1
2
3
14 = (2^3 * 1) + (2^2 * 1) + (2^1 * 1) + (2^0 * 0)
w(n) = 1 + 1 + 1 + 0
Bin(n) = 1110

解答

A选项

w(2n)相较于w(n)，是将原十进制数乘上了2，根据数学知识，我们可以得到这实际上是对原数n进行了左移一位的位运算，题目没有溢出的背景设定，故左移位运算后各位数字和不变。

PS：举例如下

1
2
3
4
5
6
7
13 = (2^3 * 1) + (2^2 * 1) + (2^1 * 0) + (2^0 * 1)
w(n) = 1 + 1 + 0 + 1
Bin(n) = 01101

28 = (2^4 * 1) + (2^3 * 1) + (2^2 * 0) + (2^1 * 1) + (2^0 * 0)
w(2n) = 1 + 1 + 0 + 1 + 0
Bin(2n) = 11010 = Bin(n) << 1

D选项

第(n+1)个内存位代指的值为2^n

1
2
3
4
1 = 2 ^ 0  // 第1个 0001
2 = 2 ^ 1  // 第2个 0010
4 = 2 ^ 2  // 第3个 0100
8 = 2 ^ 3  // 第4个 1000

w(2^n - 1)相当于将第(n+1)个内存位后方的n个位置全部变化为1。

1
2
3
4
0 = 2 ^ 0 - 1 // 第1个 0000
1 = 2 ^ 1 - 1 // 第2个 0001
3 = 2 ^ 2 - 1 // 第3个 0011
7 = 2 ^ 3 - 1 // 第4个 0111

故各项位数之和为n

C选项

w(8n + 5)相当于先做左移三位，再对数+5
w(4n + 3)相当于先做左移二位，再对数+3 

1
2
000XXXXX << 3 + 5 == XXXXX000 + 5 == XXXXX101
000XXXXX << 2 + 3 == 0XXXXX00 + 3 == 0XXXXX11

由于XXXXX位数和不变，而剩下的位数又都为2

故它们的值相等

B选项

w(2n + 3)仅仅向左移动了一位，而进行+3操作时会涉及到第一位和第二位两位操作，故不能确定这次位运算对位数和的影响，等式不一定成立。

位运算

符号 描述 运算规则
& 与 两个位都为1时，结果才为1
| 或 两个位都为0时，结果才为0
^ 异或 两个位相同为0，相异为1
~ 取反 0变1，1变0
<< 左移 各二进位全部左移若干位，高位丢弃，低位补0
>> 右移 各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）

刚才的解题中，我们所运用的主要是左右移动的知识，这是计算机中其它的位运算方法，合理利用位运算，可以加快我们的计算机程序的运算效率。

以下是一些位运算小技巧：

判断奇偶性

N & 1，当结果为1，N为奇数，反之。
因为奇数的最后一位为1，偶数为0.

交换两个数

1
2
3
4
5
6
7
void Swap(int &a, int &b){
    if (a != b){
        a ^= b; // a现在所有的位上都储存了a和b“是否相反“这一信息
        b ^= a; // b现在使用这个信息，如果相反，那么交换，现在b为a
        a ^= b; // b现在就是a，而a储存了“相反信息”，进行异或运算后a为b
    }
}