六十一、深入学习位运算
共 2610字，需浏览 6分钟
·
2020-12-20 07:23
「@Author：Runsen」
❝编程的本质来源于算法，而算法的本质来源于数学，编程只不过将数学题进行代码化。「---- Runsen」
❞
总结下之前基础的内容
& 按位与 将两个操作数对应的每一位进行逻辑与操作，满足：1&1=1，1&0=0，0&1=0，0&0=0，
| 按位或是将两个操作数对应的每一位进行逻辑或操作，满足：1|0=1，0|1=1，1|1=1，0|0=0，
^ 按位异或，将两个操作数对应的每一位进行逻辑异或操作，满足
1^1=0，0^0=0，1^0=1，0^1=1~ 按位取反是将单个操作数对应的每一位取反，
~1=0，~0=1
下面就是这篇博客重点内容，总结于极客时间的算法面试通过40讲的位运算的内容。
下面就是学习记录的笔记
交换两数
交换两数如果不想额外的空间消耗，就可以用位运算来实现，这个是以前不知道的。
>>> x =1
>>> y = 2
>>> x = x^y
>>> y = x^y
>>> x = x^y
>>> x
2
>>> y
1
判断奇数和偶数
x & 1 == 1 or == 0其实是来判断奇数还是偶数，原理就是按照位“与”运算的原则，如果两个值相应的位置都为1也就是上下都为1的时候，那么该结果就是1，如果有一个不是1，那么就是0。
因为 & 1这里固定了，二级制的原因，奇数那么最后一个一定是1，偶数最后一个一定是0。
>>> x = 2 #10
>>> y = 3 #11
>>> x & 1
0
>>> y & 1
1
因此使用x & 1 == 1 or == 0判断奇数或者偶数和 x%2 == 0等价。
清除最低位的1
这个道理和上面的一样，清除最低位的1就是去掉二级制的最后一个。每执行一次x = x&(x-1)，会将x用二进制表示时最右边的一个1变为0，因为x-1将会将该位(x用二进制表示时最右边的一个1)变为0。
>>> x = 7
>>> bin(x)
'0b111'
>>> x & (x-1)
6
>>> bin(6)
'0b110'
>>> x = x & (x-1)
>>> x & (x-1)
4
>>> bin(4)
'0b100'
x&(-x)
x&(-x)的意思
当x是一个偶数与它的负值向与时，结果是能被这个偶数整除的最大的2的n次幂，x&(-x)返回x与2^64的最大公约数，即x最多能被n个2整除就返回2^n。
当x是一个奇数与它的负值向与时结果一定是1，则返回得到最低的1
>>> 7 & -7 #111 7二进制最低是1的位数是1
1
>>> 6 & -6 # 6与2^64最大公约数是2
2
>>> 4 & -4 # 4与2^64最大公约数是4
4
>>> 8& -8 # 8与2^64最大公约数是8
8
>>> 9 & -9 # 1001
1
文字版：指定位置
将 x 最右边的 n 位清零：x &(~0< 获取 x 的第 n 位值（0或者1）：(x>>n)&1 获取x的第n位的幂值：x&(1< 仅将第 n 位置为1：x|(1< 仅将第 n 位置为0：x&(~(1< 将 x 最高位至第 n 位（含）清零：x&((1< 将 第n位 至第 0 位（含）清零：x&(~((1<<(n+1))-1))
还有很多的复杂的位运算，Runsen是小白的水平，真的看不懂怎么多。
下面是尝试使用
>>> 7&(~0<<2) #111 将最右边的2位清零
4 #100
>>> 7&(~0<<1) #111 将最右边的1位清零
6 #110
>>> (2>>5)&1 #101 获取 5 的第 2 位值
0
Leetcode 191 ：统计位1的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
最快的方法就是转化为字符串的，然后通过遍历判断的方式或者count的方法求出1的个数。记得需要进行bin操作。
class Solution:
def hammingWeight(self, n: int) -> int:
index = 0
for i in str(bin(n)):
if i == "1":
index = index + 1
return index
但是Runsen学习的是位运算，因此也要学会位运算的方法。方法也很简单：每一次右移一位，判断是 奇数还是偶数，奇数那么就加一，因为位数最后一个肯定是1。
class Solution:
def hammingWeight(self, n: int) -> int:
count = 0
while n != 0:
#x%2 != 0等价
if n&1 != 0:
count = count + 1
n = n >> 1
return count
在Leetcode上，Runsen也看了一个官方的最快的解决的方法。就是遍历数字的 32 位。如果某一位是 1，将计数器加一。其实就是mask左移一位，比如第一次是0001（这里有32位），那么下一次就是0010。
class Solution:
def hammingWeight(self, n: int) -> int:
res = 0
mask = 1
for i in range(32):
if n & mask:
res +=1
mask = mask << 1
return res
Leetcode231：2的幂次方问题
给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
输入: 1
输出: true
解释: 20 = 1
输入: 16
输出: true
解释: 24 = 16
若，且 为自然数（即 为 的幂），则一定满足以下条件：恒有 ，这是为什么，Runsen告诉大家，这是因为：的位运算只有一个1，那么通过 ，把那个1拔了出来，然后全部都是000000000了。
因此最快的方法就是return n > 0 and n & (n - 1) == 0，还有一种的方法是通过math.log2最后求出来是不是整数。但是返回的是浮点数，比如是2.0 。所以这种方法就pass。最后一种就是通过不断对2取模运算。最后看看是不是1。
class Solution(object):
def isPowerOfTwo(self, n):
"""
:type n: int
:rtype: bool
"""
if n == 0:
return False
while n % 2 == 0:
n = n / 2
return n == 1
Leetcode338：比特位计数问题
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:
输入: 2
输出: [0,1,1]
示例 2:
输入: 5
输出: [0,1,1,2,1,2]
最快速的方法就是直接count进行计数就可以了。
class Solution:
def countBits(self, num: int) -> List[int]:
res = []
for i in range(num+1):
count = bin(i).count("1")
res.append(count)
return res
这题还可以使用位运算或者动态规划的方法，Runsen的动态规划真的是烂到家。
思路：动态规划
观察：
十进制0： 二进制0
十进制1： 二进制1
十进制2： 二进制10
十进制3： 二进制11
十进制4： 二进制100
十进制5： 二进制101
二进制中，乘以2相当于左移一位，1的个数不会改变；由于偶数的二进制形式结尾一定是0，所以一个偶数加1变为奇数，只会将其结尾的0变为1；
所以状态转移方程为：
$dp(i) = dp(i//2)$ 若i为偶数；这里//2保证是整数，防止溢出
$dp(i) = dp(i-1)+1$ 若i为奇数；
边界条件：dp(0) = 0
class Solution:
def countBits(self, num: int) -> List[int]:
dp = [0] * (num+1)
for i in range(1,num+1):
if i % 2 == 0:
dp[i]=dp[i//2]
else:
dp[i]=dp[i-1]+1
return dp
最后说下位运算：dp[i] = dp[i>>1] + (i&1)，这里 i>>1代表前一个二进制位的次数, i&1代表i的末尾是否为1，因此可以继续将代码变得更简洁。
class Solution:
def countBits(self, num: int) -> List[int]:
dp = [0]
for i in range(1, num + 1):
dp.append(dp[i>>1] + (i&1))
return dp
❝本文已收录 GitHub，传送门~[1] ，里面更有大厂面试完整考点，欢迎 Star。
❞
Reference
传送门~: https://github.com/MaoliRUNsen/runsenlearnpy100
更多的文章
点击下面小程序
- END -