Binary arithmetic: flags, carries, and wide numbers
prerequisite
A register holds a fixed number of bits: 32 in a w register, 64 in an x register. Every add and subtract has to fit its answer into those bits, and sometimes the true answer does not fit. The processor never stops to complain. It keeps the bits that fit and records four facts about the result in the condition flags, four single bits named N, Z, C and V that the conditional branches read.
This lesson covers what each flag means, which branches read which flags, and how the carry flag lets a program add numbers too wide for any one register.
Adding in binary
Binary addition works column by column from the right, the same as decimal addition, except that a column is full at 2 instead of 10. 1 + 1 is 10 in binary: write 0 and carry 1 into the next column. Here is 109 + 167 worked in 8 bits:
0110 1101 109 + 1010 0111 + 167 ----------- ----- 1 0001 0100 276The answer needs 9 bits, and an 8-bit register has room for 8. The extra 1 on the left, the carry out, is dropped, and the register keeps 0001 0100, which is 20. That is 276 - 256: the count went past the largest 8-bit value, 255, and started again from 0, the way a car's odometer rolls from 99999 to 00000. Keeping only the low n bits of every answer is called arithmetic modulo 2^n. A w register works modulo 2^32 and an x register modulo 2^64.
Subtraction is addition
The processor has no separate circuit for subtracting. To work out a - b it adds a to the negation of b, and the negation of b in two's complement is b with every bit flipped, plus 1. Here is 5 - 7 in 8 bits:
7 0000 0111 flip the bits 1111 1000 add 1 1111 1001 this is -7 0000 0101 5 + 1111 1001 -7 ----------- 1111 1110 -2 read as signed, 254 read as unsignedNo carry comes out of the top bit here, and that is how the processor knows a borrow was needed: 5 is smaller than 7, so the subtraction had to take from a column that is not there. Work out 7 - 5 the same way and a carry does come out of the top bit, because no borrow was needed. So after a subtraction, a carry of 1 means "no borrow" and a carry of 0 means "borrow".
The four flags
| flag | name | set to 1 when |
|---|---|---|
| N | negative | the top bit of the result is 1, so the result reads as negative when treated as signed |
| Z | zero | every bit of the result is 0 |
| C | carry | an add carried a 1 out of the top bit, or a subtract needed no borrow |
| V | overflow | the signed answer does not fit, so the result has the wrong sign; for an add, two values with the same sign gave a result with the other sign |
Among the arithmetic and logic instructions, only the ones that end in s write the flags: adds, subs, ands, negs, adcs and sbcs. cmp a, b is a subs that throws its result away and keeps only the flags, cmn a, b does the same with adds, and tst a, b does the same with ands. A plain add or sub leaves the flags exactly as they were.
note
C and V ask different questions about the same bits. C asks whether the answer fits when every value is read as unsigned, 0 to 2^32 - 1 for a w register. V asks whether it fits when every value is read as signed, -2^31 to 2^31 - 1. One operation can set either flag, both, or neither.
Watching the flags change
The program below does four 32-bit operations picked to sit at the edges of the register, and prints each result in hex beside its four flags. It reads the flags with cset, which writes 1 to a register when a condition holds and 0 when it does not. cset w3, mi gives 1 when N is set (mi is short for minus), eq checks Z, cs checks C, and vs checks V. It prints:
operation result N Z C V0x7fffffff + 1 0x80000000 1 0 0 10xffffffff + 1 0x00000000 0 1 1 05 - 5 0x00000000 0 1 1 03 - 7 0xfffffffc 1 0 0 0Row by row:
0x7fffffff + 1: two positive values gave0x80000000, whose top bit is 1. Read as signed, that is the most negativeint, so the true answer did not fit: V = 1 and N = 1. No carry came out of bit 31, so C = 0.0xffffffff + 1: every column carries, the carry falls off the top, and the result is 0, so Z = 1 and C = 1. Read as signed this is -1 + 1 = 0, which fits, so V = 0.5 - 5: the result is 0, so Z = 1, and no borrow was needed, so C = 1.3 - 7: the result is0xfffffffc, which is -4, so N = 1. A borrow was needed, so C = 0, and -4 fits, so V = 0.
Change one operand, predict all four flags, then run it to check.
warning
The ldr and cset lines between adds and bl printf never touch the flags, so all four cset lines read the same result. A call is different: printf, like any function, is free to change the flags, so read them before the call, never after.
Signed and unsigned conditions
cmp a, b works out a - b and sets all four flags. It does not know whether you mean the bits as signed or unsigned, and it does not need to: the branch that follows makes that choice. The bit pattern 0xffffffff is 4294967295 read as unsigned and -1 read as signed. Signed conditions read N and V, unsigned conditions read C and Z:
| to branch when | signed | unsigned |
|---|---|---|
| a < b | b.lt (less than) | b.lo (lower) |
| a <= b | b.le (less or equal) | b.ls (lower or same) |
| a > b | b.gt (greater than) | b.hi (higher) |
| a >= b | b.ge (greater or equal) | b.hs (higher or same) |
b.eq and b.ne read Z alone, so they work for both kinds. b.hs and b.lo have second names, b.cs (carry set) and b.cc (carry clear), because after a compare they test C and nothing else.
The program below compares -1 with 1 twice, once with b.lt and once with b.lo. It prints:
signed: -1 is less than 1unsigned: 4294967295 is not lower than 1Same compare, same flags, opposite answers. Pick the condition that matches what the number means: a count, a size or an address is unsigned, and a value that can drop below zero is signed.
note
a_r and b_r live in w19 and w20 because printf may change x0 to x18 and the flags. main uses them without saving them first, as course programs do. A subroutine you write must save any of x19 to x28 it changes and put them back before it returns.
Numbers wider than a register
A 128-bit number fits in two x registers: a high half and a low half. Adding two of them is column addition again, with columns 64 bits wide. First add the low halves with adds, which leaves the carry out of bit 63 in C. Then add the high halves with adc (add with carry), which adds C in as one extra 1.
Subtraction has the same pair: subs on the low halves, then sbc (subtract with carry) on the high halves, which takes away one more when the low halves needed a borrow. For numbers longer than two registers, each middle step uses adcs or sbcs, which take the carry in and also set a new one for the next step.
The program below adds two 128-bit numbers and prints them laid out like a sum on paper, high half first:
0000000000000001 ffffffffffffffff+ 0000000000000002 0000000000000003= 0000000000000004 0000000000000002The low halves, 0xffffffffffffffff + 3, give 2 with a carry out, and adc turns the high halves' 1 + 2 into 4. Change adc to add and run it again: the high half reads 3, so the sum is short by exactly 2^64.
Multiplying with shifts and adds
Long multiplication is simpler in binary than in decimal because each digit of the multiplier (the number you multiply by) is 0 or 1. A 0 digit adds nothing. A 1 digit at bit position k adds the multiplicand (the number being multiplied) shifted left k places, which is the multiplicand times 2^k. 11 is 1011 in binary, so 13 x 11 works out like this:
1101 13 x 1011 11 ------ 1101 bit 0 is 1: add 13 1101 bit 1 is 1: add 13 shifted left 1 = 26 0000 bit 2 is 0: add nothing 1101 bit 3 is 1: add 13 shifted left 3 = 104 -------- 10001111 143The program below does the same steps. tst checks the lowest bit of the multiplier, lsl moves the multiplicand one place left, and lsr brings the next multiplier bit down to bit 0. The loop stops once no 1 bits are left. It prints:
bit 0 is 1, product = 13bit 1 is 1, product = 39bit 2 is 0, product = 39bit 3 is 1, product = 14313 x 11 = 143mul does this work in hardware in one instruction. The shift-and-add view still explains two things you will meet. First, the product of two n-bit numbers can need 2n bits, so a 32-bit product that might be large is worked out in x registers after widening both inputs with sxtw. Second, multiplying by a power of two is a single lsl. Division runs the same idea backward, as binary long division that subtracts the divisor wherever it fits; sdiv and udiv do it in hardware.
pitfall
A common mistake from this lesson, with a broken program and its fix that you can run:
Check yourself
w1andw2both hold0x80000000. Afteradds w0, w1, w2, what are N, Z, C and V?w0holds0xfffffffeandw1holds 2. Aftercmp w0, w1, isb.gttaken? Isb.hitaken?- Which instruction adds the high halves of two 128-bit numbers, and what does it add besides them?
answers
show answers
- The result is 0, so N = 0 and Z = 1. A carry came out of bit 31, so C = 1. Two negative values gave a result that is not negative, so V = 1.
- Read as signed,
0xfffffffeis -2, which is not greater than 2, sob.gtis not taken. Read as unsigned, it is 4294967294, which is higher than 2, sob.hiis taken. adc. It also adds the C flag, the carry left over from adding the low halves withadds.
Practice
- The overflow detective: read V and C after a 32-bit
addsand say which way the add went wrong. - Fibonacci past the horizon: 128-bit numbers kept in two registers and added with
addsandadc. - Basic quiz: binary arithmetic, then core and challenge: wraparound, subtraction by negation, carries, and the flags.
- Fill in the blank: binary arithmetic (core): pick the mnemonic or unsigned condition each line needs,
addsandadcincluded. - Predict: binary arithmetic (challenge): trace wraparound and a carry passed from one add to the next.