Confused about two's complement with ALU.

[HighSchoolerWhoAsksHowTooMuch]

Hi.

It says in the book that to take a negative of a number, you flip every bit and then add 1. Why is it for the ALU you only flip the number?

Thanks!

[ashort]

The ALU can "negate" a number, and it can also do a "bitwise not".  They are different.

Negating a number is like going from -7 to 7, or from 7 to -7.    If numbers are stored in 2's complement, it's easy to negate a number, you just flip all the bits, then add 1.  (or you can subtract 1, then flip all the bits).  When you study 2's complement, you'll see why this works like magic.

Bitwise not is simply flipping all the bits.

[WBahn]

The problem you run into is that (flipping all the bits) and (add one) are two different operations that can't be done at the same time in the Hack architecture. Most architectures use an adder that has a carry-in bit and so you can get the (add one) for free at the same time that you flip all the bits. The Hack can't do that.

But what the Hack CAN do is flip all the bits on either input AND on the output. That's the key to the Hack being able to negate (i.e., take the 2's complement additive inverse) of a number.

[HighSchoolerWhoAsksHowTooMuch]

Thank you both for replying. I think I understand now. When using the ALU, I will be flipping and then adding 1 in order to form a two's compliment, instead of the ALU being able to do the entire process in one step.

[WBahn]

Why?

The Hack is able to negate a number in a single instruction just fine. It merely doesn't do it by flipping the bits and adding one. Instead, it uses it's other capabilities to produce the same result.

Look at the Hack instruction set, specifically the -A, -D, and -M instructions.

The key is to note the relationship between bitwise inversion and two's complement arithmetic.

If we use !x to indicate the bitwise inverse of x (i.e., flipping all the bits) and -x to indicate the arithmetic inverse of x (i.e., the number such that x + -x = 0) then we have

-x = (!x) + 1

The old "flip the bits and add one" description of arithmetic inverse in two's complement.

This means that

!x = -x - 1

Let's now consider what the arithmetic result is if we configure the Hack ALU to perform the following:

out = !(x + !0)

In other words, for y to be zero and then invert it, add this to x, and then invert the ALU output.

out = !(x + !0)
out = !(x + (-0-1))
out = !(x - 1)
out = -(x-1) - 1
out = -x

[ashort]

Another way to look at it, is to consider the line:

out = !(x - 1)

This is like saying let’s subtract 1 then flip all the bits.  All in one Hack instruction.

And that is one way to get the 2’s complement of a number.

[HighSchoolerWhoAsksHowTooMuch]

This is very interesting and I think I understand how the Alu will be implemented. It takes only 1 instruction to negate. Some alus, but not the hack alu, can do this in 1 step.

[WBahn]

HighSchoolerWhoAsksHowTooMuch wrote

This is very interesting and I think I understand how the Alu will be implemented. It takes only 1 instruction to negate. Some alus, but not the hack alu, can do this in 1 step.

I don't understand the conclusion you appear to have drawn. The Hack ALU most definitely CAN negate in one step. We've shown how it is done. It merely uses different capabilities to do so.

[rleininger]

I guess it depends on what you mean by one step.  The Hack ALU certainly requires only one Hack machine instruction  to negate a number supplied as input to the ALU.  There are actually 2 versions of an instruction that that does this - to arithmetically negate either the x-input or the y-input of the ALU.

I guess you could think of "steps" in terms of the individual logical elements required to actually execute the instruction as identified in the ALU specification provided in Figure 2.5b (2nd edition of the book).  This is shown for educational purposes in the annotated snip below.



For example, there are six actions that must happen to produce the negative of a value provided to the x-input of the ALU.  You might consider these "steps", although the authors don't refer to them in that way.  As far as I can tell, the term "steps" is undefined in the context of the Hack computer.  If this is the sense in which HighSchoolerWhoAsksHowTooMuch means "steps", then his statement about the number of steps the Hack ALU requires to negate a number seems correct.  By the same token then, a "step" and an "instruction" must now mean entirely different things.

WBahn is absolutely correct in saying that only one instruction is required to negate a number because all the logic to do so is completely executed in a single clock cycle.  His algebraic description of how the negation is produced kind of describes these "steps".  The ALU, in "Step 5", adds -1 (produced at y-input by "steps" 3 and 4) to the number to be negated at the x-input (unchanged by "steps" 1 and 2), then "flips" the bits of that sum ("step" 6) to create the ALU output for the instruction.  All this happens in a single clock cycle in the Hack ALU.  The original confusion, I think, results from the way the ALU does negation.  It's conceptually different from the way the authors describe how to do it in their discussion of 2's complement arithmetic.  As WBahn has pointed out, the same result is produced either way.

[HighSchoolerWhoAsksHowTooMuch]

I see the confusion. I was talking about steps not clock cycles. Thank you both!

[ashort]

I encourage you to go through the table rleininger provided and ask yourself why those various bit manipulations produce the desired output.   Some of it seems crazy and convoluted, but it works.  It’s a lot of fun and very instructive to see why and how each one works

[WBahn]

HighSchoolerWhoAsksHowTooMuch wrote

I see the confusion. I was talking about steps not clock cycles. Thank you both!

Then an ALU that uses the carry-in bit to perform the add 1 is also taking multiple steps. The inversion happens before the value is applied to the input of the adder.

Virtually all logical operations require multiple "steps" in that sense.