How to get the logical right binary shift in python

Question

As revealed by the title, in JavaScript there is a specific operator >>>. For example, in JavaScript we will have the following result:

(-1000) >>> 3 = 536870787

(-1000) >> 3 = -125

1000 >>> 3 = 125

1000 >> 3 = 125

So is there a certain method or operator representing this >>>?

NPE · Accepted Answer · 2011-04-29T22:02:41.227

60

There isn't a built-in operator for this, but you can easily simulate the >>> yourself:

>>> def rshift(val, n): return val>>n if val >= 0 else (val+0x100000000)>>n
... 
>>> rshift(-1000, 3)
536870787
>>> rshift(1000, 3)
125

The following alternative implementation removes the need for the if:

>>> def rshift(val, n): return (val % 0x100000000) >> n

edited Apr 29 '11 at 22:02

answered Apr 29 '11 at 14:05

NPE

486,780
108
951
1,012

4

`(val + 0x100000000) % 0x100000000)` is `val % 0x100000000`. – Baffe Boyois Apr 29 '11 at 19:16
1

@Baffe Boyois: in Python it most certainly isn't (the result is always positive whereas the first operand can have either sign). – NPE Apr 29 '11 at 19:57
3

Example? Note that `-1 % 3 == 2` in Python. ["The modulo operator always yields a result with the same sign as its second operand (or zero)"](http://docs.python.org/reference/expressions.html#binary-arithmetic-operations) – Baffe Boyois Apr 29 '11 at 21:39
9

0x100000000 is `1 << 32`, and 32 is the number of bits used to represent the integer (which is important but not stated anywhere). If you had 64 bit integers then you'd have to use `1 << 64` instead. – Scott Griffiths Nov 15 '17 at 17:10
This answer is WRONG if val < 0 and n == 0 !! See a corrected answer below. rshift(-1, 0) = 4294967295 with this answer! – systemBuilder Jan 14 '21 at 19:42
[This answer](https://stackoverflow.com/a/64987033/839733) explains the logic behind `val+0x100000000`. – Abhijit Sarkar Aug 21 '21 at 10:13
@systemBuilder This how logical/unsigned right shift behaves in other languages. If you do `val >>> 0` it essentially converts it to unsigned. Open your browser console and try for yourself. – Inkling Dec 13 '21 at 01:32

score 12 · Answer 2 · answered Apr 29 '11 at 13:58

12

No, there isn't. The right shift in python is arithmetical.

answered Apr 29 '11 at 13:58

Femaref

60,705
7
138
176

1

So is this included in some package anyway? – dementrock Apr 29 '11 at 14:03
Since Python doesn't have unsigned numbers, it only makes sense that it wouldn't include unsigned shifts. – Mark Ransom Jul 10 '12 at 17:06
3

@Mark Ransom: That's wrong, you might need to compute an expression defined in another language (just as I do now). But I agree that due to the non-existence of unsigned numbers the need for unsigned shift is rather limited. – maaartinus Aug 29 '12 at 14:32

score 3 · Answer 3 · edited May 23 '17 at 12:32

3

Here's a spinoff of aix's answer. The normal right-shift operator will work if you feed it a positive value, so you're really looking for a conversion from signed to unsigned.

def unsigned32(signed):
    return signed % 0x100000000

>>> unsigned32(-1000) >> 3
536870787L

edited May 23 '17 at 12:32

Community

1
1

answered Jul 10 '12 at 17:13

Mark Ransom

299,747
42
398
622

score 2 · Answer 4 · answered Jan 05 '15 at 20:29

Trying to flip the sign bit of a negative number by masking it with 0x100000000 is fundamentally misconceived as it makes hard assumptions about the word length. In my time as a programmer I have worked with 24-, 48-, 16-, 18-, 32-, 36- and 64-bit numbers. I have also heard of machines that work on odd-lengths, such as 37 and others that use ones-complement, and not twos-complement, arithmetic. Any assumptions you make about the internal representation of numbers, beyond that they are binary, is dangerous.

Even the binary assumption is not absolutely safe, but I think we'll allow that. :)

score 2 · Answer 5 · edited Feb 06 '23 at 19:00

2

Numpy provides the right_shift() function that does this:

>>> import numpy
>>> numpy.right_shift(1000, 3)
125

edited Feb 06 '23 at 19:00

Glorfindel

21,988
13
81
109

answered Apr 29 '11 at 14:12

jathanism

33,067
9
68
86

11

But isn't that just the `>>` operator? If I try `numpy.right_shift(-1000, 3)` I get `-125` not `536870787`. – Scott Griffiths Apr 29 '11 at 18:11
@ScottGriffiths is right. However you can use numpy to convert to an unsigned type, and then the normal operator works, e.g: `numpy.uint32(-1000) >> 3`. Be aware that the output type when I tested this specific case was `numpy.int64` (signed). – Inkling Dec 13 '21 at 01:22

score 2 · Answer 6 · edited Feb 06 '23 at 19:00

2

You can do a bitwise shift padding with zeros with the bitstring module using the >>= operator:

>>> a = BitArray(int=-1000, length=32)
>>> a.int
-1000
>>> a >>= 3
>>> a.int
536870787

edited Feb 06 '23 at 19:00

Glorfindel

21,988
13
81
109

answered Apr 29 '11 at 18:09

Scott Griffiths

21,438
8
55
85

Rotate is not the same as shift. – Mark Ransom Jul 10 '12 at 17:05
@Mark: Fair point - I had misunderstood what the >>> operator was doing. Fixed now. – Scott Griffiths Jul 10 '12 at 19:25

score 1 · Answer 7 · answered May 14 '15 at 13:00

1

You need to remember that if the number is negative, the top bit is set and with each shift right you need to make the top bit set as well.

Here is my implementation:

def rshift(val, n):
    s = val & 0x80000000
    for i in range(0,n):
        val >>= 1
        val |= s
    return val

answered May 14 '15 at 13:00

blackd0t

439
1
6
13

I think you got the sense of the question backwards. All python shifts are arithmetic. You have implemented an arithmetic shift., duplicating python's functionality The original question is asking for a logical shift operator, not an arithmetic shift. – systemBuilder Jan 14 '21 at 19:37

Victor010 · Answer 8 · 2019-04-30T14:53:48.697

0

A solution that works without a modulo:

>>> def rshift(val,n): return (val>>n) & (0x7fffffff>>(n-1))

This works since 7fffffff is a positive number and right shifting that will add zeros to the left.

edited Apr 30 '19 at 14:53

answered Apr 30 '19 at 11:54

Victor010

1
1

Daniel · Answer 9 · 2020-03-16T21:08:43.767

0

You could also use floor division:

def rshift(val, n):
    if val > 0:
        return val >> n
    return val // -(2^n)

edited Mar 16 '20 at 21:08

answered Mar 16 '20 at 17:30

Daniel

198
2
14

iamwaseem99 · Answer 10 · 2020-04-24T14:50:36.857

This is not an efficient approach but works just as expected

def _toBinary(x):
    x=int(x)
    binary = []
    while x > 0:
        binary.append(str(x%2))
        x=int(x/2)
    return "".join(binary[::-1])

def _fromBinary(xs):
    ans = 0
    for i,x in enumerate(xs[::-1]):
        if x == '1':
            ans += 2**i
    return ans

def leftLogicalShift(x,n=1):
    if not type(x) == int:
        return x
    xs = _toBinary(x)
    xs = [x for x in xs]
    for _ in range(n):
        xs.pop(0)
        xs.append('0')
    return _fromBinary("".join(xs))

def rightLogicalShift(x,n=1):
    if not type(x) == int:
        return x
    xs = _toBinary(x)
    xs = [x for x in xs]
    for _ in range(n):
        xs.pop()
        xs.insert(0,'0')
    return _fromBinary("".join(xs))

def leftArithmeticShift(x,n=1):
    return leftLogicalShift(x,n)

def rightArithmeticShift(x,n=1):
    if not type(x) == int:
        return x
    xs = _toBinary(x)
    xs = [x for x in xs]
    for _ in range(n):
        tmp = xs[0]
        xs.pop()
        xs.insert(0,tmp)
    return _fromBinary("".join(xs))

lls = leftLogicalShift(10,2) 
print(lls) # 8

rls = rightLogicalShift(10,2) 
print(rls) # 2

las = leftArithmeticShift(10,2)
print(las) # 8

ras = rightArithmeticShift(10,2)
print(ras) # 14

references:

https://open4tech.com/logical-vs-arithmetic-shift/

https://www.interviewcake.com/concept/java/bit-shift

score -2 · Answer 11 · edited Aug 05 '20 at 01:00

-2

I think a logical right binary shift is not available in Python directly. Instead you can use Javascript in Python as in:

import js2py
rshift = js2py.eval_js('function $(a, b){ return a >>> b}')
print (rshift(244, 324)) #15

edited Aug 05 '20 at 01:00

Ivo Mori

2,177
5
24
35

answered Aug 04 '20 at 23:39

SomeOne

1
1

systemBuilder · Answer 12 · 2021-01-14T19:40:16.933

-3

The top-voted answer produces WRONG results for val < 0 and n == 0!

def rshift(val, n):
    if (val >= 0): return val >> n
    elif (n == 0): return val
    else: return (val + 0x10000000) >> n

>>> rshift(-1, 0)
-1

edited Jan 14 '21 at 19:40

answered Jan 14 '21 at 19:32

systemBuilder

55
1
3

How to get the logical right binary shift in python

12 Answers12

Linked

Related