Why is the Carry Flag set during a subtraction when zero is the minuend?

Question

At the moment I write my own little library for arithmetic and logical operations for very big unsigned integers. To improve performance I decided to implement some functions in assembly. So here is my question. While subtracting two unsigned integers the Carry Flag is set when I subtract any number from 0.

But why is the Carry Flag set in this situation? The Carry Flag is only set when an overflow occurs, but if I subtract any number from zero I don't get an overflow. Or I am wrong?

Overburden

Note: writing your own operations in assembly may not provide the optimization you anticipate. The compiler does not check the inline assembly and has no way of optimizing them. You may find the compiler will do a better job optimizing if you simply provide logical C code. – Unfleshly

Thanks for your advice. But I don't do inline assembler. I write separate parts in assembly and I link this object files with the C-code. – Overburden

Then there is even less chance there can be any optimization of the assembler routines within the overall structure of your code. Don't get me wrong, I'm not knocking trying to gain speed using assembler, I used to think it would always be faster too, but always compare the performance of your code with linked assembly to the performance of the code written in straight C with full compiler optimizations (-O3 on most -Ofast for gcc version >= 4.6.0). Compilers are quite good at optimizing today and 9/10 times the straight C will be faster. – Unfleshly

OK, thanks I will keep that in mind. The biggest problem I have, is the fact that there is no simple way in C to check the status of the carry flag and use it in further operations. So at the moment I use the Most Significant bit of the unsigned integer type as the carry flag. But I am not really satisfied with that. That is why I want to implement the core logic of subtracting and adding in assembler. But maybe someone has a better idea to do that. I am always open to other suggestions. – Overburden

Answer 1

Carry flag is carry or borrow out of the Most Significant bit (MSb):

CF (bit 0) Carry flag — Set if an arithmetic operation generates a carry or a borrow out of the mostsignificant bit of the result; cleared otherwise. This flag indicates an overflow condition for unsigned-integer arithmetic. It is also used in multiple-precision arithmetic.

Don't associate the CF with the sign bit, in a subtraction CF is set whenever the minuend, treated as unsigned, is less than the subtrahend, treated as unsigned.
This is equivalent to an overflow condition, for signed numbers the equivalent flag is OF.

For an (unnecessary?) visual clue, in this 4-5 operation, it is the second borrow, the red one, that set the CF

Not if you subtract from zero, it comes naturally that for any number, but zero itself, you'll always have the CF set, as the subtrahend has at least one bit set.

---

Finally, some instructions let you change the sign bit without affecting the CF (see for example the logic operations or the behavior of neg).

Jiujitsu

Thanks for your detailed answer. My problem was the fact that I didn't know anything about borrowing. I thought that the flags at subtracting are set in the same way as at adding the two's complement. But now I recognized that this is wrong. At the x86 arch the carry flag is set the other way around. (sub) 4-5 = CF(1). (add) 4+(-5) = CF(0). – Overburden

@idlmn89: Don't look at the carry flag for signed numbers; the overflow flag tells you whether they wrap around. This is normal for the carry flag on all architectures, AFAIK, not just x86. See also this very good carry vs. overflow tutorial. In extended-precision data, only the most-significant word contains the sign bit. The other words are all effectively unsigned, so you add/sub them with carry/borrow-in and carry/borrow-out. But the MSB only has a carry-in, and no carry/borrow out. – Lacerta

"Finally, some instructions let you change the sign bit without affecting the CF (see for example the logic operations or the behavior of neg)." neg does effect the carry flag though. – Playful

Answer 2

We know from grade school that a - b = a + (-b). And that is how logic does it we dont subtract we add the negative. We also know from beginner programming classes that with twos complement to get the negative you invert and add one. a - b = a + (~b) + 1. We also know from grade school the concept of carrying. 9+3 = 2 carry the one. Same in binary, with two operands you can have 1 + 1 = 0 carry the one. So each column in logic needs a carry. Each are three bits in two bits out, the two operands in plus carry in and carry out and the result out. Since each of these logic blobs has an input bit, carry in, normal addition that first carry in is a zero, but for subtraction we can make that carry in a 1 and invert the second operand to get a + b = a + (~b) + 1

So subtraction is addition, if you work through a few simple examples, or better try every three bit combination of operands yourself. You will see that there is no such thing as signed nor unsigned addition (or subtraction), the beauty of twos complement encoding.

Knowing all of this, subtraction is addition, with addition we get a carry out on UNSIGNED overflow, the signed overflow bit is when the carry in and the carry out of the msbit dont match, usually represented as the V flag. Now some architectures, since they are already inverting the b operand on the way in and the carry in on the way in, they invert the carry out on the way out. SOME DONT. So you have to look at your particular architecture to understand if the carry out is considered an unsigned addition overflow or if it is a borrow. or not borrow or whatever.

zero minus something is not always going to have a carry out for the addition.

0b000 - 0b111

 0001
  000
+ 000
=====
  001

The carry out of the addition is zero. Your architecture may choose to leave it that way or it may choose to invert it and call it a borrow.

Within an architecture family. All of the x86s or all of the ARMs it is likely they will continue to do it the same way forever. But there is no reason to expect ARM and MIPS and x86 and XYZ to all do it the same way.

Inverting it and defining it as a borrow makes sense from a terminology perspective.

Note that all of the (signed/unsigned) greater than, less than, greater than or equal, less than or equal definitions are based on the carry/borrow choice for that architecture, you cannot translate those flag comparisions across architectures unless they have the same definition.

Wimsatt

Have you forget the +x1 after ~ operation ? – Serrulation