aspose file tools*
The moose likes Beginning Java and the fly likes Using ~ (Unary bitwise complement) for Zero Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Using ~ (Unary bitwise complement) for Zero" Watch "Using ~ (Unary bitwise complement) for Zero" New topic
Author

Using ~ (Unary bitwise complement) for Zero

Pranav Raulkar
Ranch Hand

Joined: Apr 20, 2011
Posts: 73

I wrote a program to find 0's complement and found out that its -1.

So I get it that ~ is giving me 2's complement. But what I dont understand how is 0's 2's complement is -1.

   00000000 is 0
   11111111 is 1's complement
1 00000000 is 2's complement of above where carry 1 is ignored.

So why the result is -1 (11111111)

If 1's complement was used then it would give me -0 which is wrong.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 36453
    
  15
The ~ operator does not give you a two’s complement. It simply inverts every bit. It is similar to one’s complement. So 0000_0000 turns into 1111_1111, which is exactly what you have shown.
Pranav Raulkar
Ranch Hand

Joined: Apr 20, 2011
Posts: 73

And 11111111 represents -1 in binary?
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3366
    
    9
In Java's representation (which uses two's complement), yes.
Pranav Raulkar
Ranch Hand

Joined: Apr 20, 2011
Posts: 73

So in java 2's complement for 0 is 11111111 which is -1. Agreed.
But if you calculate 2's complement it comes out to be 00000000. Correct me if I'm wrong from my first post.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10908
    
  12

Pranav Raulkar wrote:So in java 2's complement for 0 is 11111111 which is -1. Agreed.

WRONG.

~0 is NOT two's compliment, it simply flips every '0' bit to '1', and every '1' bit to '0'.


In Java, 2's compliment for 0 is 0. In fact, in ANY language, 2's compliment of 0 is 0, as 2's compliment is an algorithm, not a language specific feature.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 36453
    
  15
Pranav Raulkar wrote:So in java 2's complement for 0 is 11111111 which is -1. Agreed.
No. Not at all. I think you have misunderstood two’s complement arithmetic. The two’s complement representation of 0 is 0000_0000 (in 8 bits). The two’s complement of 0 is not 1111_1111. Never.

This is how two’s complement numbers are worked out:
  • You work out the range of numbers available: for 8 bits that is 256
  • You allow exactly half that range for negative numbers: -1 to -128 inclusive.
  • You allow exactly the other half of the range for non-negative numbers: 0 to 127 inclusive.
  • For non-negative numbers, use exactly the same format as for unsigned numbers, 0000_0000 to 0111_1111 inclusive.
  • For negative numbers, subtract the absolute value from the size of the range.
  • You can work out the two’s complement value of a negative number by subtracting its absolute value from the size of the whole range.
  • For example: the two’s complement representation of -97 is the same as the unsigned representation of 256 - 97, or 1_0000_0000 - 0110_0001

  • That is how complementary numbers are really defined.
    If you try that calculation, you get this for -97:
    1_0000_0000
      0110_0001-
      1001_1111

    There are at least two other ways you can think of a two’s complement number (still in 8 bits):
    One way: The leftmost bit (no 7) represents -2^7 (-128)or 0, the next bit represents (+)64 or 0, then (+)32 or 0, etc until the rightmost bit (the 0-th bit) represents (+)1 or 0. So 1001_1111 means -128 + 0 + 0 + 16 + 8 + 4 + 2 + 1 = -97.

    The other way is to remember that 256 - 97 = 256 - 1 - 97 + 1. The -1 and +1 cancel out, but look good in binary.
    256 - 1 looks like this:
    1_0000_0000
      0000_0001-
      1111_1111
    . . . 255 in unsigned numbers.

    Now you can subtract 97 from 255
    1111_1111
    0110_0001-
    1001_1110


    Now you add 1 again
    1001_1110
    0000_0001+
    1001_1111
    . . . and lo and behold, we have -97

    Did you notice that subtracting from 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 is the same as swapping all the bits? So, you can get something identical to two’s complement by swapping all the bits and adding 1. If you try complementing 0 to -1 and adding 1, you get 0. Try it

    But if you calculate 2's complement it comes out to be 00000000. Correct me if I'm wrong from my first post.
    No, you are not calculating a two’s complement at all. What you are doing is taking the bit pattern, eg 0110_0001 for 97 and 0000_0000 for 0 (in 8 bits) and getting the complement of that bit pattern. That is equal to -(i + 1). As you saw above, 97 turns into -98 and 0 turns into -1.
    Pranav Raulkar
    Ranch Hand

    Joined: Apr 20, 2011
    Posts: 73

    OK I got this from wiki

    In two's-complement, there is only one zero (00000000). Negating a number (whether negative or positive) is done by inverting all the bits and then adding 1 to that result.

    Can you put up a claculation just like you did for -97 for complement of zero?
    fred rosenberger
    lowercase baba
    Bartender

    Joined: Oct 02, 2003
    Posts: 10908
        
      12

    Note: There is a difference between the "complement" and the "two's compliment". I assume you want the latter.

    0 is

    0000 0000 0000 0000 (i'm only going to use 16 bits, but it works the same for 32, or 64 or however many bits you want)

    invert all the bits, you get

    1111 1111 1111 1111

    add 1:



    but that left-most 1 doesn't fit. We run out of bits, so it falls off the end, leaving us with

    0000 0000 0000 0000

    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 36453
        
      15
    Pranav Raulkar wrote: . . . Can you put up a claculation just like you did for -97 for complement of zero?
    Fred has already done that, only for 16 bits. It is exactly the same, but occupies more space on the screen.
    The wikipedia article about two’s complement is slightly imprecise. Two’s complement is made by subtracting from 2^i where i is the number of available bits. Inverting each bit and adding one is not how it is defined, but always gives the same result, provided the numbers are within the range -2^(i - 1)...2^(i - 1) - 1.
    Pranav Raulkar
    Ranch Hand

    Joined: Apr 20, 2011
    Posts: 73

    Agreed! Complement and 2's complement are different.
    If we do complement of 0 its 11111111 which is 255.
    since ~ is complement operator ~0 should give me 255. Why -1? If its giving me -1 it means ~ is 2's complement.
    But we all know 2's complement for 0 is 00000000 (Carry over 1 is discarded)

    I'm so LOST!
    fred rosenberger
    lowercase baba
    Bartender

    Joined: Oct 02, 2003
    Posts: 10908
        
      12

    Again, you're making a few faulty assumptions here.

    the complement of 0 will slightly depend on whether you have an int or a long. an int is 32 bits, and a long is 64 bits. so, 0 will be either

    0000 0000 0000 0000 0000 0000 0000 0000

    or

    0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000

    the complement will be (for the int)

    1111 1111 1111 1111 1111 1111 1111 1111

    To determine the value, you have to do the following:

    look at the left most bit. If it is a zero (it our case it isn't), you simply add up the powers of 2 that correspond to the 1's, and the value is positive.

    if the left-most bit IS a 1, your result will be negative. next, take the 2's complement of the number. So, we flip all the bits, and add 1. so it becomes

    0000 0000 0000 0000 0000 0000 0000 0000
    + 1
    =============================
    0000 0000 0000 0000 0000 0000 0000 0001

    So "1111 1111 1111 1111 1111 1111 1111 1111" represents "-1".
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 36453
        
      15
    1111_1111 is only 255 in unsigned binary numbers. It is meaningless to say something like “1010_1010 means xyz”, without saying what format you are using, and what memory size. There are at least four formats for binary integers, possibly five if you include one’s complement. In two’s complement in eight bits, 1111_1111 means -1decimal.
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 36453
        
      15
    I have already told you, and I think Fred has too, that the ~ operator does not produce the two’s complement. It returns the bit pattern inverted, which is more akin to one’s complement. So you get the one’s complement of 0 which in two’s complement returns -1decimal. Remember you had to add 1 to ~97 to get -97.
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 36453
        
      15
      0000_0000   Flip the bits. What the ~ operator does, giving the result on the next line.
      1111_1111   That returns -1decimal, but to get that into two’s complement, add 1, and the 8th bit vanishes into cyber-limbo never to be seen again.


    1_0000_0000   Now we get back to 0. But that isn’t what the ~ operator does. It only does what you saw one line up.
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Using ~ (Unary bitwise complement) for Zero
     
    Similar Threads
    lang fund Ques from dan mock exam
    10 >> -2
    Bitwise complement operator
    >>> Operator
    Unsigned Right Shift