位运算

分享｜从集合论到位运算，常见位运算技巧分类总结！ - 力扣（LeetCode）

压缩表示

集合用二进制表示，从高到低第i位为1表示i在集合中。如{0,2,3}可以表示为1101，压缩成一个数字 13

集合与集合

集合的交并补差

集合与元素

“<<”代表左移，相当于乘2 ^ i

“>>”代表右移， 相当于除2 ^ i

补集~s

全集 (1<<n) - 1

属于 (s >> i) & 1 = 1

不属于 (s >> i) & 1 = 0

添加元素 s | (1 << i)

删除元素 s & ~ (1 << i) (比如i = 2 变成0100 取反变成 1011 然后和s并起来 这样才可以保证 只删除目标位而不影响其他位)

删除最小元素 s & (s - 1) ((s - 1)可以使得最低位的1变为0 并且其右边的所有0变为1 然后&s 使得 最低位的1以及后面的所有0全部变成0)

lowbit = s & (-s)

     s = 101100
    ~s = 010011
(~s)+1 = 010100 // 根据补码的定义，这就是 -s   最低 1 左侧取反，右侧不变
s & -s = 000100 // lowbit

部分库函数

s.bit_count() # 集合大小
s.bit_length() # 二进制长度
(s&-s).bit_length()-1 # 集合中的最小元素

遍历集合

for i in range(n):
    # 如果i在s中
    if (s >> i) & 1:
        pass

枚举集合

# 从空集枚举到全集U
for s in range(1 << n):
    pass

# 设集合为s 从大到小枚举s的所有非空子集sub
sub = s
while sub:
    # pass
    
    sub = (sub - 1) & s # （如何证明？）
"""
跳过非子集的集合！
意思是，把10100 的最低位1变0，它的后面有两位 00， 都是0。这时候按照普通二进制，会把这两个 00 都变成 11，如果按照压缩版，就只把原来集合里有的 1 变成 1 （因为求的是子集），其余的还是 0，原有的集合是 10101，最后两位是 01，所以只保留 01。综合起来就是 10100 先变 10000，然后保留 01，变成 10001。

这样做的效果是从 10100 直接跳到 10001，把中间的 10011 和10010 忽略掉了（普通减法顺序是 10100 - 10011 - 10010 - 10001），因为10011 和 10010不是有效的子集。
"""
# 所有子集
while sub:
    sub = (sub - 1) & s
    if sub == s:
        break

例题

136. 只出现一次的数字 - 力扣（LeetCode）

一个数字出现一次 其他数字出现两次 用异或操作 因为a^0 = a a ^ a = 0 所以两个一样的数异或就为0

并且a ^ b ^ c 满足交换律

即所有的数都是相同的凑成一对 变为0 然后剩下的目标数字^0 = 目标 输出即可

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ret = 0
        for x in nums:
            ret ^= x
        return ret

137. 只出现一次的数字 II - 力扣（LeetCode）

一个数字出现三次 目标数字出现三次

所以每个比特位的1的数量必定是3的倍数 不是3的倍数的 就是ans的比特位

注意python这种对有符号整型和无符号整型不区分的语言 需要特判最高位

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ret = [0] * 33
        for x in nums:
            for i in range(32):
                ret[i] += ((x>>i) & 1)
        ans = 0
        for i in range(32):
            if ret[i] % 3 != 0:
                if i == 31:
                    ans -= (1 << i)
                else:
                    ans |= (1 << i)
        return ans

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        int ret[32] = {0};
        for (auto x : nums)
        {
            for (int i = 0; i < 32; i++)
            {
                ret[i] += ((x >> i) & 1);
            }
        }
        for (int i = 0; i < 32; i++)
        {
            if (ret[i] % 3 != 0)
                ans += (1 << i);
        }
        return ans;
    }
};

260. 只出现一次的数字 III - 力扣（LeetCode）

每个元素只出现两次 有两个只出现一次的数 要找出这两个数

由于这两个数不同 必然有一个(以上)的比特位不同 那么就求这个比特位

然后把所有在这个比特位上 是1 的 异或到一起 （包含所有 这个比特位上是1 的两个两个的数 和 这个比特位上是1 的目标数） 把所有这个比特位上是0 的异或到一起…

注意取 lowbit lowbit = a & (-a)

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xorsum = 0
        for x in nums:
            xorsum ^= x
        ans1 = ans2 = 0
        lb = xorsum & (-xorsum)
        for x in nums:
            if lb & x:
                ans1 ^= x
            else:
                ans2 ^= x

        return [ans1, ans2]

78. 子集 - 力扣（LeetCode）

子集的形式与二进制数非常相似 可以考虑用二进制来写

1 < (1 << n)就是小于2的n次方

i>>j 就是把i这个二进制数往右移动j位

比如0001 移动0位是1 移动1位是0 移动两位是0 三位是0

就是用这种方式 代表每个位置上的数选或不选

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        rets = []
        i = 0
        while i < (1<<n):
            ret = []
            for j in range(n):
                if (i >> j) & 1 == 1:
                    ret.append(nums[j])
            rets.append(ret)
            i += 1
        return rets

421. 数组中两个数的最大异或值 - 力扣（LeetCode）

前缀哈希表

mask每次是00000-10000-11000-11100-11110-11111 每次让他第i位变成1 则其前i位都为1 后i + 1位都为0

new_ans = ans|=(1 << i) 就是假设ans的第i位为1 其余位不变

然后对每个x 先和mask与 得到 前缀 重点 这里是得到前缀 因为mask前i位为1 后为0 则与后 x前i位不变 后i+1位为0 实现取前缀的操作

假设此时进行到了第 k个x (即nums[k]) seen里面有nums的前k - 1个数的前缀（后缀为0）如果x ^ new_ans 在seen里找到了 说明ans的这一位为1是可以的 因为：

x ^ new_ans 如果在seen里找到了 说明seen里一定有一个数 y 满足 x ^ y == new_ans （因为a ^ b = c <=> a ^ c = b <，=> b ^ c = a）那就说明 有两个数的异或值 可以为new_ans （也即在保留前i - 1位的情况下 第i位可以为1） 如果没有找到的话 就说明不存在两个数异或为new_ans 那ans就不变 （即该位为0不变）否则ans = new_ans 这样 每一位都尽量取1 最后就是最大值

主要用了 用mask与 取前缀排除后缀的影响 不是只比较第i位 而是比较前i位

设new_ans 去异或 然后在set里查找

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        ans = mask = 0
        high_bit = max(nums).bit_length() - 1
        for i in range(high_bit, -1, -1):
            mask = 1 |= (1 << i) 
            seen = set()
           	new_ans = ans |= (1 << i)
            for x in nums:
                x &= mask
                if (x ^ new_ans) in seen():
                    ans = new_ans
                    break
                seen.add(x)
        return ans

前缀树

建前缀树 要尽量往相反方向走

每个数进入add函数 建树 扩展树的枝叶

每个数进入check函数 如果当前位是1 则尽量往0的枝叶走（left）如果左边走不了再走右 如果当前位是0 尽量往1走（right）

每次走到相反位 x = x * 2 + 1 相同位 x = x * 2 因为是从高往低位走的（从根往叶子走）

class Trie():
    def __init__(self):
        self.left = None
        self.right = None

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        root = Trie()
        high_bit = max(nums).bit_length() - 1
        
        def add(num: int):
            cut = root
            for k in range(high_bit, -1, -1):
                bit = (num >> k) & 1
                if bit == 0:
                    if cur.left is None:
                        cur.left = Trie()
                    cur = cur.left
                else:
                    if cur.right is None:
                        cur.right = Trie()
                    cur = cur.right
       	
        def check(num: int):
            cur = root
            x = 0
            for k in range(high_bit, -1, -1):
                bit = (num >> k) & 1
                if bit == 0:
                    if cur.right:
                        cur = cur.right
                        x = x * 2 + 1
                    else:
                        cur = cur.left
                        x = x * 2
                else:
                    if cur.left:
                        cur = cur.left
                        x = x * 2 + 1
                    else:
                        cur = cur.right
                        x = x * 2
            return x
         
        x = 0
        n = len(nums)
        for i in range(1, n):
            add(nums[i - 1])
            x = max(x, check(nums[i]))
        return x
            

2939. 最大异或乘积 - 力扣（LeetCode）

aa

两个位相同的话 x的该位就直接取反

两个位不同的话 总有一位为0 一位为1 如何取

注意到a = 12 和 b = 5 即 1100 和 0101 x第二位为0第三位为1 那么x如果是0010 即让x异或完a变成 0100 = 8 b变成1101 = 13 总和为21 如果x是1010 a = 0110 6 b = 1111 15 总和为21 其实也很好想 每个地方放1 不管放在哪 都会被加进去 在a第0位 放1 变成a + 1 + b 在b的第0位放1 也是a + b + 1 所以a + b 总和是不变的 这也是位运算的特殊之处

基本不等式 a + b > 2 sqrt(a * b) 要让a b尽量接近

如何让a b 尽量接近呢 由上分析 已经知道了 只需要考虑a 和b中 不相等的位 那这几位1是固定的 关键在于如何把1分配给a 和b 要让a b 尽量接近 如果a > b 就把最高位分配给a 剩余位 分配给b （因为最高的一位大于剩下最低位的和

然后考虑分配 a b 都小于2 ^ n 直接分 a b有一个 大于等于 2 ^ n的时候 那前面的部分是不可修改的 如果a b前面的位都相同 那就跟上面一样 分配后面的 否则 a > b 的话 那就把所有的1都分配给b

class Solution:
    def maximumXorProduct(self, a: int, b: int, n: int) -> int:
        if a < b:
            a, b = b, a
        mask = (1 << n) - 1 # 全为1的掩码
        # 取出第n位及其左边的数 不被x影响
        ax = a & ~mask
        bx = b & ~mask
        # 再来算右边的
        a &= mask
        b &= mask
        
        left = a ^ b # 可分配的位 （a^b 就是a和b的不同位）
        one = mask ^ left # 不用分配的位
        # 把右边的 无需分配的 先加到左边
        ax |= one
        bx |= one
        
        if left > 0 and ax == bx:
            high_bit = 1 << (left.bit_length() - 1)
            ax |= high_bit # 最高位给a
            left ^= high_bit # 除了最高位以外的其他位
        bx |= left # 给b （因为当left > 0 ax == bx的时候才需要把最高位给a  但是 其他的不管什么情况都是给b）
    	return ax * bx % (10 ** 9 + 7)