登录以参加训练计划

课件

位运算基础

基本位运算符

• & (按位与): 两位都为1时结果为1
• | (按位或): 任一位为1时结果为1
• ^ (按位异或): 两位不同时结果为1
• ~ (按位取反): 0变1, 1变0
• << (左移): 二进制位向左移动
• >> (右移): 二进制位向右移动

常用技巧

// 判断奇偶
if (n & 1) // n为奇数

// 交换两个数
a ^= b;
b ^= a;
a ^= b;

// 找落单的数字
int ans = 0;
for (int i = 0; i < n; i++) {
    cin >> x;
    ans ^= x;
}

快速幂

快速幂可以将 $a^b$ 的时间复杂度从 $O(b)$ 降低到 $O(\log b)$

long long pow_mod(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

核心思想

利用 $a^b = (a^{b/2})^2$ 和二进制分解:

• $b$ 的二进制表示决定了哪些幂需要乘入结果
• 每一步将指数右移一位，底数平方

高低位交换

对于 32 位整数，高低位交换:

unsigned int swap_high_low(unsigned int n) {
    unsigned int high = (n >> 16) & 0xFFFF;
    unsigned int low = n & 0xFFFF;
    return (low << 16) | high;
}

复杂度分析

• 普通幂运算: $O(b)$
• 快速幂: $O(\log b)$
• 位运算异或: $O(1)$ per operation