「@Author:Runsen」
❝编程的本质来源于算法,而算法的本质来源于数学,编程只不过将数学题进行代码化。「---- Runsen」 ❞
总结下之前基础的内容
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就是去掉二级制的最后一个。每执行一次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)
的意思
>>> 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
文字版:指定位置
还有很多的复杂的位运算,Runsen是小白的水平,真的看不懂怎么多。
下面是尝试使用
>>> 7&(~0<<2) #111 将最右边的2位清零
4 #100
>>> 7&(~0<<1) #111 将最右边的1位清零
6 #110
>>> (2>>5)&1 #101 获取 5 的第 2 位值
0
编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 '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
给定一个整数,编写一个函数来判断它是否是 2 的幂次方。
输入: 1
输出: true
解释: 20 = 1
输入: 16
输出: true
解释: 24 = 16
因此最快的方法就是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
给定一个非负整数 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。 ❞
[1]传送门~: https://github.com/MaoliRUNsen/runsenlearnpy100
- END -