bitwise not - not what I expected

[Bengt Richter]

On Sun, 17 Aug 2003 13:05:13 GMT, "Elaine Jackson" <elainejackson7355 at home.com> wrote:

>
>"Tim Peters" <tim.one at comcast.net> wrote in message
>news:mailman.1061098645.13097.python-list at python.org...
>
><snip>
>| To understand your example above, note that
>| binary 10010 actually has an unbounded number of 0 bits "to the left":
>|
>|     ...00000010010 = 13
>|
>| The bitwise inversion of that therefore has an unbounded number of 1 bits
>| "to the left":
>|
>|     ...11111101101 = -19
>
>** What you're saying, the way I read it, is that 5+S=(-19), where S is the
>(divergent) sum of all the powers 2^k of 2 with k>=5. I'm still at sea, in other
>words.
>
Since all the sign bits extend infinitely, we can chop them off any place above
the first of the repeating bits to get N bits with some number of repetitions at the
top. We will see that the interpreted numeric value does not depend on how far
to the left we chop the bits, so long as we keep at least the first of
the repeating bits.

This representation of a signed integer with N total bits b(i) little-endianly numbered
with i going 0 to N-1 and each bit having a value b(i) of 0 or 1 is interpreted as having
the (N-1)th bit as the sign bit, and the rest positive, i.e.,

                            ___ i=N-2
                            \   
    a = -b(N-1)*2**(N-1)i +  >  b(i)*2**i   
                            /__ 
                                i=0

or in python, operating on a little-ending list of N bits,

 >>> def bitsvalue(b):  #b is bitlist, to follow convention above
 ...     N=len(b)
 ...     sum = -b[N-1]*2**(N-1)
 ...     for i in xrange(N-1):
 ...         sum += b[i]*2**i
 ...     return sum
 ...

(Remember this is little-endian: least significant bit to the left, sign at the right)

 >>> bitsvalue([0,1,0,0,1,0])
 18
 >>> bitsvalue([1,0,1,1,0,1])
 -19

It doesn't matter how far you extend a copy of the top bit, the value remains the same:
 >>> bitsvalue([1,0,1,1,0,1,1,1,1,1,1,1])
 -19

You can verify it from the math of the sum, if you separate it into two sums, one with
the top repeating sign bits b(N-r) to b(N-1) and the other with the rest, which has the
same constant value. I'll leave it as an exercise.

 >>> bitsvalue([1,1,1,1,1,1])
 -1
 >>> bitsvalue([1,1,1,1])
 -1
 >>> bitsvalue([1,1,1,0])
 7

><snip>
>| Python can't *guess* how many bits you want to keep.
>
>**  But it could if someone had told it that the leftmost nonzero digit is the
>place to start. I just assumed somebody had told it that.
>
Or the leftmost bit that is either the only bit of all or different
from the one to its right is the minimum sign bit to copy arbitrarily leftwards.

><snip>
>| Python represents negative integers in unbounded 2's-complement form
>
>** Now we're getting someplace. That was the missing piece in my puzzle.
>
Ok, I guess you don't need the demo prog after all ;-)

Regards,
Bengt Richter