Two's complement but no flipping bits

Question

In my one class we learned about two's complements. I know there's one way to do it flipping bits and adding 1, but last time in class at the end the instructor said no flipping bits and adding one in the class.

I've looked all over and through my notes and I can't figure out another way to do it. The instructor is away for the weekend so I can't just ask her how she meant to do it. How else would you do this?

Answer 1

Suppose that your number has $n$ bits. Then taking the two’s complement can be done by subtracting it from $2^n$. For example, the two’s complement of $1101$ is

$$10000-1101=0011\;.$$

Note that the binary representation of $2^n$ is a $1$ followed by $n$ zeroes.

To see why it works, imagine that you start with a bit string $b_1b_2\ldots b_n$. After you flip the bits, you have another string, $\bar b_1\bar b_2\ldots\bar b_n$, say. If you add those two strings you get

$$\underbrace{11\ldots11}_{n\text{ ones}}\;.$$

Thus, if you flip the bits to get $\bar b_1\bar b_2\ldots\bar b_n$ and add $1$ to get the two’s complement, adding this two’s complement to the original string $b_1b_2\ldots b_n$ will give you

$$\underbrace{11\ldots11}_{n\text{ ones}}+1=1\underbrace{00\ldots00}_{n\text{ zeroes}}\;,$$

the binary representation of $2^n$. Consequently, you can get the two’s complement simply by performing the subtraction

$$1\underbrace{00\ldots00}_{n\text{ zeroes}}-b_1b_2\ldots b_n\;.$$

Answer 2

You can add $1$ until the register busts, and then count how many $1$'s you have added.

e.g. $10101+1=10110, 10110+1=10111, 10111+1=11000,\dots,=11111,11111+1=busted$

We added $1011$ ones.

Answer 3

Another alternative is to start from the left and flip everything up to but not including the last 1.

Some examples using 8-bits:

$12=00001100$ so $-12=\color{red}{11110}100$

$38=00100110$ so $-38=\color{red}{110110}10$

$96=01100000$ so $-96=\color{red}{10}100000$