使用位操作了解 python 中的二进制加法-解网

问：

我正在寻找这个问题的解决方案：

给定两个整数和，返回两个整数之和，而不使用运算符和。（输入限制：<= a， b <=ab+--10001000)

在所有这些解决方案中，我都在努力理解为什么这些解决方案在评估时超过最大 32 位时会这样做 [请参阅下面的代码]。~(a ^ mask)a0x7fffffffa + b

def getSum(self, a: int, b: int) -> int:
    
    # 32bit mask
    mask = 0xFFFFFFFF # 8Fs = all 1s for 32 bits

    while True: 
        # Handle addition and carry 
        a, b = (a ^ b) & mask, ((a & b) << 1) & mask
        if b == 0:
            break

    max_int = 0x7FFFFFFF

    print("A:", a)
    print("Bin A:", bin(a))
    print("Bin M:", bin(mask))
    print("  A^M:", bin(a ^ mask))
    print("~ A^M:", bin(~(a ^ mask)))
    print("  ~ A:", bin(~a))

    return a if a < max_int else ~(a ^ mask)

我不明白为什么我们在返回答案时需要再次掩码？a

退出循环时，它已经被屏蔽了：。那么，如果设置为 for，为什么我们不能这样做呢？a = (a ^ b) & mask~a32nd bit1a

我看了 Python 中 Bit-wise NOT 的含义，理解了 ~ 操作，但没有明白。

的输出、。正确返回：a = -12b = -8-20

A: 4294967276
Bin A: 0b11111111111111111111111111101100
Bin M: 0b11111111111111111111111111111111
  A^M: 0b10011
~ A^M: -0b10100
  ~ A: -0b11111111111111111111111111101101

Python 位操作

a从技术上讲，不是无符号的。Python 中的所有整数都是有符号的，但它是一个正值，因为你从不做任何事情来使它为负数。如果您使用的是具有 32 位整数的语言，则设置位 31 会使其为负数。这在 Python 中不会发生。我可以根据需要添加任意数量的位，并且它将保持为正数。我们看不到符号位，我们无法设置符号位。

答：

2赞 relent95 2/19/2023 #1

您忘记指定原始问题的约束，即和在 [-1000， 1000] 中。该代码是 C 或 Java 实现的端口，它假定并且是 4 字节签名整数。而且我不确定你是否正确理解和代码。前者添加第 i 位，并忽略每个位的进位。后者获得所有被忽略的进位。abab(a ^ b)(a & b) << 1ab

要点是，最后一个操作是处理负整数。反转的下 32 位并保留其他上位。因此，结果的按位 NOT 保留了的下 32 位，并反转了其他上位。因为的上位（下 32 位除外）都为零，所以只是将所有上位设置为 1。它相当于，可读性更强。~(a ^ mask)a ^ maska~(a ^ mask)aa~(a ^ mask)a | ~mask

请参阅以下示例。

print(~(0xffffffff ^ 0xffffffff)) # This will output -1.
print(~(0xfffffffe ^ 0xffffffff)) # This will output -2.
print(~0xffffffff) # This will output -4294967296(-0x100000000).

是的，你对第一个问题是正确的，因为的上位（下 32 位除外）都为零。对于第二个问题，你所说的“作为一个整体”，是指？那么不，它不是在计算二的补码。它将表示负整数作为二进制补码（32 位有符号整数）的正 Python 整数转换为负 Python 整数。最后，如果您认为所有变量都表示为位列表，则更具可读性。a ^ mask~(a ^ mask)a | ~mask

0赞 Parth 2/19/2023

所以你的意思是给 2s 补码吗？然后，将 2s 补码转换为有符号数？这究竟是如何/为什么工作的？从定性上讲，我有点明白 ~ 会将前 32 位后所有剩余的 0 翻转为 1（并把前 32 位还给我们，因为我们之前对它们进行了 XOR 处理）。但是这是否也翻转了符号位，以便 Python 现在知道这是一个负数？a ^ mask~(a^ mask)

0赞 Parth 2/19/2023

如果可能的话，你能给我看一个写出 1（比如 8 位）的例子来说明它是如何工作的吗？或者有没有任何地方我可以阅读这篇文章，并举例写出 1 和 0 中的数字并显示工作原理？我仍然不明白为什么更具可读性（其他人在对 leet 代码的评论中也提到了这一点）a | ~mask

0赞 Parth 2/21/2023 #2

这里有一个有用的链接 - 区分 2 的补码负数和相应的正数。

由于边界，我们永远不会有正数溢出。（数字仅在 [-1000， 1000] 之间）。所以我们知道，当设置第 32 位时，它是因为它是一个负数。

请注意，如果我们的范围也允许正数加法溢出，那么就无法区分正数设置第 32 位和负数设置。

因此，我们保留直到前 32 位的位，并向其添加无限前导 1，以便 Python 知道这是一个负数。~(a ^ mask)a

如果你看一下，它已经是 -20 的 2s 补码表示。但现在 Python 将其视为正数。因此，我们需要告诉 Python 使用 .Bin A~(a ^ mask)

上一个：React Native Text 不受容器视图限制的限制

下一个：AttributeError： module 'torch' has no attribute 'hstack' [closed]

使用位操作了解 python 中的二进制加法

Understanding binary addition in python using bit manipulation

评论

评论