RE: bitwise not - not what I expected

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

  1. Tim Peters

    Tim Peters Guest

    [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
    #1
    1. Advertising

  2. "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
    #2
    1. Advertising

  3. 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
    #3
  4. Tim Peters

    Carl Banks Guest

    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
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. J. Campbell

    bitwise not and "auto casts"

    J. Campbell, Nov 13, 2003, in forum: C++
    Replies:
    8
    Views:
    450
    J. Campbell
    Nov 15, 2003
  2. Mantorok Redgormor

    bitwise not operator

    Mantorok Redgormor, Oct 1, 2003, in forum: C Programming
    Replies:
    1
    Views:
    536
    Dan Pop
    Oct 1, 2003
  3. Elaine Jackson

    bitwise not - not what I expected

    Elaine Jackson, Aug 17, 2003, in forum: Python
    Replies:
    12
    Views:
    627
    Dennis Lee Bieber
    Aug 20, 2003
  4. Tim Peters

    RE: bitwise not - not what I expected

    Tim Peters, Aug 18, 2003, in forum: Python
    Replies:
    2
    Views:
    313
    Elaine Jackson
    Aug 19, 2003
  5. David Garamond

    bitwise AND, OR, XOR, NOT for strings?

    David Garamond, Feb 24, 2004, in forum: Ruby
    Replies:
    3
    Views:
    270
    David Garamond
    Feb 25, 2004
Loading...

Share This Page