What is two's complement?

We all know how positive decimal numbers (like 65) are represented in binary format, don’t we? (If you don’t remember, no worries. We’ll go through that shortly.) But the question is how are negative decimal numbers (like -65) represented in binary?

Two’s complement is one of the many schemes (and one of the widely used these days) to represent negative numbers in binary format.

⚡ In this post when I say decimal, I mean numbers represented in base 10.

Binarify

Is that even a valid word? Well I don’t know nor care. Anyways before getting into representing negative decimals I just want to quickly go over how to represent a positive decimal number in a binary format, just so we are all on the same page. If you’re already familiar with it please skip to the next section.

To calculate binary representation of a given positive integer, you divide the number by 2 and note down the quotient and remainder. Then divide the quotient by 2 and note the quotient and remainder again. Repeat this process until the quotient is 0. Then write down your remainder in reverse order and that is the binary representation of your number.

Divide by    Quotient   Remainder
        2  )  65        1   
        2  )  32        0   
        2  )  16        0 
        2  )   8        0 
        2  )   4        0 
        2  )   2        0   
        2  )   1        1   ↑
        2  )   0        

So 65 can be represented in binary as 1 0 0 0 0 0 1. And if the number is represented in 8-bits then we can pad it with a 0 like 0 1 0 0 0 0 0 1 (notice I added padding at the start).

Two’s complement

So we nailed the binary representation of positive integer. How about the negative integer?

One thing we know is that many programming languages use signed integers these days. What does that mean? It means that they store the sign (positive/negative) of the integer on the first bit. If the first bit is 0 that means the number is positive, if it is 1 that means the number is negative. But how about other bits?

Actually to find the binary representation of negative integer -n, you just find the two’s complement of integer n and that’s it.

And how do we calculate two’s complement of n? It’s very easy:

1. Invert the value for each bit of n
2. Then add 1

For example we looked at binary representation of 65 above - 0 1 0 0 0 0 0 1. Now lets use that to figure out the binary representation of -65 by calculating two’s complement.

    0 1 0 0 0 0 0 1  ⇐ (binary representation of 65)
    ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
    1 0 1 1 1 1 1 0  ⇐ (invert the bits - from 0 to 1 and 1 to 0)
   +              1  ⇐ (add 1)
   -----------------
    1 0 1 1 1 1 1 1  ⇐ (binary representation of -65)

Easy aye? If you are happy with how to calculate the two’s complement and don’t really care about how it works or why it works, good bye. Thanks for stopping by, I will see you at a later post. But if you are thinking - “this is absolutely crazy, why is it done this way?”, then stick around and I will try to explain this little further.

Remember elementary school?

Lets think about negative numbers in decimal. -65 is same as 0 - 65. This is true in binary also. So to figure out binary for -65 we can just do 0 minus the binary of 65. Let’s do the math.

If you don’t remember how to do binary substraction, please check it out. Basically its similar to decimal substraction - if you don’t have enough to subtract from, you carry over and substract. Also 1 - 1 = 0, 0 - 0 = 0, 10 - 1 = 1

Below I show you step by step by substracting 0 and binary representation of 65.

                1   
    0 0 0 0 0 0 0 0
  - 0 1 0 0 0 0 0 1 
  --------------------
                  1
    

              1 1  
    0 0 0 0 0 0 0 0
  - 0 1 0 0 0 0 0 1 
  --------------------
                1 1
    

            1 1 1   
    0 0 0 0 0 0 0 0
  - 0 1 0 0 0 0 0 1 
  --------------------
              1 1 1
    

          1 1 1 1   
    0 0 0 0 0 0 0 0
  - 0 1 0 0 0 0 0 1 
  --------------------
            1 1 1 1
    

        1 1 1 1 1  
    0 0 0 0 0 0 0 0
  - 0 1 0 0 0 0 0 1 
  --------------------
          1 1 1 1 1
    

      1 1 1 1 1 1  
    0 0 0 0 0 0 0 0
  - 0 1 0 0 0 0 0 1 
  --------------------
        1 1 1 1 1 1
    

    1 1 1 1 1 1 1  
    0 0 0 0 0 0 0 0
  - 0 1 0 0 0 0 0 1 
  --------------------
      0 1 1 1 1 1 1
    

  1 1 1 1 1 1 1 1  
    0 0 0 0 0 0 0 0
  - 0 1 0 0 0 0 0 1 
  --------------------
    1 0 1 1 1 1 1 1
    

Notice that the result from this calculation is exactly same as the result of caculating two’s complement. Whooaa!

How/Why?

Two’s complement is really a magic trick. It’s a very neat shortcut for doing the above elementary math. But how does it work? Let’s think about how our computer does the math. If our computer stores integer as 8-bits binary and we ask it to substract one 8-bit binary from 9-bit binary it will happily ignore first bit from our 9-bit binary. So substracting any 8-bit integer from 0 0 0 0 0 0 0 0 is exactly same as substracting from 1 0 0 0 0 0 0 0 0 (this has 9-bits and first bit is 1). Our computer just ignores the first bit which is 1.

So 0 0 0 0 0 0 0 0 - n yields the same result as 1 0 0 0 0 0 0 0 0 - n. Now 1 0 0 0 0 0 0 0 0 can also be represented as 1 + 1 1 1 1 1 1 1 1. So in effect 0 0 0 0 0 0 0 0 - n yields same result as 1 + 1 1 1 1 1 1 1 1 - n. And one of the neat things about substracting any binary from another binary with all 1s is that it’s exactly same as reverting the bits (0 to 1 and 1 to 0). So 1 1 1 1 1 1 1 1 - n is same as reverting every bits of n. You don’t have to believe me on this, you can just try!

In summary, substracting any binary number n from 0 is exactly same as reverting all the bits of n and adding 1 to the result - which is exactly what we did to calculate the two’s complement.