, 4 min read
Unsigned vs. signed integer arithmetic
Given any non-negative integers x and d, we can write uniquely x = q d + r where q (the quotient) and r (the remainder) are non-negative and r is less than d. We write r = x mod d.
Most modern processors represent signed and unsigned integers in the following manner:
- Unsigned integers as simply 32-bit or 64-bit binary numbers. E.g., we write the number 15 as 0b0...01111. Programmers write bits from right to left, starting with the least significant bits: the right-most bit has value 1, the second right-most bit has value 2, and so forth.
We have to worry about overflows: e.g., when adding two 32-bit integers that won’t fit in 32 bits. What happens if there is an overflow? How your programming language handles it is one thing, but processors often make it easy to compute the operations “modulo the word size”. This means that x + y is the same as (x + y) mod 2w where w is the word size in bits (typically 32 or 64).
Dividing by two can be achieved by “right-shifting” the bits by 1. Multiplying by two is equivalent to “left-shifting” the bits by 1.
- Signed integers are implemented at the processor level in a manner similar to unsigned integers, using something called Two’s complement. We can think about Two’s complement as a way of mapping signed values to unsigned (binary) values. Positive values (in [0,2w-1)) are mapped to themselves (m(x)= x) whereas negative values (in [-2w-1, -1]) are mapped to the complement (m(x)= 2w–x).
You can distinguish negative integers from positive integers since their left-most bit is set to true. That’s convenient.
Programmers prefer to say that we can negate a number by flipping all its bits (sometimes called “one’s complement”) and adding the value one. You can verify that if you take a number, flip all its bits and add the original number, you get a binary value with all the bits set to 1, or 2w-1. So the result follows by inspection but I prefer my formulation (m(x)= 2w–x) as it makes the mathematics clearer.
A fun problem with Two’s complement is that you have more negative numbers than you have positive (non-zero) numbers. This means that taking the absolute number of a signed integer is a bit tricky and may lead to an overflow. Thus we cannot do something like a/b = sign(b) * a / abs(b) or a * b = sign(a) * sign(b) * abs(a) * abs(b) since there is no safe absolute-value function.
The nice thing with Two’s complement is that because the processor implements unsigned integer arithmetic modulo a power of two (e.g., (x + y) mod 2w ), then you “almost” get the signed arithmetic for free. Indeed, suppose that I want to add two values x and y but that one of them (y) is negative. Then I first apply my map to transform them into unsigned values (y becomes 2w-y), and I end up with x + 2w-y mod 2w which is just x - y mod 2w as one would expect.
So we get that multiplications (including right shifts), additions, and subtractions are nearly identical operations whether you have signed or unsigned integers.
This means that a language like Java can avoid unsigned integers for the most part. Signed and unsigned integers more or less work the same.
When you program in assembly, it is not quite true. For example, on x86 processors, the MUL (unsigned multiplication) and IMUL (signed multiplication) instructions are quite different. However, as long as you only care for the multiplication modulo the word size, you can probably use them interchangeably: a critical difference is that the unsigned multiplication actually compute the full result of the multiplication, using another word-sized register to store the more significant bits. Other processors (e.g., ARM) work slightly differently, of course, but the need to distinguish between signed and unsigned integers still arise from time to time.
The division, remainder and right shifts are something else entirely.
Let us divide by two. The value -2 is mapped to 0b111...10. With unsigned arithmetic, we would simply shift all bits right by one, to get 0b0111...1, but that’s no longer a negative value in Two’s complement notation! So when we shift right signed integers, we typically replicate the left-most bit, so that we go from 0b111...10 to 0b111...11.
This works well as long as we only have negative even numbers, but let us consider a negative odd number like -1. Then doing the signed right shift trick, we go from 0b111...11 to 0b111...11, that is (-1>>1) is -1. It is not entirely unreasonable to define -1/2 as -1. That’s called “rounding toward -infinity”. However, in practice people seem to prefer to round toward zero so that -1/2 is 0. The net result is that whereas division by two of unsigned integers is implemented as a single shift, the division by two of signed integers ends up taking up a handful of instructions.