9

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 ?

nurabha
  • 1,152
  • 3
  • 18
  • 42
  • Does this answer your question? https://stackoverflow.com/questions/5832982/how-to-get-the-logical-right-binary-shift-in-python – Muhammad Junaid Haris Nov 23 '20 at 06:01
  • 1
    Actually, Python only has arithmetic right shift; logical right shift would not make sense in the context of Python's unbounded integer type. For logical right shift to be defined, you need to specify the number of bits used to represent an integer. – kaya3 Nov 23 '20 at 10:45
  • https://docs.python.org/3/reference/expressions.html#shifting-operations – kaya3 Nov 23 '20 at 10:52
  • You seem to have `>>` and `>>>` reversed: Java (and Javascript) supports two types of right shift operator. The `>>` operator is a signed right shift operator and `>>>` is an unsigned right shift operator. – chqrlie Nov 24 '20 at 12:43

3 Answers3

9

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
chqrlie
  • 131,814
  • 10
  • 121
  • 189
  • 2
    [This answer](https://stackoverflow.com/a/5833119/839733) does `x + 0x100000000` instead of `x & 0xffffffff`. The results are the same but the latter actually clears the sign bit (and discards the carry), which, IMO, is more intuitive. – Abhijit Sarkar Aug 21 '21 at 09:45
0

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
ClausWorks
  • 33
  • 4
  • 2
    *"Note that Python's binary representation of negatives is not in 2's complement format"* - Python's bitwise operations on integers [are defined as](https://docs.python.org/3/library/stdtypes.html#bitwise-operations-on-integer-types) *"calculated as though carried out in two’s complement with an infinite number of sign bits"*. What you see from the `bin` function is only how the `bin` function formats them *as strings*, not how they are represented internally, and this has no implications for bitwise operators. – kaya3 Nov 05 '21 at 13:51
  • 1
    Mm, there's an ambiguity there; "binary representation of" was apparently meant as "base-2 string representation", and not "underlying representation in memory". – Karl Knechtel Nov 05 '21 at 13:55
-1

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;
Spektre
  • 49,595
  • 11
  • 110
  • 380