I am trying to understand the bit shift operation >> on a negative integer.
-2 >> 1 # -1
-3 >> 1 # -2
-5 >> 1 # -3
-7 >> 1 # -4
Can someone explain how this is done? I know it is related to Two's complement, but I can't related that to the shifting operation.
The full explanation is provided here
Two's Complement binary for Negative Integers:
Negative numbers are written with a leading one instead of a leading zero. So if you are using only 8 bits for your twos-complement numbers, then you treat patterns from "00000000" to "01111111" as the whole numbers from 0 to 127, and reserve "1xxxxxxx" for writing negative numbers. A negative number, -x, is written using the bit pattern for (x-1) with all of the bits complemented (switched from 1 to 0 or 0 to 1). So -1 is complement(1 - 1) = complement(0) = "11111111", and -10 is complement(10 - 1) = complement(9) = complement("00001001") = "11110110". This means that negative numbers go all the way down to -128 ("10000000").
Of course, Python doesn't use 8-bit numbers. It USED to use however many bits were native to your machine, but since that was non-portable, it has recently switched to using an INFINITE number of bits. Thus the number -5 is treated by bitwise operators as if it were written "...1111111111111111111011".
So, the explanation for shift operator:
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 order to understand the above explanation you can check it out with something like this:
def twos_comp(val, nbits):
"""Compute the 2's complement of int value val"""
if val < 0:
val = (1 << nbits) + val
else:
if (val & (1 << (nbits - 1))) != 0:
# If sign bit is set.
# compute negative value.
val = val - (1 << nbits)
return val
def foo(a,b):
print("{0:b} >> {1:b} = {2:b} <==> {3:b} >> {4:b} = {5:b}".format(
a,b,a>>b,
twos_comp(a,8),b, twos_comp(a>>b,8)
))
foo(-2, 1)
foo(-3, 1)
foo(-5, 1)
foo(-7, 1)
Which outputs:
-10 >> 1 = -1 <==> 11111110 >> 1 = 11111111
-11 >> 1 = -10 <==> 11111101 >> 1 = 11111110
-101 >> 1 = -11 <==> 11111011 >> 1 = 11111101
-111 >> 1 = -100 <==> 11111001 >> 1 = 11111100
As you can see, the two's complement of the number will extend the sign.
