如何将 python3中的负位表示数转换为实际的负整型值?

By simon at 2019-05-19 • 0人收藏 • 10人看过

你好,我已经解决了这个 leetcode 问题Https://leetcode.com/problems/single-number-ii. 目标是在 o (n)时间和0(1)空间中求解该问题。 我写的代码如下:

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 | ((counter [ i ]% 3) i) return self.convert (result) # return result convert (self,x) : if x 2 * * 31: x (~ x & 0xffffff)) + 1 x-x return x x

现在有趣的部分是转变函数,因为 python 使用对象存储Int相对于一个32位的单词或东西,它不知道的结果是否定的时候,我的 MSB计数器设置为1。 我通过将它转换为它的2的补数并返回负值来处理这个问题。

现在有人发布了他们的解决方案:

Def convert (self,x) : if x2 * * 31: x-2 * * 32 return x

我不知道为什么会这样。 我需要帮助来理解为什么这个减法是有效的。

4 个回复 | 最后更新于 2019-05-19
2019-05-19   #1

这就是 n 位上的数字 a 的补码的定义。

  • 如果数字 a 是正数,用 a 的二进制代码

  • 如果 a 是负数,使用2 ^ n + a (或2 ^ n-| a |)的二进制代码。 这个数字必须加到 | a | 才能得到2 ^ n (即 | a | 对2 ^ n 的补数,因此得到了两个补数方法的名称)。

所以,如果你有一个负数 b 在2的补码中,它的代码实际上是2 ^ n + b。 为了得到它的值,你必须从 b 减去2 ^ n。

2的补数(~ a + 1,~ (A-1)等)有许多其他定义,但这个定义最有用,因为它解释了为什么有符号2的补数相加与正数相加是完全相同的。 该数字位于代码中(如果为负,则加2 ^ 32) ,如果忽略作为执行可能生成的2 ^ 32(并且没有溢出) ,则加法结果将是正确的。 这种算术性质是计算机使用二进制补码的主要原因。

2019-05-19   #2

32位有符号整数2 * * 32,所以正数与符号位设置(即2 * * 31)具有与负数相同的二进制表示2 * * 32少。

2019-05-19   #3

Python 整数是无穷大的。 当你添加更多的比特时,它们不会变成负数,所以二进制的补码可能不会像预期的那样工作。 你可以用不同的方式处理负面情绪。

Def singleNumber (nums) : result 0 sign [1,-1][ sum (int (n0) for n in nums)% 3] for i in range (32) : counter 0 for num in nums: counter + ((num) i) & 1 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 (ni) & 1) if counter 0: result | (counter% 3) i return result-2 * (result & (131))

如果您喜欢一行程序,可以使用 functools 中的 reduce ()来实现它:

结果 reduce (lambda r,i: r | sum (1 & (n i) for n in nums)% 3 i,范围(32) ,sum (n 0 for n in nums)% 3 * (- 132))

请注意,这种方法总是执行32次数据传递,并且仅限于 -2 ^ 31... 2 ^ 31范围内的数字。 增加这个范围将系统地增加通过数字列表的传递次数(即使列表只包含很小的值)。 此外,由于您没有在 i 循环之外使用 counter [ i ] ,因此您不需要一个列表来存储计数器。

您可以使用一个非常类似的方法来利用 base 3而不是 base 2(这个方法也在 o (n)时间和 o (1)空间中响应) :

Def singleNumber (nums) : result sign 0 for num in nums: if num 0: sign + 1 base31 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-digit + (digit + rest) se3 return result * (1-sign% 3 * 

这种方法的优点是它只会遍历列表一次(因此支持将迭代器作为输入)。 它不限制值的范围,将尽可能少地执行嵌套的 while 循环(根据每个值的大小)

它的工作方式是在一个3进制表示中独立添加数字,并循环结果(逐位) ,而不应用进位。

例如: [16,16,32,16]

基数10位3基3位结果(累计)————————————————161210 | 1 | 2 | 1121161210 | 1 | 2 | 12123220122 | 0 | 1 | 2221161210 | 1 | 2 | 12012————数字之和% 32 | 0 | 1 | 232

这个零号机循环处理这些数字。 它将以最大的 log (v,3)运行,其中 v 是数字列表中最大的绝对值。 就其本身而言,它类似于为 i 在范围(32)循环在基2的解决方案,除非它总是使用最小可能的范围。 对于任何给定的值模式,while 循环的迭代次数将小于或等于一个常数,从而保持了主循环的 o (n)复杂度。

我做了一些性能测试,实际上,当值很小时,base3版本只比 base2方法快。 Base3方法总是执行较少的迭代,但是,当值很大时,由于模与按位操作的开销,它会损失总的执行时间。

为了使 base2解决方案总是比 base 3解决方案更快,它需要通过反向循环嵌套(位内数字而不是位内数字)来通过位优化迭代:

Def singleNumber (nums) : bits [0] * len (bin (max (nums,key abs))))在 nums 中为 num 符号0: if num 0: sign + 1 num abs (num) bit 0而 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)返回结果 * [1,-1][ sign% 3]

现在它每次都将胜过基3方法。 另一个好处是,它不再受值范围的限制,并将支持迭代器作为输入。 注意,位数组的大小可以视为一个常量,所以这也是一个 o (1)空间解决方案

但是,为了公平起见,如果我们对基3方法应用相同的优化(即使用一个基3位的列表) ,对于所有的值大小,它都会返回到前面:

如果 num 0: sign + 1 num (num) base30而 num 0: digit% 3 if: tribits [ base3] + digit base3 / / 3 result sum (count% 3 * 3 * 3 for base3,count in enumer (base3) if count% 3)返回结果 * [1,-1][ sign% 3]

.

来自集合的计数器将使用一行代码给出 o (n)时间内的预期结果:

[1,0,1,0,1,0,1,0,99] singleN (n 表示 n,在计数器中计数(数字)。 项目()(如计算1)

集合在 o (n)中也可以工作:

不同的集合()多重[ n 为 n,如果 n 为不同的或不同的,添加(n)] singleN min (不同的,差异(多重))

最后两个解决方案确实使用了与列表大小成比例的可变量额外内存(即非 o (1)空间)。 另一方面,它们运行速度快30倍,并且支持列表中的任何数据类型。 它们还支持迭代器

2019-05-19   #4

对象的最高位的值未署名的N 位数字是图2N-1.

的最高位的值署名2的补码 n 位数是- 2N-1.

这个差异在这两个值之间的是图2N.

因此,如果一个无符号 n 位数设置了最高位,则将其转换为二的补码有符号数减去图2N.

在一个32位的数字中,如果设置了31位,那么这个数字将是2图31所以公式是

如果 n 2 * * 31: n-2 * * 32

我希望这能说明问题。

登录后方可回帖

Loading...