位运算技巧

【位运算】是直接对整数二进制位进行操作的技术，在ACM竞赛中经常用于优化算法、降低时间复杂度和空间复杂度。掌握位运算技巧可以帮助我们编写更高效的代码。

基本位运算符

C++中常用的位运算符包括：

常用位运算技巧

1. 判断奇偶性

使用&1来判断一个数是否为奇数：

// 检查n是否为奇数
bool isOdd(int n) {
    return n & 1;  // 等价于 n % 2 != 0
}

2. 乘除2的幂

使用位移操作可以高效实现乘以或除以2的幂：

// 乘以2的k次方，等价于 n * (2^k)
int multiplyByPowerOf2(int n, int k) {
    return n << k;
}

// 除以2的k次方，等价于 n / (2^k)
int divideByPowerOf2(int n, int k) {
    return n >> k;
}

3. 获取二进制表示中的特定位

获取第i位（从0开始，最低位为第0位）：

// 获取n的第i位（0或1）
int getBit(int n, int i) {
    return (n >> i) & 1;
}

4. 设置或清除特定位

// 将n的第i位设置为1
int setBit(int n, int i) {
    return n | (1 << i);
}

// 将n的第i位设置为0
int clearBit(int n, int i) {
    return n & ~(1 << i);
}

// 将n的第i位取反
int flipBit(int n, int i) {
    return n ^ (1 << i);
}

5. 计算二进制中1的个数

// 计算n的二进制表示中1的个数
int countOnes(int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

// C++内置函数（更高效）
int countOnes(int n) {
    return __builtin_popcount(n);  // GCC编译器特有
}

6. 获取最低位的1

// 获取n二进制表示中最低位的1
// 例如：n = 12 (1100)，结果为 4 (100)
int lowestOneBit(int n) {
    return n & -n;  // 或写作 n & (~n + 1)
}

7. 去除最低位的1

// 去除n二进制表示中的最低位1
// 例如：n = 12 (1100)，结果为 8 (1000)
int removeLowestOneBit(int n) {
    return n & (n - 1);
}

8. 判断是否为2的幂

// 判断n是否为2的幂
bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

高级应用

1. 子集枚举

使用位运算可以方便地枚举一个集合的所有子集：

void subsets(vector<int>& nums) {
    int n = nums.size();
    int subsetCount = 1 << n;  // 2^n个子集

    for (int mask = 0; mask < subsetCount; mask++) {
        cout << "子集 {";
        for (int i = 0; i < n; i++) {
            // 检查第i位是否为1
            if (mask & (1 << i)) {
                cout << nums[i] << " ";
            }
        }
        cout << "}" << endl;
    }
}

2. 状态压缩DP

状态压缩动态规划中，我们用整数的二进制位表示状态：

// 旅行商问题(TSP)的状态压缩DP示例
int tsp(vector<vector<int>>& dist) {
    int n = dist.size();
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));

    // 初始状态：只访问城市0
    dp[1][0] = 0;

    // 枚举所有状态
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            // 如果u不在当前集合中，跳过
            if (!(mask & (1 << u))) continue;

            // prev_mask表示不包含u的状态
            int prev_mask = mask ^ (1 << u);

            // 如果prev_mask为0，说明mask只包含u
            if (prev_mask == 0) continue;

            // 尝试从其他城市到达u
            for (int v = 0; v < n; v++) {
                if (v == u) continue;
                if (prev_mask & (1 << v)) {
                    dp[mask][u] = min(dp[mask][u], dp[prev_mask][v] + dist[v][u]);
                }
            }
        }
    }

    // 计算从最后一个城市回到起点的距离
    int finalMask = (1 << n) - 1;  // 所有城市都已访问
    int minDist = INT_MAX;
    for (int u = 1; u < n; u++) {
        if (dp[finalMask][u] != INT_MAX) {
            minDist = min(minDist, dp[finalMask][u] + dist[u][0]);
        }
    }

    return minDist;
}

3. 快速幂运算

使用位运算优化快速幂算法：

// 计算(a^b) % mod
long long quickPow(long long a, long long b, long long mod) {
    long long result = 1;
    a %= mod;

    while (b > 0) {
        // 如果当前二进制位为1，将a累乘到结果中
        if (b & 1) {
            result = (result * a) % mod;
        }

        // 处理下一位
        a = (a * a) % mod;
        b >>= 1;
    }

    return result;
}

4. 位域数据结构

可以使用位运算来实现高效的集合操作：

class BitSet {
private:
    vector<unsigned int> bits;
    int size;

public:
    BitSet(int n) {
        size = n;
        // 每个unsigned int可以存储32个位
        bits.resize((n + 31) / 32, 0);
    }

    // 设置第i位为1
    void set(int i) {
        if (i >= size) return;
        bits[i / 32] |= (1u << (i % 32));
    }

    // 清除第i位
    void clear(int i) {
        if (i >= size) return;
        bits[i / 32] &= ~(1u << (i % 32));
    }

    // 检查第i位是否为1
    bool test(int i) {
        if (i >= size) return false;
        return (bits[i / 32] & (1u << (i % 32))) != 0;
    }

    // 位运算操作
    BitSet& operator&=(const BitSet& other) {
        for (int i = 0; i < bits.size(); i++) {
            bits[i] &= other.bits[i];
        }
        return *this;
    }

    BitSet& operator|=(const BitSet& other) {
        for (int i = 0; i < bits.size(); i++) {
            bits[i] |= other.bits[i];
        }
        return *this;
    }

    BitSet& operator^=(const BitSet& other) {
        for (int i = 0; i < bits.size(); i++) {
            bits[i] ^= other.bits[i];
        }
        return *this;
    }
};

位运算的应用场景

1. 优化算术运算：使用位运算代替乘除法
2. 集合操作：高效实现集合的交、并、补等操作
3. 状态压缩：在动态规划中表示状态
4. 权限管理：使用位掩码表示权限组合
5. 位图排序：处理大量整数的排序和去重
6. 散列函数：构造高效的散列函数
7. 编码算法：在压缩和加密算法中应用

典型例题

例题1：找出唯一出现一次的数

问题：给定一个数组，其中除了一个数出现一次外，其他数都出现两次，找出这个只出现一次的数。

解法：利用异或操作的性质 a ^ a = 0 和 a ^ 0 = a

int findSingle(vector<int>& nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

例题2：格雷码生成

问题：生成n位二进制的格雷码序列。

解法：利用位运算转换二进制码到格雷码

vector<int> grayCode(int n) {
    vector<int> result;
    int size = 1 << n;  // 2^n

    for (int i = 0; i < size; i++) {
        // 将二进制转换为格雷码：G(i) = i ^ (i >> 1)
        result.push_back(i ^ (i >> 1));
    }

    return result;
}

注意事项

1. 【可读性问题】：位运算代码往往难以理解，建议添加详细注释
2. 【溢出问题】：位移操作可能导致溢出，尤其是左移
3. 【符号问题】：右移符号位的处理在不同编译器可能不同
4. 【跨平台问题】：整数大小在不同平台可能不同，影响位运算结果
5. 【优化权衡】：位运算优化有时会降低代码可读性，需要权衡

常见位运算公式

• 交换两数：a ^= b; b ^= a; a ^= b;
• 取绝对值（仅限32位整数）：(n ^ (n >> 31)) - (n >> 31);
• 取二进制的最低位1：n & -n;
• 去掉二进制末尾的1：n & (n - 1);
• 二进制中1的个数：__builtin_popcount(n);
• 整数的平均值：(a & b) + ((a ^ b) >> 1);
• 判断两个数符号是否相同：(a ^ b) >= 0;

练习题目推荐

1. LeetCode 136 - Single Number
2. LeetCode 78 - Subsets
3. LeetCode 89 - Gray Code
4. LeetCode 191 - Number of 1 Bits
5. LeetCode 338 - Counting Bits

总结

位运算是ACM竞赛中的一项强大工具，恰当地应用位运算可以：

• 优化算法的时间和空间复杂度
• 简化状态表示和状态转移
• 实现高效的集合操作

然而，位运算也可能使代码变得难以理解，因此在实际使用时需权衡效率和可读性。建议在刚开始学习时，先掌握基本的位运算技巧，然后逐步应用到实际问题中，熟练掌握后再尝试更复杂的应用。