0

Assume we use 3 bits to subtract 1 from 0:

  0b000
- 0b001
  ------
  0b111

I have the following 2 questions:

1- Where is the borrowed 1 into the MSB coming from? When we do 0b000 - 0b001, the MSB of the first operand is a 0 so there is nothing to borrow from, hence in this case the carry flags get set and a 1 gets borrowed into the MSB of the first operand (which makes the output negative). Where is the 1 coming from? it just comes form thin air and a flag gets set? is it a math rule just to "borrow" a 1 in this case and make the output negative? There is this exact same question I found but the selected answer doesn't really answer the question: Subtracting 1 from 0 in 8 bit binary

2- I've read there are two ways to do subtraction in hardware. Either turn a - b into a + (-b) and use the adders, or use the borrow method.

This answer talks about using the adders: https://stackoverflow.com/a/5793952

This answers talks about an actual subtractor being used in x86 as flags needs to be set properly and the previous method won't work: https://stackoverflow.com/a/62219965/14940626

So which one is it? does x86 use the latter and MIPS (as an example) uses the former method?

Dan
  • 2,694
  • 1
  • 6
  • 19
  • 1
    See https://en.wikipedia.org/wiki/Adder%E2%80%93subtractor - doing `a + (~b) + 1` with the +1 as a carry-in apparently works, including producing the correct borrow output and probably even signed-overflow. – Peter Cordes Aug 03 '21 at 02:13
  • Interesting, this answers also mentions something similar: https://stackoverflow.com/a/56279548/14940626 – Dan Aug 03 '21 at 02:16
  • So it's safe to say x64 also implements the `a + (-b)` method when doing a subtraction? – Dan Aug 03 '21 at 02:22
  • Borrow is an *output* that propagates from LSB to MSB, it doesn't matter what's to the left, but that's a separate question from how ALUs are built. – Peter Cordes Aug 03 '21 at 02:22
  • No, `a + (-b)` is an oversimplification that wouldn't generate the correct OF and CF outputs. It has to do `a + (~b) + 1` with the +1 as a carry input to a chain of full adders (https://en.wikipedia.org/wiki/Adder%E2%80%93subtractor) so there's only one addition-like operation, with only simple bit-flipping in parallel on one of the inputs. And because x86-64 has to set CF = borrow on subtraction, it has to invert the carry output as old_timer explained on your previous question ([How is overflow detected when doing binary subtraction](https://stackoverflow.com/a/68598762)) – Peter Cordes Aug 03 '21 at 02:25
  • thanks, so `a + (~b) + 1` is the generic method which subtraction is done using adders. Now regarding `Borrow is an output that propagates from LSB to MSB`, i don't really understand what you mean by it. Mathematically you find the first `1` on your left, turn it into 0, then propagate `2` into the right hand bits where it was needed. In my example there is no `1` to cross anywhere, it's all 0s. – Dan Aug 03 '21 at 02:28
  • No, there's never a `2`, this is binary logic so everything is either 0 or 1. Borrow propagates left flipping 0 to 1 until it hits a 1. If there isn't one, it propagates arbitrarily far, through as many bits as you want to calculate, setting them all to `1`. That's how 2's complement works, and why 2's complement sign-extension works by prepending copies of the sign bit. – Peter Cordes Aug 03 '21 at 02:32
  • This is what I mean: `When a borrow out is generated, 2 is added in the current digit. (This is similar to the subtraction algorithm in decimal. Instead of adding 2, we add 10 when we borrow.)` https://en.wikipedia.org/wiki/Subtractor – Dan Aug 03 '21 at 02:34
  • And this is how I know binary subtraction: https://youtu.be/sJXTo3EZoxM?t=1119 , I just want to know where a borrowed 1 comes from in this case. sorry I might be having a difficulty communicating my question. – Dan Aug 03 '21 at 02:35
  • Borrow doesn't "come from" anywhere, just like carry doesn't "go anywhere" when you get to the last bit in whatever fixed precision you're using. In arbitrary precision, you'd have an infinite number of leading 1s from propagating the borrow infinitely, i.e. a 2's complement negative number. But in fixed-width like CPUs use, it's just an output. (Which you can chain into a `sbb` instruction that takes a borrow input, allowing you to implement subtraction wider than a register). There's no answer to the "where does it come from" question because that's the wrong concept. – Peter Cordes Aug 03 '21 at 03:34
  • `it's just an output` but it's an output of what? Let's put CPUs aside and do he math by hand like the above video. It simply puts a `1` down or "borrows" a 1 from somewhere when there's nothing to borrow from. Is it simply turnning the number to a negative and not borrowing anything? – Dan Aug 03 '21 at 03:37
  • An output of the ALU, and of the `sub` instruction. In math terms, using the schoolbook notation where you put the borrow above the column to the left, it's a borrow into a column where there are no input bits (i.e. one bit wider than the inputs). Since there's nothing to subtract from, you either just discard it (MIPS or RISC-V) or put it in a FLAG bit (ISAs with flags). – Peter Cordes Aug 03 '21 at 03:40
  • In math terms tho they alway flip the inputs in this case and add a negative sign to the output. They actually never do `0-1` as it doesn't make sense, they do a `1-0` and add a negative sign to the result. – Dan Aug 03 '21 at 03:42
  • Flipping an input is an implementation detail of how ALUs usually use an [adder-subtractor](https://en.wikipedia.org/wiki/Adder%E2%80%93subtractor), rather than just a pure subtractor which is something you can build directly out of logic gates if you want to (https://en.wikipedia.org/wiki/Subtractor). An adder-subtractor can produce equivalent outputs to a subtractor. Also, all of that is implementation detail, not math. I was talking about what it means in terms of schoolbook long-hand subtraction like you'd do on paper. (Which definitely doesn't involve 2's complement!) – Peter Cordes Aug 03 '21 at 03:45
  • Im also referring to school math tho, not ALU design. If you give me say `5-9`, I would always do `9-5` and add a `-` sign to the output, I would never actual do `5-9` as is. – Dan Aug 03 '21 at 03:56
  • Oh, reverse the operands, not flip (the bits) in one of them, yeah. That's how you do sign/magnitude subtraction to avoid ever producing a borrow output. But if you look at a schoolbook representation of what ALUs do, they never reverse the operands, and do binary / 2's complement, not sign-magnitude. – Peter Cordes Aug 03 '21 at 03:59
  • Correct, so the ALUs are implementation defined. When there is a binary `1` on the left side it will be borrowed from. When there's none like in `0b00 - 0b01` the ALU will give you a `1` as it's output and sets a flag, that's where the 1 is coming from, is that close to being correct? – Dan Aug 03 '21 at 04:03
  • 1
    Yup, exactly like a 1-bit Full Subtractor. https://en.wikipedia.org/wiki/Subtractor#Full_subtractor, however it actually works internally. – Peter Cordes Aug 03 '21 at 04:04
  • I never got around to answering this of finding a duplicate after fully understanding what real ALUs do myself. I updated my answer on [Arithmetic identities and EFLAGS](https://stackoverflow.com/a/62219965) to mention that `sub` could be emulated with `not input` / `stc` (set CF) / `adc dst, inverted_src` / cmc but didn't finish an example. [What CPU architecture was first to implement 'inverted borrow' carry flag during subtractions?](https://retrocomputing.stackexchange.com/q/21861) also mentions what inputs to a full-adder you use, and talks about the borrow output being inverted or not. – Peter Cordes Apr 05 '22 at 04:35
  • And [How does the CPU do subtraction?](https://stackoverflow.com/a/56279548) is a possible duplicate (especially that linked answer.) – Peter Cordes Apr 05 '22 at 04:37

0 Answers0