位运算与循环移位在算法题中的高效应用

一、问题背景：最大二进制和类题型

在某些算法题中（如最大二进制和），给定一个 n×n 的 0/1 矩阵，允许对每行进行循环移位，以获得按行拼接后的最大十进制和。

常规方法每行枚举所有移位，时间复杂度高达 O(n³)，不适合处理大规模数据。

---

二、位运算基本技巧

1. 二进制转十进制

int val = 0;
for (int bit : row) {
    val = (val << 1) | bit;
}

2. 创建掩码以保留 n 位

int mask = (1 << n) - 1;

3. 实现循环左移

rowVal = ((rowVal << 1) | (rowVal >> (n - 1))) & mask;

说明：

• rowVal << 1 左移一位；
• rowVal >> (n - 1) 提取最高位；
• | 实现循环补位；
• & mask 清除多余高位。

---

三、完整实现示例（C++）

int maxRowValue(int rowVal, int n) {
    int mask = (1 << n) - 1;
    int maxVal = rowVal;
    for (int i = 1; i < n; ++i) {
        rowVal = ((rowVal << 1) | (rowVal >> (n - 1))) & mask;
        maxVal = max(maxVal, rowVal);
    }
    return maxVal;
}

配合输入解析函数：

int parseRow(const string& line) {
    int val = 0;
    for (char ch : line) {
        if (ch == '0' || ch == '1') {
            val = (val << 1) | (ch - '0');
        }
    }
    return val;
}

---

四、时间复杂度分析

每行进行 n 次循环移位，每次操作为 O(1)，共 O(n²)。

与字符串旋转/数组移动实现相比：

• 常规数组操作：O(n³)
• 滑动窗口法：O(n²)
• 位运算法：O(n²) 且常数低，速度快

---

五、常见变种与注意点

• 若输入较长（如 n=64），可使用 unsigned long long 存储位图；
• 注意不同平台下位运算边界处理（尤其是左移溢出）。

---

六、结语与扩展思考

位运算是处理二进制矩阵类题目的高效利器，能显著优化时间与空间性能。掌握掩码与循环移位技巧，在位图压缩、图形、字符串哈希等场景同样大有用武之地。

推荐进一步练习：

• LeetCode 476. 数字的补数
• LeetCode 201. 数字范围按位与
• 位图去重与集合表示问题

后续我们还将介绍滑动窗口法与动态编程在类似问题中的应用。