CODEWITHSUNDEEP
pythonmathbitwise-operatorsbit-shiftshift
nurabha
nurabha

Reputation: 1212

How to do arithmetic right shift in python for signed and unsigned values

Some languages like Java, Verilog have both bitwise logical (<<, >>) and arithmetic shift (<<<, >>>) operators.

For unsigned values, logical and arithmetic shifts have identical operation. Say if 8'b11000101 is binary representation of 8-bit unsigned number 197, then

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

For signed values, only the arithmetic and logical left shift operations are identical but arithmetic right shift leads to sign extension. Say if 8'b11000101 is binary representation of 8-bit signed number -59, then

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

Python only has logical shift operators but no arithmetic shift operators. So how to achieve arithmetic right shift in python for signed and unsigned values ?

Upvotes: 10

Views: 14274

Answers (3)

chqrlie
chqrlie

Reputation: 144540

Python only has logical shift operators but no arithmetic shift operators. So how to achieve arithmetic right shift in python for signed and unsigned values?

Python actually only has arithmetic shift operators:

  • Left shifting by n is exactly the same as multiplying by 2 to the power n for both positive an negative values.
  • Right shifting by n depends on whether the value being shifted is negative or not. Positive values are divided by 2 to the power of n and rounded toward 0, whereas negative values behave as if there was an infinite string of 1 bits extending on the most significant bit side, a side effect of two's complement representation of negative numbers. This translates into a single mathematical equivalence: right shifting an integer by a positive integral quantity n is evaluated as dividing it by 2 to the power of n and rounding the result toward negative infinity, Math.floor(value / 2**n)

If you want to simulate unsigned right shift of negative values, as available in java and javascript, you must convert the negative value to a positive value with the fixed number of bits you are considering. Right shifting that will give the expected value:

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

Upvotes: 12

ClausWorks
ClausWorks

Reputation: 53

I think the answer to your question depends on how you are storing your numbers. If you want 0b11000101 to represent -59, then you need to specify the bit length somehow before performing the shift. Note that Python's binary representation of negatives is not in 2's complement format:

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

So, if -0b111011 works for your purposes, then you can perform the arithmetic right shift as specified in chqrlie's answer.

However, if you need your result to be in a 2's complement format, i.e. you need 0b11000101 arithmetic right-shifted by 2 to evaluate to literally 0b11110001, then the following function should work for you:

# 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

This basically performs the regular right shift, but fills in the leading zeroes with ones if the number is negative (in 2's complement format, with the specified bit length).

Examples:

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

Upvotes: 2

Spektre
Spektre

Reputation: 51835

not a python coder but I usually overcome this problem like this:

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

so simply copy the MSb of original x into space created by the bitshift. However this will work only for shifts by 1 bit. For more you need to do something like this:

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

...

You can create a LUT for the masks

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

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

The mask for bit-shift by k bits is just number containing k ones from MSb and then the rest are zeroes in binary.

There is also simpler solution (at cost of twice negating) like this:

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

Upvotes: -1

Related Questions