26.5 移位运算 – 数字的快速倍增

“移位运算是计算机中最快的运算之一，”我兴奋地说，”左移一位相当于乘以2，右移一位相当于除以2，这可比普通的乘除法快多了！”

26.5.1 快速计算2的幂

题目描述： 小明在学习2的幂次方时，发现用移位运算可以快速计算。请你帮他写一个程序，输入一个数n，输出2的n次方。

输入格式： 输入一个整数 n（0≤n≤30）。

输出格式： 输出2的n次方。

样例输入：

10

样例输出：

1024

代码实现：

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    // 1左移n位就是2的n次方
    int r = 1 << n;
    
    cout << r << endl;
    
    return 0;
}

算法解析：

1. 1的二进制是1
2. 左移n位相当于在后面添加n个0
3. 例如：1 << 3 = 1000(二进制) = 8(十进制) = 2³
4. 这比使用循环或pow函数计算要快得多

26.5.2 快速除以2

题目描述： 在游戏中，角色每次受到特殊攻击，生命值会减半（向下取整）。给定初始生命值和受到攻击的次数，计算最终的生命值。

输入格式： 第一行输入初始生命值 hp（1≤hp≤10000）。第二行输入受到攻击的次数 n（0≤n≤20）。

输出格式： 输出最终的生命值。

样例输入：

100
3

样例输出：

12

代码实现：

#include <iostream>
using namespace std;

int main() {
    int h, n;
    cin >> h >> n;
    
    // 右移n位相当于除以2的n次方（向下取整）
    int f = h >> n;
    
    cout << f << endl;
    
    return 0;
}

算法解析：

1. 100的二进制是1100100
2. 右移3位：1100100 >> 3 = 1100 = 12
3. 相当于100 / 8 = 12.5，向下取整为12
4. 右移运算自动实现了向下取整的效果

26.5.3 设置标志位

题目描述： 现在我们学会了左移运算，可以回过头来看一个更实用的例子。在游戏编程中，我们经常用一个整数的不同位来表示不同的状态。比如用第0位表示是否有红钥匙，第1位表示是否有蓝钥匙，第2位表示是否有黄钥匙。现在小明初始状态是0（没有任何钥匙），他依次获得了一些钥匙，请输出他最终的状态值。

输入格式： 第一行是一个整数 n（1≤n≤10），表示获得钥匙的次数。接下来 n 行，每行一个整数（0、1或2），表示获得的钥匙类型（0-红色，1-蓝色，2-黄色）。

输出格式： 输出一个整数，表示最终的状态值。

样例输入：

3
0
2
1

样例输出：

7

代码实现：

#include <iostream>
using namespace std;

int main() {
    int n;
    int s = 0;  // 初始状态，没有任何钥匙
    
    cin >> n;
    for(int i = 0; i < n; i++) {
        int key;
        cin >> key;
        // 使用左移和或运算设置对应的位
        // 1 << key 将1左移key位，得到对应位置的标志
        s = s | (1 << key);
    }
    
    cout << s << endl;
    
    return 0;
}

算法解析：

1. 初始状态是0，二进制表示为000
2. 获得红钥匙(0)：s | (1<<0) = 000 | 001 = 001
3. 获得黄钥匙(2)：s | (1<<2) = 001 | 100 = 101
4. 获得蓝钥匙(1)：s | (1<<1) = 101 | 010 = 111 = 7
5. 最终状态111表示拥有所有三把钥匙