bitwise not - not what I expected

Discussion in 'Python' started by Elaine Jackson, Aug 17, 2003.

  1. 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, but when I
    went to try it I found out that wasn't the case. 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? (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.)

    Muchas gracias for any and all helps and hints.

    Peace,
    EJ
    Elaine Jackson, Aug 17, 2003
    #1
    1. Advertising

  2. Elaine Jackson wrote:

    >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, but when I
    >went to try it I found out that wasn't the case. 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.
    >


    It has a lot to do with binary! Google for "two's complement".

    In the meantime, try this:

    >>> ~18 & 31

    13

    The '~' operator cannot care about precision -- that is, how many bits
    you're operating on, or expecting in your result. In your example, you
    represent decimal 18 as '10010', but '000000010010' is also correct,
    right?

    In two's complement math, both inverses, '01101' and '111111101101'
    respectively, are equivalent to decimal -19.

    And-ing with a mask that is the of length 'n' will ensure that you only
    get the least significant n bits -- and this is what you're looking for.
    Since you're operating on five bits in your example, I chose decimal 31,
    or '11111'.

    -- Graham
    Graham Fawcett, Aug 17, 2003
    #2
    1. Advertising

  3. "Elaine Jackson" <> schrieb im Newsbeitrag
    news:1YD%a.747879$...


    ....

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

    Hi Elaine,
    You have described a general misconception you seem to be not the only one
    to live with.
    The enlightening answers having been posted might sufficwe, but a schuld
    liek to add some more "enlightenment":
    Bit complements have a lot to do with set complents and the aritmetic
    negation (sometimes called two's complement for obvious reasons). Consider
    the set of of "red" of "blue". Now whats the complement? "green" and
    "yellow" is obviously the wrong answer. You in fact cannot give any answer
    befor you define the total set you are dealing with. The same applies to
    logical bit operations. Generally you take a "processor" word or a part of
    it to be defined. Some high level languages are more flexible; and even some
    computers ("vector processors") are.

    The only rule is, that ~(~x) == x

    The same situation with numbers: What is the negation of +5. You have to
    think very hard! This is a trick question and you probably will give a
    "trick answer": -5. You should be aware that this is just a trick. "-5"
    contains no other information as that it is some "complement" of 5. (same
    with complex "imaginary" numbers: 5j (in Python) just says it is some fancy
    5.)

    Now we define a transformation between positive numbers and bit patterns 5 =
    LoL. Note that 5 == ...000005 or LoL == ....ooooLoL does not help any
    understanding so you generally skip this part.

    Now you do some arithmetic "inversion": 5 -> -5 This however can (and
    should) stay a secret of the processor! By no means should you be interested
    in how the machine represents "-5". If you are courious then know that
    there had been times when computers represente -5 as ...LLLoLo. Yes it
    worked! And you had two diffrent "zeros" then: +0 and -0 !!!!

    Most computers do not distinguish between the representation of negativ
    numbers and complemented sets (let alone note a special "total set" the
    complemt was referring to). Thus the "secret" of modern two's-complement
    computern arithmetic is always disclosed to you.

    Note that there is no use in something like "masking" the MSB, i.e. that
    bits-complements only work on 31 bits. This will lead to ~5 == ~LoL == ~
    LL..LLLLoL == 2,147,483,643 Not much improvement, eh!?

    Kindly
    Michael P
    Michael Peuser, Aug 17, 2003
    #3
  4. While others explained how the ~ operator works, let me suggest
    another possibility: the bitwise exclusive or.

    >>> def bin(i):

    .... l = ['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111',
    .... '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']
    .... s = ''.join(map(lambda x, l=l: l[int(x, 16)], hex(i)[2:]))
    .... if s[0] == '1' and i > 0:
    .... s = '0000' + s
    .... return s
    ....
    >>> bin(18)

    '00010010'
    >>> ~18

    -19
    >>> bin(~18) # tricky...

    '11111111111111111111111111101101'
    >>> ~18 & 0x1f

    13
    >>> bin(~18 & 0x1f)

    '00001101'
    >>> 18 ^ 0x1f # XOR!

    13
    >>> bin(18 ^ 0x1f) # XOR

    '00001101'
    >>>



    You still have to think about the number of bits you want to invert.
    x ^ 0x1f inverts the 5 least significant bits of x.
    x ^ 0xff inverts the 8 least significant bits of x, and so on.


    --Irmen de Jong
    Irmen de Jong, Aug 17, 2003
    #4
  5. Elaine Jackson fed this fish to the penguins on Saturday 16 August 2003
    09:58 pm:

    >
    >
    > 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,
    > [but when I
    > went to try it I found out that wasn't the case. 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? (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.)
    >
    > Muchas gracias for any and all helps and hints.
    >

    You've had lots of answers at the moment though I haven't seen anyone
    explain away the "+1" part...

    Most computers use twos-complement arithmetic to avoid the problem of
    having two valid values for integer 0, which is what appears in ones
    complement arithmetic.

    For argument, assume an 8-bit integer. The value of "5" would be
    represented as 00000101. The one's complement negative would be
    11111010. So far there isn't any problem... But consider the value of
    0, represented as 00000000. A one's complement negative would become
    11111111 -- But mathematically, +0 = -0; in one's complement math, this
    does not hold true.

    So a little trick is played, to create twos complement... To negate a
    number, we take the ones complement, and then add 1 to the result. The
    "5" then goes through: 00000101 -> 11111010 + 1 -> 11111011... Looks
    strange, doesn't it... But watch what happens to that 8-bit 0: 00000000
    -> 11111111 + 1 -> (overflows) 00000000.... Negative 0 is the same as
    positive 0.

    So when you complemented your number, you first neglected to take into
    account that you complement the entire bit width, including all those 0
    bits to the left, and then when displaying the result, were confused by
    what the computer does to display... Namely, seeing a MSB set to 1, it
    interpreted the result as a negative number, put out a "-" sign, then
    generated a twos complement to create a positive value for output. The
    twos complement has that +1 step, so the ones complement "18" became
    "19"


    --
    > ============================================================== <
    > | Wulfraed Dennis Lee Bieber KD6MOG <
    > | Bestiaria Support Staff <
    > ============================================================== <
    > Bestiaria Home Page: http://www.beastie.dm.net/ <
    > Home Page: http://www.dm.net/~wulfraed/ <
    Dennis Lee Bieber, Aug 17, 2003
    #5
  6. "Dennis Lee Bieber" <> schrieb im Newsbeitrag
    news:...
    > Elaine Jackson fed this fish to the penguins on Saturday 16 August 2003
    > 09:58 pm:
    >
    > >
    > >
    > > 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,
    > > [but when I
    > > went to try it I found out that wasn't the case. 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.


    [..]

    > You've had lots of answers at the moment though I haven't seen

    anyone
    > explain away the "+1" part...
    >
    > Most computers use twos-complement arithmetic to avoid the problem

    of
    > having two valid values for integer 0, which is what appears in ones
    > complement arithmetic.
    >
    > For argument, assume an 8-bit integer. The value of "5" would be
    > represented as 00000101. The one's complement negative would be
    > 11111010. So far there isn't any problem... But consider the value of
    > 0, represented as 00000000. A one's complement negative would become
    > 11111111 -- But mathematically, +0 = -0; in one's complement math, this
    > does not hold true.
    >
    > So a little trick is played, to create twos complement... To

    negate a
    > number, we take the ones complement, and then add 1 to the result. The
    > "5" then goes through: 00000101 -> 11111010 + 1 -> 11111011... Looks
    > strange, doesn't it... But watch what happens to that 8-bit 0: 00000000
    > -> 11111111 + 1 -> (overflows) 00000000.... Negative 0 is the same as
    > positive 0.


    [..]

    I have the impression (may be wrong) that you are working under the
    misconception that there can be a "natural" binary represensation of
    negative numbers!?
    Three conventions have commonly been used so far:
    1- Complement
    2-Complement
    Sign tag plus absolut binary values

    All of them have their pros and cons. For a mixture of very technical
    reasons (you mentioned the +0/-0 conflict, I might add the use of binary
    adders for subtraction) most modern computers use 2-complement, and this now
    leads to those funny speculations in this thread. ;-)

    Kindly
    Michael P
    Michael Peuser, Aug 17, 2003
    #6
  7. Michael Peuser fed this fish to the penguins on Sunday 17 August 2003
    02:41 pm:

    >
    > I have the impression (may be wrong) that you are working under the
    > misconception that there can be a "natural" binary represensation of
    > negative numbers!?


    Apologies if I gave that impression... the +/- 0 technical affair is
    the main reason I went into the whole thing...

    > Three conventions have commonly been used so far:
    > 1- Complement
    > 2-Complement
    > Sign tag plus absolut binary values
    >
    > All of them have their pros and cons. For a mixture of very technical
    > reasons (you mentioned the +0/-0 conflict, I might add the use of
    > binary adders for subtraction) most modern computers use 2-complement,
    > and this now leads to those funny speculations in this thread. ;-)
    >

    From a human readable standpoint, your third option is probably the
    most "natural"; after all, what is -19 in human terms but a "pure" 19
    prefaced with a negation tag marker... (I believe my college
    mainframe's BCD hardware unit actually put the sign marker in the
    nibble representing the decimal point location -- but it has been 25
    years since I had to know what a Xerox Sigma did for COBOL packed
    decimal <G>).

    ie, 00010011 vs -00010011 <G>

    1s complement is electrically easy; just "not" each bit.

    2s complement is mathematically cleaner as 0 is 0, but requires an
    adder to the 1s complement circuit... Though both complement styles
    lead to the ambiguity of signed vs unsigned values

    --
    > ============================================================== <
    > | Wulfraed Dennis Lee Bieber KD6MOG <
    > | Bestiaria Support Staff <
    > ============================================================== <
    > Bestiaria Home Page: http://www.beastie.dm.net/ <
    > Home Page: http://www.dm.net/~wulfraed/ <
    Dennis Lee Bieber, Aug 17, 2003
    #7
  8. "Michael Peuser" <> wrote in message
    news:bhosrr$u57$06$-online.com...

    | I have the impression (may be wrong) that you are working under the
    | misconception that there can be a "natural" binary represensation of
    | negative numbers!?
    | Three conventions have commonly been used so far:
    | 1- Complement
    | 2-Complement
    | Sign tag plus absolut binary values

    The last alternative sounds like what I was assuming. If it is, I would argue
    that it's pretty darn natural. Here's a little function to illustrate what I
    mean:

    def matilda(n): ## "my tilde"
    if 0<=n<pow(2,29):
    for i in range(1,31):
    iOnes=pow(2,i)-1
    if n<=iOnes:
    return iOnes-n
    else:
    raise
    Elaine Jackson, Aug 18, 2003
    #8
  9. In article <bhosrr$u57$06$-online.com>, Michael Peuser wrote:

    > I have the impression (may be wrong) that you are working under the
    > misconception that there can be a "natural" binary represensation of
    > negative numbers!?
    > Three conventions have commonly been used so far:
    > 1- Complement
    > 2- Complement
    > Sign tag plus absolut binary values
    >
    > All of them have their pros and cons. For a mixture of very technical
    > reasons (you mentioned the +0/-0 conflict, I might add the use of binary
    > adders for subtraction)


    The latter is _far_ more important than the former. Being able
    to use a simple binary adder to do operations on either signed
    or unsigned values is a huge savings in CPU and ISA design. I
    doubt that anybody really cares about the +0 vs. -0 issue very
    much (IEEE FP has zeros of both signs, and nobody seems to
    care).

    > most modern computers use 2-complement, and this now leads to
    > those funny speculations in this thread. ;-)


    --
    Grant Edwards grante Yow! An Italian is COMBING
    at his hair in suburban DES
    visi.com MOINES!
    Grant Edwards, Aug 18, 2003
    #9
  10. "Bengt Richter" <> schrieb im Newsbeitrag
    news:bhpjm1$g01$0@216.39.172.122...
    > On Sun, 17 Aug 2003 22:18:39 GMT, Dennis Lee Bieber

    <> wrote:
    >
    > >Michael Peuser fed this fish to the penguins on Sunday 17 August 2003
    > >02:41 pm:
    > >
    > >> I have the impression (may be wrong) that you are working under the
    > >> misconception that there can be a "natural" binary represensation of
    > >> negative numbers!?

    > >
    > > Apologies if I gave that impression... the +/- 0 technical affair

    is
    > >the main reason I went into the whole thing...
    > >
    > >> Three conventions have commonly been used so far:
    > >> 1- Complement
    > >> 2-Complement
    > >> Sign tag plus absolut binary values
    > >>
    > >> All of them have their pros and cons. For a mixture of very technical
    > >> reasons (you mentioned the +0/-0 conflict, I might add the use of
    > >> binary adders for subtraction) most modern computers use 2-complement,
    > >> and this now leads to those funny speculations in this thread. ;-)
    > >>

    > > From a human readable standpoint, your third option is probably

    the
    > >most "natural"; after all, what is -19 in human terms but a "pure" 19
    > >prefaced with a negation tag marker... (I believe my college
    > >mainframe's BCD hardware unit actually put the sign marker in the
    > >nibble representing the decimal point location -- but it has been 25
    > >years since I had to know what a Xerox Sigma did for COBOL packed
    > >decimal <G>).
    > >
    > > ie, 00010011 vs -00010011 <G>
    > >
    > > 1s complement is electrically easy; just "not" each bit.
    > >
    > > 2s complement is mathematically cleaner as 0 is 0, but requires

    an
    > >adder to the 1s complement circuit... Though both complement styles
    > >lead to the ambiguity of signed vs unsigned values
    > >

    > Everyone says "two's complement" and then usually starts talking about

    numbers
    > that are bigger than two. I'll add another interpretation, which is what I

    thought
    > when I first heard of it w.r.t. a cpu that was designed on the basis that

    all its
    > "integer" numbers were fixed point fractions up to 0.9999.. to whatever

    precision
    > the binary fractional bits provided. There was no units bit. And if you

    took one
    > of these fractional values 0.xxxx and subtracted it from 2.0, you would

    have a
    > complementary number with respect to two. Well, for addition and

    subtraction, that turns
    > out to work just like the "two's complement" integers we are used to. But

    since the
    > value of fractional bits were all in negative powers of two, squaring

    e.g., .5 had
    > to result in a consistent representation of 0.25 -- i.e. in binary

    squaring 0.1
    > resulted in 0.01 -- which is shifted one bit from what you get looking at

    the numbers
    > as integers with the lsb at the bottom of the registers and the result.
    >
    > I.e., a 32-bit positive integer n in the fractional world was n*2**-31. If

    you square
    > that for 64 bits, you get n**2, but in the fractional world that looks

    like (n**2)*2**-63,
    > where it's supposed to be (n*2**-31)**2 => (n**2)*2**-62 with respect to

    the binary point.
    > The fractional model preserved an extra bit of precision in multiplies.
    >
    > So on that machine we used to count bits from the left instead of the

    right, and place imaginary
    > binary points in the representations, so a binary 0.101 could be read as

    "5 at 3" or "2.5 at 2"
    > or "10 at 4" etc. And the multiplying rule was x at xbit times y at ybit

    => x*y at xbit+ybit.
    >
    > You can do the same counting the bit positions leftwards from lsb at 0, as

    we usually do now,
    > of course, to play with fixed point fractions. A 5 at 0 is then 1.25 at 2

    ;-)
    >
    > Anyway, my point is that there was a "two's complement" implementation

    that really meant
    > a numeric value complement with respect to the value two ;-)
    >
    > Regards,
    > Bengt Richter



    A very good point! I might add that this is my no means an exotic feature.
    Mathematically speaking there is great charme in computing just inside the
    invervall (-1,+1). And if you have no FPU you can do *a lot* of pseudo real
    operations. You have get track of the scale of course - it is a little bit
    like working with sliding rules if anyone can remember those tools ;-)

    Even modern chips have support for this format, e.g. there is the 5$ Atmel
    Mega AVR which has two kinds of multiplication instructions: one for the
    integer multiplication and one which automatically adds a left shift after
    the multiplication! I leave it as an exercise to find out why this is
    necessary when multiplying fractional numbers ;-)

    Negative numbers are formed according to the same rule for fractionals and
    integers:
    Take the maximum positive number: 2**32-1 or 0.999999
    Extend your scope
    Add one bit: 2*32 or 1
    Double it: 2*33 or 2
    Subtract the number in question
    Reduce your scope again

    Kindly Michael P
    Michael Peuser, Aug 18, 2003
    #10
  11. In article <bhq01j$tge$03$-online.com>, Michael Peuser wrote:

    > A very good point! I might add that this is my no means an exotic feature.
    > Mathematically speaking there is great charme in computing just inside the
    > invervall (-1,+1). And if you have no FPU you can do *a lot* of pseudo real
    > operations. You have get track of the scale of course - it is a little bit
    > like working with sliding rules if anyone can remember those tools ;-)


    Sure. I've got two sitting at home. :)

    FWIW, it used to be fairly common for process-control systems
    to define operations only over the interval (-1,+1). This made
    implimentation easy, and the input and output devices
    (temp/pressure sensors, valves, whatnot) all had pre-defined
    ranges that mapped logically to the (-1,+1) interval.

    --
    Grant Edwards grante Yow! The SAME WAVE keeps
    at coming in and COLLAPSING
    visi.com like a rayon MUU-MUU...
    Grant Edwards, Aug 18, 2003
    #11
  12. "Grant Edwards" <> schrieb im Newsbeitrag
    news:3f40d077$0$164$...
    > In article <bhq01j$tge$03$-online.com>, Michael Peuser wrote:
    >
    > > A very good point! I might add that this is my no means an exotic

    feature.
    > > Mathematically speaking there is great charme in computing just inside

    the
    > > invervall (-1,+1). And if you have no FPU you can do *a lot* of pseudo

    real
    > > operations. You have get track of the scale of course - it is a little

    bit
    > > like working with sliding rules if anyone can remember those tools ;-)

    >
    > Sure. I've got two sitting at home. :)
    >
    > FWIW, it used to be fairly common for process-control systems
    > to define operations only over the interval (-1,+1). This made
    > implimentation easy, and the input and output devices
    > (temp/pressure sensors, valves, whatnot) all had pre-defined
    > ranges that mapped logically to the (-1,+1) interval.
    >
    > --

    Yes it simplifies a lot of matters, even when using full floating point
    numbers. Take OpenGL e.g. The colour space is a 1x1x1 cube. Very fine! No
    magic numbers near 256 ;-)

    Kindly
    Michael P
    Michael Peuser, Aug 18, 2003
    #12
  13. Grant Edwards fed this fish to the penguins on Monday 18 August 2003
    06:11 am:

    >
    > Sure. I've got two sitting at home. :)
    >

    Only two? <G>

    I've got five (the most recent, new-in-box, cost me more than I paid
    for an HP25 back in 1978 <G>)... Regretably, I missed my chance at a
    lovely plastic over bamboo laminate back then... As I recall, a
    deci-trig log-log model, being cleared out by my college bookstore at
    half price (which put it about $25 -- the HP25 was $100 or so, and also
    a clear-out as no one else was smart enough to buy an RPN calculator).

    --
    > ============================================================== <
    > | Wulfraed Dennis Lee Bieber KD6MOG <
    > | Bestiaria Support Staff <
    > ============================================================== <
    > Bestiaria Home Page: http://www.beastie.dm.net/ <
    > Home Page: http://www.dm.net/~wulfraed/ <
    Dennis Lee Bieber, Aug 20, 2003
    #13
    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:
    437
    J. Campbell
    Nov 15, 2003
  2. Mantorok Redgormor

    bitwise not operator

    Mantorok Redgormor, Oct 1, 2003, in forum: C Programming
    Replies:
    1
    Views:
    523
    Dan Pop
    Oct 1, 2003
  3. Tim Peters

    RE: bitwise not - not what I expected

    Tim Peters, Aug 17, 2003, in forum: Python
    Replies:
    3
    Views:
    503
    Carl Banks
    Aug 17, 2003
  4. Tim Peters

    RE: bitwise not - not what I expected

    Tim Peters, Aug 18, 2003, in forum: Python
    Replies:
    2
    Views:
    305
    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:
    256
    David Garamond
    Feb 25, 2004
Loading...

Share This Page