当前位置：首页 > news >正文

位运算的基本概念+通过 Brian Kernighan算法计算 lowbit 实现的奇技淫巧 python

news 来源：原创 2025/6/7 2:32:36

引入

判断奇偶

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

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

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

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

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

位运算概念

在这里插入图片描述

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

在这里插入图片描述

进入正题

~~介绍奇技淫巧环节~~

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)

举一反三

求大于等于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：那么right-1是不是一定在【left，right】内
right-1 = 00101100
right = right & (right-1) = 00101100(抹去了最右边的1，即lowbit)
再下去倘若left=right，则直接return right
若left<right：那么right-1是不是一定在【left，right】内
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 再 & 的操作简化成抹掉最右侧的 1，极致的 “骚操作”

总结

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

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

目录

引入

判断奇偶

位运算概念

进入正题

Brian Kernighan 算法

lowbit 介绍

判断幂

举一反三

牛刀小试

汉明重量

总结

相关文章：