Understand functions in figure 2.5b: y + 1

[charleszzx]

I tried to verify one particular row (y + 1) in figure 2.5b (second edition of the book) using the control bits, but I can't seem to arrive at y + 1. My progress is as follow:

Since zx and nx are both 1, x is updated to -1.

Since zy=0, ny=1, y is updated to !y.

Since f = 1, out = -1 + !y.

Finally, we negate the result: out = !out= !(-1 + !y) = (!-1 + !!y) = 0 + y = y.

!-1 = 0 because we flip all bits in -1, which is 0. !!y = y is straightforward.

Could someone point out which step I got wrong in the above computation? Thanks for the help!

[ashort]

The way I see it, it does this:

-sets x to 0
-sets x to !0, which is 1111 1111 1111 1111 (-1)
-sets y to !y
-adds -1 and !y, which is the same as !y-1
-flips the bits from the sum above.

In other words, we take !y, subtract 1, then flip all the bits.   Anytime you subtract 1 then flip all the bits, you have the 2's complement.

So this is the 2's complement of !y.  The 2's complement can also be thought of as you flip all bits, then add 1. If you flip all bits of !y you get y.  Now add 1.  You get y+1

(You seem to be using the distributive property on the ! bitwise operator across the sum. It's been too long since I've taken the course, so I leave it to someone else to explain why that doesn't work)

[WBahn]

bitwise negation does not distribute over addition.

Consider the following example (let's use 4-bit values for simplicity):

x = 5 (0b0101)

So what is !(x + -1)?

Now let's do 5 + -1, which is 4, or 0b0100.

If we negate this we get 0b1011

Now let's distribute the negation to get !x + !-1.

!x would be 0b1010 and !-1 would be 0, so the result would be 0b1010, which is different.


The proper way to relate negation to 2's complement math is as follows:

By definition of 2's complement, for an N-bit representation of x,

x + (-x) = 2^N (which is the same representation as 0 since the msb of 2^N is lost). So

-x = 2^N - x

But 2^N = (2^N - 1) + 1, so

-x = [(2^N - 1) - x] + 1

(2^N - 1) is a pattern of N 1-bits (i.e., all ones).

If we subtract x from a pattern of all ones, we get !x, so

-x = !x + 1

This is a common way of implementing 2's complement arithmetic inverse.

Rearranging this:

!x = -x - 1

[charleszzx]

Thanks! The following is my updated steps:

!(!y - 1) = !(-y - 1 - 1) , since !y = -y - 1
!(-y - 1 - 1)  = !(-y - 2),
!(-y - 2) = -(-y - 2) - 1, again, since !something = -something - 1
-(-y - 2) - 1 = y + 2 - 1 = y + 1

Hope that helps!

[WBahn]

Good job.

I wish the authors covered this more deeply, but I suspect their position would be that this is simply one of the things that needs to be done at a superficial level in order to fit everything that is critical into a one-semester course. Hard to argue with that.