跳到主要内容

【题单】位运算（基础/性质/拆位/试填/恒等式/贪心/脑筋急转弯）

来源: 分享丨【题单】位运算（基础/性质/拆位/试填/恒等式/贪心/脑筋急转弯）

前置知识: 分享｜从集合论到位运算，常见位运算技巧分类总结！

创建题单的原因: 容斥原理划分型 DP【力扣周赛 393】的Q3 我直接被秒杀!, Q4也是位运算(我看都没有看); 因此学习位运算十分有必要!

3315. 构造最小位运算数组 II (lowbit)

基础题

与或（AND/OR）的性质

异或（XOR）的性质

拆位 / 贡献法

477. 汉明距离总和
1863. 找出所有子集的异或总和再求和可以做到 $O(n)$ 时间 (看不懂思密达)
2425. 所有数对的异或和 1622 可以做到 $O(n+m)$ 时间
2275. 按位与结果大于零的最长组合 1642
1835. 所有数对按位与结果的异或和 1825 也有恒等式做法
2505. 所有子序列和的按位或（会员题）

LogTrick 技巧

LogTrick: 问一个数组的所有子数组的元素 AND/OR/lcm/gcd 的值为 k (或者是某个可能含有子数组的表达式的值) 的最近元素/子数组个数(二分right-left/三分(滑窗))

LogTrick利用AND/OR/lcm/gcd的性质, 使得时间复杂度为 $O(n\log{n})$

视频讲解可以看周赛400 Q4: Q4-3171. 找到按位或最接近 K 的子数组

原地写法: 三种基于 logTrick 的方法：二分 / 三指针 / 维护个数（Python/Java/C++/Go）
额外维护一个数组: 利用或运算的性质 + 通用模板（Python/Java/C++/Go）
3097. 或值至少为 K 的最短子数组 II 1891
2411. 按位或最大的最小子数组长度 1938
3209. 子数组按位与值为 K 的数目 ~2100
3171. 找到按位或最接近 K 的子数组
1521. 找到最接近目标值的函数值 2384 做法同 3171 题
898. 子数组按位或操作

试填法

恒等式

思维题（贪心、脑筋急转弯等）

其它

int getSum(int a, int b) {
    int tmp = (a & b) << 1;         // 记得要左移一位!
    int res = a ^ b;                // 相加(不理会进位的)
    while (tmp) {                   // 是否要进位
        int cache = tmp;
        tmp = (res & tmp) << 1;     // 进位
        res = res ^ cache;          // 相加(不理会进位的)
    }
    return res;
}
C++

请作者喝奶茶:

本文遵循

CC 4.0 BY-SA 版权协议, 转载请标明出处

Loading Comments...

0%

基础题
与或（AND/OR）的性质
异或（XOR）的性质
拆位 / 贡献法
LogTrick 技巧
试填法
恒等式
思维题（贪心、脑筋急转弯等）
其它