六十一、深入学习位运算

「@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