Good explanation on why x-1 "looks" the way it does in binary

Question

Let's take the number 28 in binary:

0b11100     # 28

If we subtract 1 from the number it looks like this:

0b11011     # 27

How I would explain how it 'looks' is that when subtracting 1 from a number, the right-most 1-bit is set to zero and all zeros after it are set to one. For example:

  0b10101 - 1
= 0b10100

---

  0b01000 - 1
= 0b00111

---

  0b10000000 - 1
= 0b01111111

What would be the best explanation as to why this occurs though? I'm sure it's a property of binary twos complement, but I'm trying to figure out the best way to explain this to myself so that I can gain a deeper understanding of it.

Answer 1

It does not matter what base you are in, the math does not change:

  1000 
- 0001
========

This is base 10, easier to see:

  1  0  0  0 
- 0  0  0  1
=============

We start in the ones column (base to the power 0), the top number is smaller than the bottom so we have to borrow, but what we find is that next column does not have anything and so on so we have to work over until we can borrow something, that value is base larger than the column it is in so if you borrow from the hundreds column into the tens column that is 10 tens so:

So first borrow:

  0 10  0  0 
- 0  0  0  1
=============

Second borrow:

  0  9 10  0 
- 0  0  0  1
=============

Third borrow:

  0  9  9 10 
- 0  0  0  1
=============

And now we can work the base to the power one column:

  0  9  9 10 
- 0  0  0  1
=============
           9

And in this case can easily finish it up:

  0  9  9 10 
- 0  0  0  1
=============
  0  9  9  9

So base 5:

    1  0  0  0
 -  0  0  0  1
===================

    0  5  0  0
 -  0  0  0  1
===================

    0  4  5  0
 -  0  0  0  1
===================

    0  4  4  5
 -  0  0  0  1
===================


    0  4  4  5
 -  0  0  0  1
===================
    0  4  4  4

And base 2:

   1  0  0  0
-  0  0  0  0 
==============

   0 10  0  0
-  0  0  0  0 
==============

   0  1 10  0
-  0  0  0  0 
==============

   0  1  1 10
-  0  0  0  0 
==============

   0  1  1 10
-  0  0  0  0 
==============
   0  1  1  1

Twos complement comes into play when you actually implement this in logic, we know from elementary programming classes that when we talk about "twos complement" we learn to "invert and add one" to negate a number. And we know from grade school math that x - y = x + (-y) so:

     0
  1000
- 0001
=======

This is the same as:

     1 <--- add one
  1000
+ 1110 <--- invert
=======

Finish:

 10001
  1000
+ 1110
=======
  0111

So for subtraction you invert/ones complement the second operand and the carry in and feed these to an adder. Some architectures invert the carry out and call it a borrow, some just leave it unmodified. When doing it this way as we see above the carry out is a 1 if there was NO borrow. It is a zero if there was a borrow.

I believe this is a base 2 thing only due to having only zero or one. How do you invert a base 10 number? 1000 - 1 = 1000 + 9998 + 1, hmm actually that works.

So base 10 100 - 1 = 99, base 9 100 - 1 = 88, base 8 (octal) 100 - 1 = 77, base 7 100 - 1 = 66 and so on.

Answer 2

Binary numbers have general form of N = dn x b^n + dn-1 x b^n-1… d1 x b^1 + d0 x b^0 where b is a base (2), d is a digit < base (0, 1) and n is position.

We write down binary numbers without b (because we know that's always 2) and also without its n exponent which goes implicitly from 0 for least significant digit (rightmost), 1 next to rightmost, etc.

For example your number 28 is 1x 2^4 + 1x 2^3 + 1x 2^2 + 0x 2^1 + 0x 2^0 = 1x 16 + 1x 8 + 1x 4 + 0x 2 + 0x 1 .

In binary:

• 1 - 1 = 0
• 0 - 1 = 1 and you carry that - 1 to the next position on left (same as when you do 10 - 1 in decimal, 0 - 1 is 9 and carry - 1 to order of tenths)

When subtracting 1 you go from the rightmost position, if there's 0 you turn it to 1 and carry subtraction up to next (left) position (and that chains all the way left until you find position where you can subtract without affecting higher position)

0b01000 - 1 can be written as 0x 2^4 + 1x 2^3 + 0x 2^2 + 0x 2^1 + 0x 2^0 - 1 x 2^0. In plain decimal that is 8 - 1 = 7 and 7 in binary is 0x 2^4 + 0x 2^3 + 1x 2^2 + 1x 2^1 + 1x 2^0 (4 + 2 + 1)