Python位运算技巧

"""
位运算技巧 — 直接操作整数二进制位
速度快，适合状态压缩、权限标记、性能关键代码
"""


def get_bit(n: int, p: int) -> int: return (n >> p) & 1
def set_bit(n: int, p: int) -> int: return n | (1 << p)
def clear_bit(n: int, p: int) -> int: return n & ~(1 << p)
def toggle_bit(n: int, p: int) -> int: return n ^ (1 << p)


def count_set_bits(n: int) -> int:
"""Brian Kernighan 算法：每次消除最低位的 1"""
c = 0
while n: n &= n - 1; c += 1
return c


def is_power_of_two(n: int) -> bool:
"""2 的幂：二进制只有一个 1"""
return n > 0 and (n & (n - 1)) == 0


def find_single_number(nums: list) -> int:
"""出现一次的数，其他成对出现（a ^ a = 0, a ^ 0 = a）"""
r = 0
for n in nums: r ^= n
return r


def swap(a: int, b: int) -> tuple:
"""不用临时变量交换两个整数"""
a ^= b; b ^= a; a ^= b; return a, b


def find_missing(arr: list, n: int) -> int:
"""0..n 中缺失的那个数，利用 XOR 性质"""
x = 0
for i in range(n + 1): x ^= i
for v in arr: x ^= v
return x


def subset_bitmask(nums: list) -> list:
"""用二进制位掩码枚举所有子集"""
res = []
for mask in range(1 << len(nums)):
res.append([nums[i] for i in range(len(nums)) if mask & (1 << i)])
return res


def demo():
n = 0b101101
print(f"原始: {bin(n)}")
print(f"get(2)={get_bit(n,2)}, set(4)={bin(set_bit(n,4))}")
print(f"clear(5)={bin(clear_bit(n,5))}, toggle(0)={bin(toggle_bit(n,0))}")
print(f"count 1s: {count_set_bits(n)}, 2的幂 16:{is_power_of_two(16)} 18:{is_power_of_two(18)}")
print(f"单身数: {find_single_number([4,1,2,1,2])}")
print(f"swap(3,5): {swap(3,5)}, 缺失: {find_missing([0,1,3,4], 4)}")
print(f"位掩码子集 [1,2]: {subset_bitmask([1,2])}")


if __name__ == "__main__":
demo()