二进制

Jessica Gracewell2023-09-282023-09-28

二进制

二进制基础操作

二进制操作可以实现多种基础和高级的功能。下面我们将探讨几种基础的二进制操作。

交换两个数
在不使用额外变量的情况下，我们可以利用异或运算来交换两个数。异或运算有如下性质：任何数与0异或得到的都是它本身，任何数与它本身异或得到的都是0。

def swap_numbers(a, b):
    """
    使用异或运算交换两个数。
    a = a ^ b  # 第一步，a变量现在保存了a和b的异或结果
    b = a ^ b  # 第二步，由于a已经是a和b的异或结果，所以这一步b变为原来的a
    a = a ^ b  # 第三步，a变为原来的b
    """
    a = a ^ b
    b = a ^ b
    a = a ^ b
    return a, b

移除最后一个1
我们可以通过以下操作移除一个数二进制表示中的最后一个1。

def remove_last_one(n):
    """
    移除n的二进制表示中的最后一个1。
    使用n与n-1的与运算来移除最后一个1。
    """
    return n & (n - 1)

获取最后一个1
要获取一个数二进制表示中的最后一个1，我们可以使用以下操作：
def get_last_one(n):
"""
获取n的二进制表示中的最后一个1。
使用n与n-1的与运算结果与n的异或运算来得到最后一个1。
"""
return (n & (n - 1)) ^ n
常见题目与详解
在解决实际问题时，我们经常会用到上述的基础二进制操作。下面，我们将通过几个常见的算法题来进一步学习二进制操作。

Single Number
这道题目要求我们找到一个数组中唯一出现一次的元素，其它元素都出现两次。我们可以使用异或运算来解决这个问题。

def single_number(nums: List[int]) -> int:
    """
    找出数组中只出现一次的元素。
    利用异或运算的性质，将数组中的所有元素进行异或运算，最终的结果就是只出现一次的元素。
    """
    result = 0  # 初始化结果为0
    for num in nums:  # 遍历数组中的每个元素
        result ^= num  # 将元素与result进行异或运算
    return result  # 返回结果

Single Number II
这道题目要求我们找出数组中唯一出现一次的元素，其它元素都出现三次。我们可以统计每个位上1出现的次数，如果某个位上1出现的次数不能被3整除，那么只出现一次的那个数在这个位上的值一定是1。

def single_number_ii(nums: List[int]) -> int:
    """
    找出数组中只出现一次的元素。
    遍历32位整数的每一位，统计每一位上1出现的次数，最后根据1出现的次数还原出只出现一次的那个数。
    """
    result = 0  # 初始化结果为0
    for i in range(32):  # 遍历32位整数的每一位
        sum = 0  # 初始化sum为0，用于统计当前位上1出现的次数
        for num in nums:  # 遍历数组中的每个元素
            sum += (num >> i) & 1  # 统计当前位上1出现的次数
        result ^= (sum % 3) << i  # 根据1出现的次数还原出只出现一次的那个数
    return result if result < 2**31 else result - 2**32  # 处理负数的情况

Single Number III
这道题目要求我们找出数组中唯一出现一次的两个元素。我们可以先计算所有元素的异或结果，再根据异或结果中的任意一个为1的位将所有元素分为两组，每组各包含一个只出现一次的元素。

def single_number_iii(nums: List[int]) -> List[int]:
    """
    找出数组中只出现一次的两个元素。
    首先计算数组中所有元素的异或结果，然后根据异或结果中的任意一个为1的位将所有元素分为两组，
    每组各包含一个只出现一次的元素，最后分别计算两组元素的异或结果。
    """
    diff = 0  # 初始化diff为0，用于保存数组中所有元素的异或结果
    for num in nums:  # 计算数组中所有元素的异或结果
        diff ^= num
    diff &= -diff  # 获取diff中的最低位1
    res1, res2 = 0, 0  # 初始化两个结果变量
    for num in nums:  # 遍历数组中的每个元素，依据diff将元素分为两组
        if num & diff == 0:  # 第一组
            res1 ^= num
        else:  # 第二组
            res2 ^= num
    return [res1, res2]  # 返回两个只出现一次的元素

Number of 1 Bits
这道题目要求我们计算一个无符号整数的二进制表达式中数字位数为 ‘1’ 的个数。我们可以通过逐位检查或利用n&(n−1) 来快速移除最低位的1。

def hamming_weight(num: int) -> int:
    """
    计算一个无符号整数的二进制表达式中数字位数为 ‘1’ 的个数。
    使用 n & (n - 1) 来快速移除最低位的1，从而实现快速计数。
    """
    count = 0  # 初始化计数器为0
    while num:  # 循环直到num变为0
        num &= num - 1  # 利用 n & (n - 1) 来快速移除最低位的1
        count += 1  # 计数器加1
    return count  # 返回计数结果

Counting Bits
这道题目要求我们计算从 0 到 num 的所有数的二进制表达式中数字位数为 ‘1’ 的个数。我们可以利用动态规划的方法来解决这个问题。

def count_bits(num: int) -> List[int]:
    """
    对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
    使用动态规划的方法，状态转移方程为：res[i] = res[i & (i - 1)] + 1。
    """
    res = [0] * (num + 1)  # 初始化结果数组，长度为 num + 1
    for i in range(1, num + 1):  # 从1开始计算到num的每个数的二进制表达式中数字位数为 ‘1’ 的个数
        res[i] = res[i & (i - 1)] + 1  # 利用动态规划的状态转移方程计算 res[i]
    return res  # 返回结果数组

Reverse Bits
这道题目要求我们颠倒给定的 32 位无符号整数的二进制位。我们可以通过一位一位地颠倒来实现。

def reverse_bits(num: int) -> int:
    """
    颠倒给定的 32 位无符号整数的二进制位。
    通过逐位颠倒的方法，将num的每一位加到结果的对应位置。
    """
    res = 0  # 初始化结果为0
    power = 31  # 初始化剩余位数为31
    while num:  # 循环直到num变为0
        res += (num & 1) << power  # 将num的最低位加到res的对应位置
        num >>= 1  # num右移一位，即去掉最低位
        power -= 1  # 剩余位数减1
    return res  # 返回结果

Bitwise AND of Numbers Range
这道题目要求我们返回范围 [m,n] 内所有数字的按位与。我们可以通过找到 m 和 n 的公共前缀来解决这个问题。

def range_bitwise_and(m: int, n: int) -> int:
    """
    返回范围 [m, n] 内所有数字的按位与（包含 m, n 两端点）。
    通过找到 m 和 n 的公共前缀来实现。
    """
    shift = 0  # 初始化移位次数为0
    while m != n:  # 当m不等于n时进行循环
        m >>= 1  # m右移一位
        n >>= 1  # n右移一位
        shift += 1  # 记录移位次数
    return m << shift  # 将m左移shift位得到结果