引入

判断奇偶

假设你不知道位运算为何物：你怎么判断奇偶呢？

n = int(input())
if n % 2 == 0:
    print(f"{n}是偶数")
else:
    print(f"{n}是奇数")

• 1
• 2
• 3
• 4
• 5

但你知道了位运算中的与运算，你可以做到：

n = int(input())
if n & 1:
    print(f"{n}是奇数")
else:
    print(f"{n}是偶数")

• 1
• 2
• 3
• 4
• 5

那什么是位运算呢？请往后看

位运算概念

异或运算可点此进入查看：详细介绍

进入正题

介绍奇技淫巧环节

Brian Kernighan 算法

实现：提取一个二进制数字最右边的1 即lowbit

假设一个8位的二进制数：
n=10110100
~n=01001011 （~为取反符）
~n+1 = 01001100 （取反加一即为求n的补码即-n）
观察到 ：
要取的1左边：n与（~n+1）相反，
要取的1右边：n与（~n+1）都为0
怎么实现1的左右两边都变为0呢？答案是 与运算&
n & (~n+1) 就能得到 00000100 即lowbit
又（~n+1）就是-n
所以 lowbit = n & （-n）

lowbit 介绍

这很重要，下面有大用

判断幂

判断一个整数是不是2的幂

2 的幂 https://leetcode.cn/problems/power-of-two/

举几个例子：
0001 = 2^0 ； 0010 = 2^1 ； 0100 = 2^2 ······
所以2的幂即二进制表示中只有一位是1
那如果 n==lowbit（n），就可以说n为2的幂

借助Brian Kernighan 算法可以一行代码轻松实现
code如下：

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and n == (n & -n)

• 1
• 2
• 3

举一反三

求大于等于n的2的幂

举个例子：
n=39 转为二进制 即00100111
答案应该是01000000 即64
所以大于等于n的2的幂就是 取最左边的1 再左边的那一位为1，其余位取0

题外话：
判断一个整数是不是3的幂（与位运算无关，感兴趣的话可以想想）

3的幂 https://leetcode.cn/problems/power-of-three/description/

牛刀小试

数字范围按位与 https://leetcode.cn/problems/bitwise-and-of-numbers-range/description/

返回【left，right】区间所有元素按位与运算的结果

直接暴力O(n)会超时，那应该怎么做呢？
请看好，不要眨眼

假设right=00101101
倘若left=right，则直接return right ，没问题。
若left right-1 = 00101100
right = right & (right-1) = 00101100(抹去了最右边的1，即lowbit)
再下去倘若left=right，则直接return right
若left right-1 = 00101011
right = right & (right-1) = 00101000(抹去了最右边的1，即lowbit)
······直到left=right，返回right
是的，这是一个while循环，right里有几个1，就做几次。
这实现了近似O(1)的时间复杂度

汉明重量

这就是Brian Kernighan 算法的另一个重要作用：
计算一个二进制表示中1的数量（即汉明重量，Hamming Weight）。
这个算法比逐位检查的方法更高效，因为它只遍历输入整数中1的个数次。

算法原理：

该算法的核心思想是：每次将整数 n 和 n−1 进行按位与运算，可以消除 n 的二进制表示中最右边的1。
通过重复这一过程，直到 n 变为0，我们可以统计出 n 中1的个数。

code如下：

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        while left < right:
            right -= right & (-right)
        return right

• 1
• 2
• 3
• 4
• 5

真是米奇妙妙屋啊 太妙了！这值得好好体会
将 -1 再 & 的操作简化成抹掉最右侧的 1，极致的 “骚操作”

总结

位运算实现速度非常快，仅仅次于赋值操作，需要好好掌握。

如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢