# RE: bitwise not - not what I expected

Discussion in 'Python' started by Tim Peters, Aug 17, 2003.

1. ### Tim PetersGuest

[Elaine Jackson]
> Is there a function that takes a number with binary numeral a1...an
> to the number with binary numeral b1...bn, where each bi is 1 if ai
> is 0, and vice versa? (For example, the function's value at 18
> [binary 10010] would be 13 [binary 01101].) I thought this was what
> the tilde operator (~) did,

Surprise: that is what ~ does.

> but when I went to try it I found out that wasn't the case.

Please give a specific example. 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

This is why you get -19:

>>> n = 18
>>> ~n

-19
>>>

Any answer other than that is wishing away the 0 bits at the left in the
input. Python can't *guess* how many bits you want to keep. If you only
want to keep the rightmost 5 bits, then explicitly mask off the rightmost 5
bits:

>>> (~18) & 0x1f

13
>>>

So that's the 13 "you expected".

> I discovered by experiment (and verified by looking at the
> documentation) that the tilde operator takes n to -(n+1). I can't
> imagine what that has to do with binary numerals. Can anyone
> shed some light on that?

Python represents negative integers in unbounded 2's-complement form (well,
it doesn't really under the covers, but it maintains the illusion of doing
so in all arithmetic and logical operators). The 2's-complement of an
integer is equal to 1 plus its 1's-complement form, and 1's-complement is
identical to bitwise inversion. So

-n = 1 + (~n)

Then

~n = -(n+1)

follows from that via rearrangement.

> (In case you're curious, I'm writing a script that will play Nim,
> just as a way of familiarizing myself with bitwise operators. Good
> thing, too: I thought I understood them, but apparently I don't.)

You're only overlooking the consequences of an infinite amount of
information <wink>.

Tim Peters, Aug 17, 2003

2. ### Michael PeuserGuest

"Elaine Jackson" <> schrieb im Newsbeitrag
news:d4L%a.781431\$...
>
> "Tim Peters" <> wrote in message
> news:...
>
> <snip>
> | To understand your example above, note that
> | binary 10010 actually has an unbounded number of 0 bits "to the left":
> |
> | ...00000010010 = 13

... should read 18 BTW

> |
> | 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.

I think not. Tim seems to point out that there is no natural final
"representation" of negative numbers unless we invent some convention. The
interpretation of 1101101 or 11111101101 or ......1111101101 as -19 is a
convention and has nothing to do with the more natural interpretaton of
101101 as 18. The main reason is that binary adders used in computers are
very simple too be (ab-) used for subtraction in that way....

Kindly
Michael P

Michael Peuser, Aug 17, 2003

3. ### Bengt RichterGuest

On Sun, 17 Aug 2003 13:05:13 GMT, "Elaine Jackson" <> wrote:

>
>"Tim Peters" <> wrote in message
>news:...
>
><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*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

Bengt Richter, Aug 17, 2003
4. ### Carl BanksGuest

Elaine Jackson wrote:
> <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.

And if someone had done that, it would violate the invariant:

~(~x) == x

In fact, by repeatedly applying ~ you'd eventually zero all the bits.

--
CARL BANKS http://www.aerojockey.com/software
"You don't run Microsoft Windows. Microsoft Windows runs you."

Carl Banks, Aug 17, 2003