如何在Python中进行有符号和无符号值的算术右移

Question

有些编程语言如Java、Verilog都具备按位逻辑(<<, >>)和算术移位(<<<, >>>)运算符。

对于无符号数，逻辑移位和算术移位的操作相同。比如8'b11000101是8位无符号整数197的二进制表示，则

8'b11000101 >>  2 => 8'b00110001
8'b11000101 >>> 2 => 8'b00110001
8'b11000101 <<  2 => 8'b00010100
8'b11000101 <<< 2 => 8'b00010100

对于带符号数，只有算术左移和逻辑左移操作是相同的，但算术右移会导致符号扩展。例如，如果8'b11000101是8位带符号数-59的二进制表示，则

8'b11000101 >>  2 => 8'b00110001
8'b11000101 >>> 2 => 8'b11110001
8'b11000101 <<  2 => 8'b00010100
8'b11000101 <<< 2 => 8'b00010100

Python 只有逻辑位移运算符，而没有算术位移运算符。那么如何在 Python 中实现带符号和无符号值的算术右移？

- nurabha

---

这个回答解决了你的问题吗？https://dev59.com/HW025IYBdhLWcg3wvIgo - Muhammad Junaid Haris

实际上，Python只有算术右移；在Python的无限整数类型的情况下，逻辑右移是没有意义的。如果要定义逻辑右移，则需要指定用于表示整数的位数。 - kaya3

https://docs.python.org/3/reference/expressions.html#shifting-operations - kaya3

你似乎把 >> 和 >>> 搞反了：Java（和Javascript）支持两种类型的右移位运算符。>> 运算符是有符号右移位运算符，而 >>> 则是无符号右移位运算符。 - chqrlie

Answer 1

Python只有逻辑移位运算符，没有算术移位运算符。那么如何在python中实现带符号和无符号值的算术右移呢？

Python实际上只有算术移位运算符：

- 将正数或负数左移n位与将其乘以2的n次方完全相同。 - 右移n位取决于被移动的值是否为负数。对于正数，它们除以2的n次方并朝0舍入。而对于负数，则会表现出一系列1位延伸到最高位的无限字符串，这是负数的二进制补码表示的副作用。这可以转化为一个数学等式：通过正整数n将整数向右移位，其结果等价于将其除以2的n次方并将结果向负无穷大四舍五入，即Math.floor(value / 2**n)。

如果您想模拟java和javascript中提供的负数无符号右移，请先将负数转换为具有固定位数的正数。然后进行右移，就会得到预期的值。

x = -1
x32 = x & 0xffffffff   # convert to 32-bit unsigned value
x >> 8                 # produces -1
x32 >> 8               # produces 0x00ffffff

- chqrlie

---

这个回答使用了 x + 0x100000000 而不是 x & 0xffffffff。结果相同，但后者实际上清除了符号位（并丢弃了进位），在我看来更直观。 - Abhijit Sarkar

Answer 2

我认为你的问题的答案取决于你如何存储你的数字。如果你想让0b11000101表示-59，那么在执行移位操作之前，你需要以某种方式指定位长度。请注意，Python对负数的二进制表示不是以2的补码格式表示的：

>>> bin(59)
'0b111011'
>>> bin(-59)
'-0b111011'

所以，如果-0b111011适用于您的目的，那么您可以按照chqrlie的答案中指定的算术右移进行操作。

然而，如果您需要将结果呈现为二进制补码格式，即您需要将0b11000101算术右移2位以计算出字面上的0b11110001，那么以下函数应该适合您：

# x is an n-bit number to be shifted m times
def sra(x,n,m):
    if x & 2**(n-1) != 0:  # MSB is 1, i.e. x is negative
        filler = int('1'*m + '0'*(n-m),2)
        x = (x >> m) | filler  # fill in 0's with 1's
        return x
    else:
        return x >> m

这基本上执行常规的右移操作，但如果数字为负数（以2的补码格式和指定的位长度表示），则用1填充前导零。

示例：

sra(0b11000101, 8,  2)    -> 0b11110001
sra(0x805a6cf3, 32, 0x10) -> 0xffff805a
sra(0x705a6cf3, 32, 0x10) -> 0x0000705a

- ClausWorks

---

请注意，Python中负数的二进制表示不采用二进制补码格式。Python对整数的按位操作被定义为“按照具有无限数量符号位的二进制补码进行计算”。bin函数显示的只是将它们“作为字符串”格式化的方式，而不是它们在内部的表示方式，并且这对按位运算符没有任何影响。 - kaya3

嗯，这里有一些歧义；“二进制表示”显然是指“基于2的字符串表示”，而不是“在内存中的底层表示”。 - Karl Knechtel

Answer 3

虽然我不是 Python 程序员，但我通常会这样解决这个问题：

x = (x>>1)|(x&80);        //  8bit
x = (x>>1)|(x&8000);      // 16bit
x = (x>>1)|(x&80000000);  // 32bit

所以只需将原始x的最高有效位复制到位移创建的空间中。 但是，这仅适用于1位的位移。 对于更多位移，您需要执行以下操作：

if (x<0) x = (x>>2)|0xC0;       else x = x>>2; //  8bit
if (x<0) x = (x>>2)|0xC000;     else x = x>>2; // 16bit
if (x<0) x = (x>>2)|0xC0000000; else x = x>>2; // 32bit

if (x<0) x = (x>>3)|0xE0;       else x = x>>3; //  8bit
if (x<0) x = (x>>3)|0xE000;     else x = x>>3; // 16bit
if (x<0) x = (x>>3)|0xE0000000; else x = x>>3; // 32bit

if (x<0) x = (x>>4)|0xF0;       else x = x>>4; //  8bit
if (x<0) x = (x>>4)|0xF000;     else x = x>>4; // 16bit
if (x<0) x = (x>>4)|0xF0000000; else x = x>>4; // 32bit

if (x<0) x = (x>>5)|0xF8;       else x = x>>5; //  8bit
if (x<0) x = (x>>5)|0xF800;     else x = x>>5; // 16bit
if (x<0) x = (x>>5)|0xF8000000; else x = x>>5; // 32bit

...

你可以为掩码创建一个查找表（LUT）

LUT8[8]=
    {
    0x00, 
    0x80, 
    0xC0, 
    0xE0, 
    0xF0, 
    0xF8, 
    0xFC, 
    0xFE, 
    }

if (x<0) x = (x>>k)|LUT8[k&7]; else x = x>>k; //  8bit

按位移动 k 位的掩码只是一个二进制数，从最高有效位开始它包含 k 个 1，其余位为 0。

还有一种更简单的解决方案（代价是两次否定），如下：

if (x<0) x = -((-x)>>k); else x = x>>k;

- Spektre