0
$\begingroup$

TL;DR. Question in a very short fashion could be:

In subtraction of two binary numbers, minuend smaller than subtrahend and using just (school) borrowing method (not two's complement, etc), how do you reason with the borrowing to get to the two's complement used as the benchmark?
Canonical example: 0000 [minuend: no one/s to hold on to] - 0001 [subtrahend]
By two's complement method we know that:
0000 + (-0001) == 0000 + (~0001) + 1 == 1111
Doing a classical subtraction with borrowing, how do we get there?
(pure [raw subtraction with borrowing]: a - b; not [2' complement]: a + (-b))
(All the rest, like the mentions to Intel and ARM are for if the Carry Flag can help or what rol plays, if any, in the problem that to the left, we don't have any 1s to borrow from, at least in one architecture, perhaps, yes, but the other one, the meaning of the carry is the opposite).

Details or clarity on question:

  • I am studying CPU flags raised in arithmetic comparison (signed and unsigned).
  • When overflow happens (wraparound), in a unsigned subtraction: the Carry (CF. Carry flag) in Intel, CF is set to 1 ("Borrow Flag", implicit, does not exist, "is set" (imaginary) to the complementary, 0). In ARM, CF is set to 0 ("Borrow Flag", implicit, does not exist, "is set" (imaginary) to the complementary, 1).
  • Obviously, this happens in the concrete number space boundaries, which establishes the condition for an overflow, e.g. If there were, for simplification, only 4 bits (we all work with 64 or 32). Size of that space is: 2^4 == 16 possibilities. See example on the body of this OP below.
  • The question is: how is the reasoning, pure logical or conventional (artificial rules, for example: "you actually have a 1 on the left that you can borrow from, so your assumption that 'left to the subtrahend one are only zeros', decays, is not true"), in terms of traditional borrowing? (Avoiding the natural alternative using two's complement: a - b == a + (-b) [in other words: circumventing the subtraction through borrowing, transforming it in a addition using the inverse of the subtrahend. This is what I would like to avoid. I want to know how will go with borrowing].
  • If the answer is: hey! (Implicit) Carry flag serves you as the 1 on the left you were missing to make the subtraction and solve the 0 - 1 conundrum! But...
  • ...if that's the case, why for example Intel actually uses for this subtraction overflow a CF == 1, what implies an imaginary "Borrow flag" == 0 ["no borrow"]. While ARM is the opposite: CF == 0, what implies an imaginary "Borrow flag" == 1 ["yes, borrow happened"]. In this precise case one cannot say that "you have the 1 from the CF", because is actually 0
  • Carry flag (Wikipedia. Literal): "For subtractive operations, two (opposite) conventions are employed as most machines set the carry flag on borrow while some machines (such as the 6502 and the PIC) instead reset the carry flag on borrow (and vice versa)." https://en.wikipedia.org/wiki/Carry_flag

Original question statement:
In computing, CPU Processor flags react to certain phenomena related with arithmetic operations related as well with the resources of certain machine to represent mathematical operations. When this operations exceed limits, in the best cases, machine could raise a flag to warn about whatever violation of assumptions and divergence from truth.
In order to understand the borrow/not-borrow//carry/not-carry logic of some architectures (like ARM or Intel), how do you reason using the following borrowing logic?

Borrowing logic (binary): when minuend is smaller than subtrahend, you borrow the base unit from the left [obtaining "a 2": 10b binary == 2d decimal, perfect for your column on the right where you were having the 0-1 problem: now you can do "10b(2d)-1b(1d) == 1"], then you subtract that borrowing from that 1 at the left (the "borrower"), what yields a 0.
You were are able yo do de subtraction as shown. Or if there was no near 1, you could have "unfolded"/propagated the base from any other 1 on the left at distance if possible.

My question is:
But what happens when you only have 0's all the way to the left.

Canonical case: 0 - 1 ("zero minus one")
Imagine: 4 bit subtraction: 0000 - 0001
Has yo yield: -1
One knows from two's complement, that should be: 0000 + (~0001) + 1 == 1111

How do you get there using the borrowing ("school") reasoning when you don't have any 1's to the left, just infinite zeros?
Needs some convention thinking? Like "you have the 1, the carry by convention", "by convention...".
But if the machine, as happens between ARM and Intel, sets CF flag (Carry Flag) in an exactly opposite way (and "carry is the opposite to borrow"), how can this be understood?

I reached related post on topic: Binary subtraction A0 - E4
And help from here (more in the comments): How is this binary subtraction done?
Also here (that is where I started looking):
https://stackoverflow.com/questions/31769464/how-to-subtract-binary-when-there-is-no-where-to-borrow-from

asked Oct 24 at 12:22
$\endgroup$
8
  • $\begingroup$ In fact you can't use traditional borrowing to subtract a positive number from a smaller non-negative number. Computer arithmetic does not follow logically from traditional borrowing. The choice of which flags to set for which conditions is not logically determined. If you want to know what a processor does for subtraction, read the specification. The important thing is that people can easily implement multiple-word integers, not that the implementation has to be exactly the same for every machine. $\endgroup$ Commented Oct 25 at 7:49
  • 1
    $\begingroup$ So I think the simple answer to your question is, "No, because what happens inside the computer is more than the mathematical idea of borrowing." Perhaps I misunderstood the question, which is a bit rambling. $\endgroup$ Commented Oct 25 at 7:51
  • $\begingroup$ @DavidK I feel you are in the very right path (the pure mathematical meaning of a borrow vs the representational capabilities of a certain machine/specification), but my feeling wasn't enough, I was needing a person very fluent in math with eagle view to simplify the thing, "ok, let's remove the leafs, what is really happening here is...". This said and demanding just an approximation, a clue for me to continue digging, how would you reason out loud the relation between the explicit-carry/implicit-borrow when subtracting unsigned numbers in, for simplification, a universe of 4 bits? $\endgroup$ Commented Oct 25 at 8:02
  • $\begingroup$ @DavidK Because the concept of borrow (in CPUs/computing arithmetic context) is not something that I decided to think to apply to this. Is mentioned all over the place relating it to the concept of carry. For example: Carry flag (Wikipedia. Literal): "For subtractive operations, two (opposite) conventions are employed as most machines set the carry flag on borrow while some machines (such as the 6502 and the PIC) instead reset the carry flag on borrow (and vice versa)." en.wikipedia.org/wiki/Carry_flag $\endgroup$ Commented Oct 25 at 8:05
  • 1
    $\begingroup$ When I was working with machine code I don't recall having any confusion about the meaning of the carry/borrow bit. I read the specifications of the processor, which told me what it meant. Admittedly, reading a specification is a skill that takes learning. It can be a lot to digest. And indeed, learning any new thing can involve letting go of preconceptions that one brings from previous experiences. $\endgroup$ Commented Oct 25 at 22:55

0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.