Chuoer47's Blog

Appearance

本文转载自力扣讨论区，作者：灵茶山艾府（endlesscheng）。 原文链接：https://leetcode.cn/circle/discuss/dHn9Vk/

位运算题单 位运算题目 位运算基础 灵茶山艾府 灵神 灵神题单

推荐先阅读：从集合论到位运算，常见位运算技巧分类总结！

一、基础题 ​

用位运算代替数组操作：

反转二进制数：

二、异或（XOR）的性质 ​

本质是模 2 剩余系的加法。

另见 数据结构题单 中的「§6.4 0-1 字典树（异或字典树）」。

三、与或（AND/OR）的性质 ​

AND 的数越多，结果越小。

OR 的数越多，结果越大。

AND/OR LogTrick ​

LogTrick 入门教程，包含原地写法，以及额外维护一个列表的写法。

如果你不熟悉原地去重算法，可以看 26. 删除有序数组中的重复项，我的题解。

模板：

py
# 对于每个右端点 i，计算所有子数组的或值，打印这些或值的分布范围（子数组左端点范围）
# 时间复杂度 O(nlogU)，其中 U = max(nums)
def logTrick(nums: List[int]) -> None:
    or_left = []  # (子数组或值，最小左端点)
    for i, x in enumerate(nums):
        # 计算以 i 为右端点的子数组或值
        for p in or_left:
            p[0] |= x  # **根据题目修改**
        # x 单独一个数作为子数组
        or_left.append([x, i])

        # 原地去重（相同或值只保留最左边的）
        idx = 1
        for j in range(1, len(or_left)):
            if or_left[j][0] != or_left[j - 1][0]:
                or_left[idx] = or_left[j]
                idx += 1
        del or_left[idx:]

        print(i, x)
        for k, (or_val, left) in enumerate(or_left):
            right = or_left[k + 1][1] - 1 if k < len(or_left) - 1 else i
            # 对于左端点在 [left, right]，右端点为 i 的子数组，OR 值都是 or_val
            print(left, right, or_val)

logTrick([4, 2, 1, 5])
java
class Solution {
    // 对于每个右端点 i，计算所有子数组的或值，打印这些或值的分布范围（子数组左端点范围）
    // 时间复杂度 O(nlogU)，其中 U = max(nums)
    public void logTrick(int[] nums) {
        List<int[]> orLeft = new ArrayList<>(); // (子数组或值，最小左端点)
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            // 计算以 i 为右端点的子数组或值
            for (int[] p : orLeft) {
                p[0] |= x; // **根据题目修改**
            }
            // x 单独一个数作为子数组
            orLeft.add(new int[]{x, i});

            // 原地去重（相同或值只保留最左边的）
            int m = 1;
            for (int j = 1; j < orLeft.size(); j++) {
                if (orLeft.get(j)[0] != orLeft.get(j - 1)[0]) {
                    orLeft.set(m++, orLeft.get(j));
                }
            }
            orLeft.subList(m, orLeft.size()).clear();

            System.out.println(i + " " + x);
            for (int k = 0; k < m; k++) {
                int orVal = orLeft.get(k)[0];
                int left = orLeft.get(k)[1];
                int right = k < m - 1 ? orLeft.get(k + 1)[1] - 1 : i;
                // 对于左端点在 [left, right]，右端点为 i 的子数组，OR 值都是 orVal
                System.out.println(left + " " + right + " " + orVal);
            }
        }
    }

    public static void main(String[] args) {
        new Solution().logTrick(new int[]{4, 2, 1, 5});
    }
}
cpp
// 对于每个右端点 i，计算所有子数组的或值，打印这些或值的分布范围（子数组左端点范围）
// 时间复杂度 O(nlogU)，其中 U = max(nums)
void logTrick(vector<int>& nums) {
    vector<pair<int, int>> or_left; // (子数组或值，最小左端点)
    for (int i = 0; i < nums.size(); i++) {
        int x = nums[i];
        // 计算以 i 为右端点的子数组或值
        for (auto& [or_val, _] : or_left) {
            or_val |= x; // **根据题目修改**
        }
        // x 单独一个数作为子数组
        or_left.emplace_back(x, i);

        // 原地去重（相同或值只保留最左边的）
        int m = 1;
        for (int j = 1; j < or_left.size(); j++) {
            if (or_left[j].first != or_left[j - 1].first) {
                or_left[m++] = or_left[j];
            }
        }
        or_left.resize(m);

        cout << i << " " << x << endl;
        for (int k = 0; k < m; k++) {
            auto [or_val, left] = or_left[k];
            int right = k + 1 < m ? or_left[k + 1].second - 1 : i;
            // 对于左端点在 [left, right]，右端点为 i 的子数组，OR 值都是 or_val
            cout << left << " " << right << " " << or_val << endl;
        }
    }
}

int main() {
    vector<int> nums = {4, 2, 1, 5};
    logTrick(nums);
    return 0;
}
go
// 对于每个右端点 i，计算所有子数组的或值，打印这些或值的分布范围（子数组左端点范围）
// 时间复杂度 O(nlogU)，其中 U = max(nums)
func logTrick(nums []int) {
    type pair struct{ or, left int } // 子数组或值，最小左端点
    orLeft := []pair{}
    for i, x := range nums {
        // 计算以 i 为右端点的子数组或值
        for j := range orLeft {
            orLeft[j].or |= x // **根据题目修改**
        }
        // x 单独一个数作为子数组
        orLeft = append(orLeft, pair{x, i})

        // 原地去重（相同或值只保留最左边的）
        idx := 1
        for j := 1; j < len(orLeft); j++ {
            if orLeft[j].or != orLeft[j-1].or {
                orLeft[idx] = orLeft[j]
                idx++
            }
        }
        orLeft = orLeft[:idx]

        fmt.Println(i, x)
        for k, p := range orLeft {
            orVal := p.or
            left := p.left
            right := i
            if k < len(orLeft)-1 {
                right = orLeft[k+1].left - 1
            }
            // 对于左端点在 [left, right]，右端点为 i 的子数组，OR 值都是 orVal
            fmt.Println(left, right, orVal)
        }
    }
}

func main() {
    logTrick([]int{4, 2, 1, 5})
}

注：下面的部分题目，可以用滑动窗口+栈做到更优的 O(n) 时间复杂度，见 原理讲解（方法二）。

GCD LogTrick ​

四、拆位 / 贡献法 ​

十进制拆位

五、试填法 ​

六、恒等式 ​

七、线性基 ​

讲解

模板（最大异或和）：

py
class XorBasis:
    # n 为值域最大值 U 的二进制长度，例如 U=1e9 时 n=30
    def __init__(self, n: int):
        self.b = [0] * n

    def insert(self, x: int) -> None:
        b = self.b
        # 从高到低遍历，保证计算 max_xor 的时候，参与 XOR 的基的最高位（或者说二进制长度）是互不相同的
        for i in range(len(b) - 1, -1, -1):
            if x >> i:  # 由于大于 i 的位都被我们异或成了 0，所以 x >> i 的结果只能是 0 或 1
                if b[i] == 0:  # x 和之前的基是线性无关的
                    b[i] = x  # 新增一个基，最高位为 i
                    return
                x ^= b[i]  # 保证每个基的二进制长度互不相同
        # 正常循环结束，此时 x=0，说明一开始的 x 可以被已有基表出，不是一个线性无关基

    def max_xor(self) -> int:
        b = self.b
        res = 0
        # 从高到低贪心：越高的位，越必须是 1
        # 由于每个位的基至多一个，所以每个位只需考虑异或一个基，若能变大，则异或之
        for i in range(len(b) - 1, -1, -1):
            if res ^ b[i] > res:  # 手写 max 更快
                res ^= b[i]
        return res
java
class XorBasis {
    private final int[] b;

    // n 为值域最大值 U 的二进制长度，例如 U=1e9 时 n=30
    public XorBasis(int n) {
        b = new int[n];
    }

    public void insert(int x) {
        // 从高到低遍历，保证计算 maxXor 的时候，参与 XOR 的基的最高位（或者说二进制长度）是互不相同的
        for (int i = b.length - 1; i >= 0; i--) {
            if ((x >> i) > 0) { // 由于大于 i 的位都被我们异或成了 0，所以 x >> i 的结果只能是 0 或 1
                if (b[i] == 0) { // x 和之前的基是线性无关的
                    b[i] = x; // 新增一个基，最高位为 i
                    return;
                }
                x ^= b[i]; // 保证每个基的二进制长度互不相同
            }
        }
        // 正常循环结束，此时 x=0，说明一开始的 x 可以被已有基表出，不是一个线性无关基
    }

    public int maxXor() {
        int res = 0;
        // 从高到低贪心：越高的位，越必须是 1
        // 由于每个位的基至多一个，所以每个位只需考虑异或一个基，若能变大，则异或之
        for (int i = b.length - 1; i >= 0; i--) {
            res = Math.max(res, res ^ b[i]);
        }
        return res;
    }
}
cpp
class XorBasis {
    vector<int> b;

public:
    // n 为值域最大值 U 的二进制长度，例如 U=1e9 时 n=30
    XorBasis(int n) : b(n) {}

    void insert(int x) {
        // 从高到低遍历，保证计算 max_xor 的时候，参与 XOR 的基的最高位（或者说二进制长度）是互不相同的
        for (int i = b.size() - 1; i >= 0; i--) {
            if (x >> i) { // 由于大于 i 的位都被我们异或成了 0，所以 x >> i 的结果只能是 0 或 1
                if (b[i] == 0) { // x 和之前的基是线性无关的
                    b[i] = x; // 新增一个基，最高位为 i
                    return;
                }
                x ^= b[i]; // 保证每个基的二进制长度互不相同
            }
        }
        // 正常循环结束，此时 x=0，说明一开始的 x 可以被已有基表出，不是一个线性无关基
    }

    int max_xor() {
        int res = 0;
        // 从高到低贪心：越高的位，越必须是 1
        // 由于每个位的基至多一个，所以每个位只需考虑异或一个基，若能变大，则异或之
        for (int i = b.size() - 1; i >= 0; i--) {
            res = max(res, res ^ b[i]);
        }
        return res;
    }
};
go
type xorBasis []int

// n 为值域最大值 U 的二进制长度，例如 U=1e9 时 n=30
func newXorBasis(n int) xorBasis {
    return make(xorBasis, n)
}

func (b xorBasis) insert(x int) {
    // 从高到低遍历，保证计算 maxXor 的时候，参与 XOR 的基的最高位（或者说二进制长度）是互不相同的
    for i := len(b) - 1; i >= 0; i-- {
        if x>>i == 0 { // 由于大于 i 的位都被我们异或成了 0，所以 x>>i 的结果只能是 0 或 1
            continue
        }
        if b[i] == 0 { // x 和之前的基是线性无关的
            b[i] = x // 新增一个基，最高位为 i
            return
        }
        x ^= b[i] // 保证每个基的二进制长度互不相同
    }
    // 正常循环结束，此时 x=0，说明一开始的 x 可以被已有基表出，不是一个线性无关基
}

func (b xorBasis) maxXor() (res int) {
    // 从高到低贪心：越高的位，越必须是 1
    // 由于每个位的基至多一个，所以每个位只需考虑异或一个基，若能变大，则异或之
    for i := len(b) - 1; i >= 0; i-- {
        res = max(res, res^b[i])
    }
    return
}

八、思维题 ​

贪心、脑筋急转弯等。

九、其他 ​

关联题单 ​

  1. 数据结构题单 中的「§6.4 0-1 字典树（异或字典树）」。
  2. 链表、二叉树与回溯 中的部分回溯题目，可以用二进制搜索解决。

算法题单 ​

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

如果你发现有题目可以补充进来，欢迎评论反馈。