如何将负位表示的数字转换为 python3 中的实际负 int 值？
How to convert negative bit-represented numbers to their actual negative int value in python3?
你好，我已经解决了这个leetcode问题https://leetcode.com/problems/single-number-ii。 objective是在O(n)时间内解决问题，0(1)space。我写的代码如下：
class Solution:
def singleNumber(self, nums: List[int]) -> int:
counter = [0 for i in range(32)]
result = 0
for i in range(32):
for num in nums:
if ((num >> i) & 1):
counter[i] += 1
result = result | ((counter[i] % 3) << i)
return self.convert(result)
#return result
def convert(self,x):
if x >= 2**31:
x = (~x & 0xffffffff) + 1
x = -x
return x
现在有趣的部分在 convert 函数中，因为 python 使用对象来存储 int 而不是 32 位字或其他东西，它不知道当我的 counter 的 MSB 设置为 1 时，结果为负。我通过将其转换为其 2 的补码并返回负值来处理该问题。
现在有人发布了他们的解决方案：
def convert(self, x):
if x >= 2**31:
x -= 2**32
return x
而且我不明白为什么会这样。我需要帮助来理解为什么这个减法有效。
这就是n位数字A的补码定义。
如果A是正数就用A的二进制码
如果A为负数，则使用2^n+A（或2^n-|A|）的二进制编码。此数字是您必须添加到 |A| 的数字得到 2^n（即 |A| 与 2^n 的补码，因此得名补码法）。
所以，如果你有一个用二进制补码编码的负数 B，它的代码中实际是 2^N+B。要得到它的值，你必须从 B.
中减去 2^N
补码还有许多其他定义（~A+1、~(A-1) 等），但这个是最有用的，因为它解释了为什么加有符号的补码与加法完全相同正数。该数字在代码中（如果为负则添加 2^32）并且加法结果将是正确的，前提是您忽略可能作为进位生成的 2^32（并且没有溢出）。这个算法属性是计算机中使用二进制补码的主要原因。
32 位有符号整数环绕每个 2**32，因此设置了符号位的正数（即 >= 2**31）与负数 2**32 具有相同的二进制表示] 少
Python 整数是无限大的。当您添加更多位时它们不会变为负数，因此二进制补码可能无法按预期工作。你可以用不同的方式处理底片。
def singleNumber(nums):
result = 0
sign = [1,-1][sum(int(n<0) for n in nums)%3]
for i in range(32):
counter = 0
for num in nums:
counter += (abs(num) >> i) & 1
result = result | ((counter % 3) << i)
return result * sign
这种二进制方法可以像这样优化和简化：
def singleNumber(nums):
result = 0
for i in range(32):
counter = sum(1 for n in nums if (n>>i)&1)
if counter > 0: result |= (counter % 3) << i
return result - 2*(result&(1<<31))
如果你喜欢一种衬里，你可以使用 functools 中的 reduce() 来实现它：
result = reduce(lambda r,i:r|sum(1&(n>>i) for n in nums)%3<<i,range(32),sum(n<0 for n in nums)%3*(-1<<32))
请注意，此方法将始终对数据进行 32 次传递，并将限制为 -2^31...2^31 范围内的数字。增加这个范围将系统地增加通过数字列表的次数（即使列表只包含小值）。此外，由于您没有在 i 循环之外使用 counter[i]，因此不需要列表来存储计数器。
您可以使用非常相似的方法（也可以在 O(n) 时间和 O(1) space 内响应）利用基数 3 而不是基数 2：
def singleNumber(nums):
result = sign = 0
for num in nums:
if num<0 : sign += 1
base3 = 1
num = abs(num)
while num > 0 :
num,rest = divmod(num,3)
rest,base3 = rest*base3, 3*base3
if rest == 0 : continue
digit = result % base3
result = result - digit + (digit+rest)%base3
return result * (1-sign%3*2)
这个的优点是它只会遍历列表一次（因此支持迭代器作为输入）。不限制取值范围，会尽可能少的执行嵌套while循环（根据每个取值的大小）
它的工作方式是在基数 3 表示中独立地添加数字并在不应用进位的情况下循环结果（逐位）。
例如：[ 16, 16, 32, 16 ]
Base10 Base 3 Base 3 digits result (cumulative)
------ ------ ------------- ------
16 121 0 | 1 | 2 | 1 121
16 121 0 | 1 | 2 | 1 212
32 2012 2 | 0 | 1 | 2 2221
16 121 0 | 1 | 2 | 1 2012
-------------
sum of digits % 3 2 | 0 | 1 | 2 ==> 32
while num > 0 循环处理数字。它最多 运行 log(V,3) 次，其中 V 是数字列表中最大的绝对值。因此它类似于基数 2 解决方案中的 for i in range(32) 循环，只是它始终使用尽可能小的范围。对于任何给定的值模式，该 while 循环的迭代次数将小于或等于一个常数，从而保留主循环的 O(n) 复杂性。
我进行了一些性能测试，实际上，base3 版本仅在值较小时比 base2 方法快。 base3 方法总是执行较少的迭代，但是当值很大时，由于模运算与按位运算的开销，它会损失总执行时间。
为了使 base2 解决方案始终比 base 3 方法更快，它需要通过反转循环嵌套（数字内的位而不是位内的数字）来优化其迭代：
def singleNumber(nums):
bits = [0]*len(bin(max(nums,key=abs)))
sign = 0
for num in nums:
if num<0 : sign += 1
num = abs(num)
bit = 0
while num > 0:
if num&1 : bits[bit] += 1
bit += 1
num >>= 1
result = sum(1<<bit for bit,count in enumerate(bits) if count%3)
return result * [1,-1][sign%3]
现在它每次都会胜过基数 3 的方法。作为一个附带的好处，它不再受值范围的限制，并将支持迭代器作为输入。请注意，位数组的大小可以视为常数，因此这也是一个 O(1) space 解决方案
但是，公平地说，如果我们对以 3 为底的方法应用相同的优化（即使用以 3 为底的列表 'bits'），它的性能在所有值大小上都排在前面：
def singleNumber(nums):
tribits = [0]*len(bin(max(nums,key=abs))) # enough base 2 -> enough 3
sign = 0
for num in nums:
if num<0 : sign += 1
num = abs(num)
base3 = 0
while num > 0:
digit = num%3
if digit: tribits[base3] += digit
base3 += 1
num //= 3
result = sum(count%3 * 3**base3 for base3,count in enumerate(tribits) if count%3)
return result * [1,-1][sign%3]
.
集合中的计数器只需一行代码即可在 O(n) 时间内给出预期结果：
from collections import Counter
numbers = [1,0,1,0,1,0,99]
singleN = next(n for n,count in Counter(numbers).items() if count == 1)
集合也可以在 O(n) 中工作：
distinct = set()
multiple = [n for n in numbers if n in distinct or distinct.add(n)]
singleN = min(distinct.difference(multiple))
最后两个解决方案确实使用了与列表大小成比例的可变数量的额外内存（即不是 O(1) space）。另一方面，它们 运行 快了 30 倍，并且它们将支持列表中的任何数据类型。他们还支持迭代器
一个无符号n-bit数的最高位的值为2n-1 .
一个有符号二进制补码n-bit数的最高位的值为-2n-1.
这两个值之间的 差异 是 2n.
因此，如果一个无符号 n-bit 数设置了最高位，转换为二进制补码有符号数减去 2n.
在一个 32 位数字中，如果设置了第 31 位，则数字将 >= 231，因此公式为：
if n >= 2**31:
n -= 2**32
我希望这能说明问题。
你好，我已经解决了这个leetcode问题https://leetcode.com/problems/single-number-ii。 objective是在O(n)时间内解决问题，0(1)space。我写的代码如下：
class Solution:
def singleNumber(self, nums: List[int]) -> int:
counter = [0 for i in range(32)]
result = 0
for i in range(32):
for num in nums:
if ((num >> i) & 1):
counter[i] += 1
result = result | ((counter[i] % 3) << i)
return self.convert(result)
#return result
def convert(self,x):
if x >= 2**31:
x = (~x & 0xffffffff) + 1
x = -x
return x
现在有趣的部分在 convert 函数中，因为 python 使用对象来存储 int 而不是 32 位字或其他东西，它不知道当我的 counter 的 MSB 设置为 1 时，结果为负。我通过将其转换为其 2 的补码并返回负值来处理该问题。
现在有人发布了他们的解决方案：
def convert(self, x):
if x >= 2**31:
x -= 2**32
return x
而且我不明白为什么会这样。我需要帮助来理解为什么这个减法有效。
这就是n位数字A的补码定义。
如果A是正数就用A的二进制码
如果A为负数，则使用2^n+A（或2^n-|A|）的二进制编码。此数字是您必须添加到 |A| 的数字得到 2^n（即 |A| 与 2^n 的补码，因此得名补码法）。
所以，如果你有一个用二进制补码编码的负数 B，它的代码中实际是 2^N+B。要得到它的值，你必须从 B.
中减去 2^N补码还有许多其他定义（~A+1、~(A-1) 等），但这个是最有用的，因为它解释了为什么加有符号的补码与加法完全相同正数。该数字在代码中（如果为负则添加 2^32）并且加法结果将是正确的，前提是您忽略可能作为进位生成的 2^32（并且没有溢出）。这个算法属性是计算机中使用二进制补码的主要原因。
32 位有符号整数环绕每个 2**32，因此设置了符号位的正数（即 >= 2**31）与负数 2**32 具有相同的二进制表示] 少
Python 整数是无限大的。当您添加更多位时它们不会变为负数，因此二进制补码可能无法按预期工作。你可以用不同的方式处理底片。
def singleNumber(nums):
result = 0
sign = [1,-1][sum(int(n<0) for n in nums)%3]
for i in range(32):
counter = 0
for num in nums:
counter += (abs(num) >> i) & 1
result = result | ((counter % 3) << i)
return result * sign
这种二进制方法可以像这样优化和简化：
def singleNumber(nums):
result = 0
for i in range(32):
counter = sum(1 for n in nums if (n>>i)&1)
if counter > 0: result |= (counter % 3) << i
return result - 2*(result&(1<<31))
如果你喜欢一种衬里，你可以使用 functools 中的 reduce() 来实现它：
result = reduce(lambda r,i:r|sum(1&(n>>i) for n in nums)%3<<i,range(32),sum(n<0 for n in nums)%3*(-1<<32))
请注意，此方法将始终对数据进行 32 次传递，并将限制为 -2^31...2^31 范围内的数字。增加这个范围将系统地增加通过数字列表的次数（即使列表只包含小值）。此外，由于您没有在 i 循环之外使用 counter[i]，因此不需要列表来存储计数器。
您可以使用非常相似的方法（也可以在 O(n) 时间和 O(1) space 内响应）利用基数 3 而不是基数 2：
def singleNumber(nums):
result = sign = 0
for num in nums:
if num<0 : sign += 1
base3 = 1
num = abs(num)
while num > 0 :
num,rest = divmod(num,3)
rest,base3 = rest*base3, 3*base3
if rest == 0 : continue
digit = result % base3
result = result - digit + (digit+rest)%base3
return result * (1-sign%3*2)
这个的优点是它只会遍历列表一次（因此支持迭代器作为输入）。不限制取值范围，会尽可能少的执行嵌套while循环（根据每个取值的大小）
它的工作方式是在基数 3 表示中独立地添加数字并在不应用进位的情况下循环结果（逐位）。
例如：[ 16, 16, 32, 16 ]
Base10 Base 3 Base 3 digits result (cumulative)
------ ------ ------------- ------
16 121 0 | 1 | 2 | 1 121
16 121 0 | 1 | 2 | 1 212
32 2012 2 | 0 | 1 | 2 2221
16 121 0 | 1 | 2 | 1 2012
-------------
sum of digits % 3 2 | 0 | 1 | 2 ==> 32
while num > 0 循环处理数字。它最多 运行 log(V,3) 次，其中 V 是数字列表中最大的绝对值。因此它类似于基数 2 解决方案中的 for i in range(32) 循环，只是它始终使用尽可能小的范围。对于任何给定的值模式，该 while 循环的迭代次数将小于或等于一个常数，从而保留主循环的 O(n) 复杂性。
我进行了一些性能测试，实际上，base3 版本仅在值较小时比 base2 方法快。 base3 方法总是执行较少的迭代，但是当值很大时，由于模运算与按位运算的开销，它会损失总执行时间。
为了使 base2 解决方案始终比 base 3 方法更快，它需要通过反转循环嵌套（数字内的位而不是位内的数字）来优化其迭代：
def singleNumber(nums):
bits = [0]*len(bin(max(nums,key=abs)))
sign = 0
for num in nums:
if num<0 : sign += 1
num = abs(num)
bit = 0
while num > 0:
if num&1 : bits[bit] += 1
bit += 1
num >>= 1
result = sum(1<<bit for bit,count in enumerate(bits) if count%3)
return result * [1,-1][sign%3]
现在它每次都会胜过基数 3 的方法。作为一个附带的好处，它不再受值范围的限制，并将支持迭代器作为输入。请注意，位数组的大小可以视为常数，因此这也是一个 O(1) space 解决方案
但是，公平地说，如果我们对以 3 为底的方法应用相同的优化（即使用以 3 为底的列表 'bits'），它的性能在所有值大小上都排在前面：
def singleNumber(nums):
tribits = [0]*len(bin(max(nums,key=abs))) # enough base 2 -> enough 3
sign = 0
for num in nums:
if num<0 : sign += 1
num = abs(num)
base3 = 0
while num > 0:
digit = num%3
if digit: tribits[base3] += digit
base3 += 1
num //= 3
result = sum(count%3 * 3**base3 for base3,count in enumerate(tribits) if count%3)
return result * [1,-1][sign%3]
.
集合中的计数器只需一行代码即可在 O(n) 时间内给出预期结果：
from collections import Counter
numbers = [1,0,1,0,1,0,99]
singleN = next(n for n,count in Counter(numbers).items() if count == 1)
集合也可以在 O(n) 中工作：
distinct = set()
multiple = [n for n in numbers if n in distinct or distinct.add(n)]
singleN = min(distinct.difference(multiple))
最后两个解决方案确实使用了与列表大小成比例的可变数量的额外内存（即不是 O(1) space）。另一方面，它们 运行 快了 30 倍，并且它们将支持列表中的任何数据类型。他们还支持迭代器
一个无符号n-bit数的最高位的值为2n-1 .
一个有符号二进制补码n-bit数的最高位的值为-2n-1.
这两个值之间的 差异 是 2n.
因此，如果一个无符号 n-bit 数设置了最高位，转换为二进制补码有符号数减去 2n.
在一个 32 位数字中，如果设置了第 31 位，则数字将 >= 231，因此公式为：
if n >= 2**31:
n -= 2**32
我希望这能说明问题。