Negative numbers, in bits
MIPS stores a negative number in
.
The rule: to get −x, flip every bit of x and add one. So −1 is all ones,
0xFFFFFFFF. Bit 31 is the sign bit: 1 means negative.
The same 32 bits, read two ways
Why is 0xFFFFFFFF both −1 and 4294967295?
decimal, read as a plain count: 4294967295 · read as a signed number: -1
- the four bits of the hovered hex digit
Click any input bit to flip it.
What to notice
The bits do not know whether they are signed. The figure shows both readings. Which one is “right” depends on the instruction that uses them, and on you. Flip bit 31 off and the two readings become equal.
The good news: one adder serves both readings. Adding the bits of 5 and the bits of −8 gives the bits of −3, with no special case for the sign.
Adding, one bit at a time
Press play. One tick is one bit position, from bit 0 up to bit 31. The lime cells are carries arriving from the bit below.
5 + (−8), bit by bit
Where does the carry chain start, and where does it stop?
5 (signed) · 0x00000005
-8 (signed) · 0xfffffff8 · 4294967288 if read unsigned
- a carry of 1 arriving at this bit
- a finished result bit
- bit 31 when signed overflow happened
- not computed yet
What to notice
Bits 3 and above are all carries: 1 + 1 + carry gives 1 and carries again, all the way to the top. The carry out of bit 31 is thrown away, and the 32 bits that remain read as −3. That is correct, and no overflow happened.
Now the case that does not fit. 0x7FFFFFFF is the largest positive number.
Add one.
0x7FFFFFFF + 1: the answer does not fit
Two positive numbers, a negative result. How does the hardware notice?
2147483647 (signed) · 0x7fffffff
1 (signed) · 0x00000001
- a carry of 1 arriving at this bit
- a finished result bit
- bit 31 when signed overflow happened
- not computed yet
What to notice
The carry runs all the way into bit 31 and flips it to 1. The 32 bits now read as −2147483648. The true answer, +2147483648, needs 33 bits. That is , and the test is: the carry into bit 31 differs from the carry out.
Two instructions, one difference
add rd,rs,rt and addu rd,rs,rt both compute rs + rt and keep the low 32
bits. They differ only when signed overflow happens:
| instruction | on overflow | GCC uses it |
|---|---|---|
add, addi, sub | trap: the program stops | never |
addu, addiu, subu | wrap: keep the 32 bits, go on | always |
A is an exception: the CPU stops the program and hands control to the operating system. Your test machine has no operating system, so the run just halts. To is to keep the 32 bits and forget the carry, like an odometer rolling over.
Watch both on the same sum. The runner pauses before the add to ask you.
addu wraps, add traps: the same bits, a different rule
What happens when 0x7FFFFFFF + 1 does not fit in a signed 32-bit register?
program (address · word · instruction)
| PC → | 0xbfc00000 | 0x3c087fff | _start:lui $t0,0x7fff |
| 0xbfc00004 | 0x3508ffff | ori $t0,$t0,0xffff | |
| 0xbfc00008 | 0x24090001 | li $t1,1 | |
| 0xbfc0000c | 0x3c191000 | lui $t9,0x1000 | |
| 0xbfc00010 | 0x37390ff0 | ori $t9,$t9,0xff0 | |
| 0xbfc00014 | 0x01095021 | addu $t2,$t0,$t1 | |
| 0xbfc00018 | 0xaf2a0004 | sw $t2,4($t9) | |
| 0xbfc0001c | 0x01095820 | add $t3,$t0,$t1 | |
| 0xbfc00020 | 0xaf2b0004 | sw $t3,4($t9) |
registers — read · written this tick
console (what the doors printed)
▮tick 0 of 8
Nothing has run yet. The PC (program counter) points at the first instruction.
Tick 6 (addu) writes 0x80000000 and the program goes on; the number door prints it as −2147483648. Tick 8 (add) computes the same bits, but the machine stops: overflow trap. The store after it never runs.
What to notice
Tick 6 and tick 8 do the same arithmetic. Tick 6 (addu) writes
0x80000000 and the console prints it as −2147483648. Tick 8 (add) writes
nothing: the machine stops, and the store after it never runs.
Before reading on, decide:
C's int arithmetic is expected to wrap. Which add does GCC emit for `x + y`?
The u does not mean unsigned
This is the trap in the name. addu adds signed numbers just as well as
unsigned ones. The bits are identical. The u means “unchecked”: no trap on
overflow. Count the instructions in the fourteen reference dumps:
| mnemonic | count | mnemonic | count |
|---|---|---|---|
addu | 22 | add | 0 |
addiu | 215 | addi | 0 |
subu | 2 | sub | 0 |
Every add in every compiled program is the unchecked form. Carolyne’s MIPS
description marks add, addi and sub as non-trapping for now. That LIMIT
never shows in a compiled program, because GCC never asks for them.
Subtracting, and subtracting a constant
sub and subu follow the same pattern. Subtracting is adding the two’s
complement: a − b = a + (~b + 1). The adder does it with one extra carry
in.
5 − 8 = 5 + (~8 + 1)
Why is subtraction just another add?
5 (signed) · 0x00000005
-9 (signed) · 0xfffffff7 · 4294967287 if read unsigned
- a carry of 1 arriving at this bit
- a finished result bit
- bit 31 when signed overflow happened
- not computed yet
What to notice
The second row is b with every bit flipped. The extra +1 arrives as the
carry into bit 0. The result reads −3. The overflow test is the same.
There is no sub with an immediate. To subtract a constant, add a negative
one with addiu. That is what GCC does at the start of every function:
addiu sp,sp,-32 from hello.c at -O0 (0x27BDFFE0 at 0xBFC0018C)
Where is the −32, and why does it work as a subtraction?
What to notice
The 16-bit field holds 0xFFE0, which is −32 when sign-extended. Adding −32
to $sp moves the stack pointer down by 32 bytes. Section 3.2 explains the
sign extension; §4.4 explains why the stack grows downward.
Two more names you will see: neg and negu. They are
:
negu rd,rs is subu rd,$zero,rs, that is 0 − rs. The CPU never sees the
word negu.
Go deeper: why a trapping add exists at all, and what Carolyne does with it
MIPS was designed in 1985 to run several languages. Some, such as Ada and Pascal, require an error when integer arithmetic overflows. Giving them a checked add in hardware costs nothing: the adder already has the carry into bit 31 and the carry out, and comparing the two is one gate. So MIPS offered both forms and let each compiler choose. C chose the unchecked one, and C won, which is why the checked forms are museum pieces in a modern dump.
Carolyne’s MIPS description has no trap policy yet (the same gap that keeps
RISC-V’s ecall out). Its add, addi and sub therefore wrap like the
u forms, and the description records this as a LIMIT. Because GCC never
emits them, all 34 census builds run correctly anyway. The browser simulator
under the runner above does implement the trap, so you can see the difference.
Can you now explain it?
One adder, two readings. add and addu produce the same bits; add traps when the signed result does not fit, addu wraps. C wants wrapping, so compiled MIPS is addu, addiu and subu all the way down.
If you remember only three things
- Negative is a reading, not a bit pattern. 0xFFFFFFFF is −1 or 4294967295 depending on who looks. The adder does not care.
- Overflow is a 33rd-bit problem. The carry into bit 31 differs from the carry out. add stops the program there; addu keeps the low 32 bits.
- u means unchecked. Not unsigned. GCC emits the u forms for every int, and subtracts constants with addiu and a negative.
Now try to explain this one yourself: 0xFFFFFFFF + 1 carries out of bit
31 and gives 0x00000000. Under add, does this trap? Use the overflow test.
Go deeper: a model answer, once you have tried
No. Read signed, the sum is −1 + 1 = 0, which fits. The overflow test agrees.
Bit 31 of −1 is 1, bit 31 of 1 is 0, and the carry arriving from bit 30 is 1.
So 1 + 0 + 1 gives sum bit 0 and carry out 1. Carry in 1, carry out 1: equal,
so no signed overflow. A carry out alone is the unsigned overflow test, and
MIPS never traps on that. add writes 0 and continues.
Check your understanding
0/5 answered1.In C, `i = i + 1;` with `int i`. Which instruction does GCC emit?
2.$t0 holds 0x7FFFFFFF. What does `addiu $t1,$t0,1` put in $t1?
3.Is `sub $t0,$t0,4` a legal MIPS instruction?
4.What does the `u` in `addu` mean?
5.How does the hardware know that an add overflowed?