CODEWITHSUNDEEP
pythonpython-2.7python-3.x
Shejo284
Shejo284

Reputation: 4761

Discussion around bitwise operator statement

I am curious about a python statement:

csum = (N * (N + 1)) >> 1

where N = 5 and csum = 15. I do not understand the operator >> and what's going on in this statement. What is the the under-the-hood thought behind this action? csum is supposed to be the cumulative sum of a vector 1:5.

Appreciate your thoughts on this.

Upvotes: 6

Views: 76

Answers (2)

Stephen Rauch
Stephen Rauch

Reputation: 49784

The operator >> is a shift right, in this case by 1. It is roughly equivalent to integer divide by 2^N, so in this case divide by 2^1 (eg 2). So: 

csum = (N * (N + 1)) >> 1

where N = 5, is 5 * 6 / 2 which equals 15.

Which gives the cumulative sum for a one based incrementing vector such as 1:5

Upvotes: 3

Kasravnd
Kasravnd

Reputation: 107287

Based on Python wiki:

x >> y Returns x with the bits shifted to the right by y places. This is the same as //'ing x by 2**y.

In your statement python calculates the (N * (N + 1)) part first then performs the >> operation between the result and the number 1:

In [4]: (N * (N + 1))
Out[4]: 30

In [5]: 30 >> 1
Out[5]: 15

Well, for a better demonstration you can simply convert your integers to binary using bin() function:

In [6]: bin(30)
Out[6]: '0b11110'

Now shift the bits to right by 1 and you'll get the following number:

01111

Now convert the result to integer using int() and 2 as the base:

In [11]: int('01111', 2)
Out[11]: 15

As another alternative way for calculating the right shift operation you can also use operator.rshift() function:

In [12]: from operator import rshift
In [13]: rshift(30, 1)
Out[13]: 15

Read more: https://en.wikipedia.org/wiki/Arithmetic_shift

As mentioned in python wiki and @eryksun pointed out, you can also think of a right shift operation as dividing the 30 (left side number) by 21 (right side number) which it would be easier to interpret when you convert your number to coefficients of 2 powers.

bin(30) is equal to 11110 which is:

1*24 + 1*23 + 1*22 + 1*21 + 0*20

And by deviding with 2 you'll get:

1*23 + 1*22 + 1*21 + 1*20 + 0 = 8 + 4 + 2 + 1 = 15

Upvotes: 5

Related Questions