Two's complement: how negative integers actually work¶

Every modern CPU represents signed integers in two's complement. Once you understand it, a long list of "weird" behaviors stops being weird: why -1 prints as 0xFFFFFFFF, why INT_MIN cannot be negated, why a signed overflow wraps to a negative number, why right-shifting -1 does not give you zero, why C compilers exploit signed-overflow-is-undefined-behavior for optimization. They are all the same idea seen from different angles.

This page is the idea, the consequences, and the production gotchas. It assumes you have read Bit operations - the operators show up immediately.

1. Why we need a representation for negative numbers¶

A computer's memory holds bytes, and a byte holds 8 bits, each of which is 0 or 1. There is no minus sign anywhere. If you want to represent -3, you have to assign meaning to some pattern of bits.

You could imagine three approaches:

Sign-and-magnitude. Use the top bit as a sign (0 = positive, 1 = negative) and the remaining bits as the magnitude. So 8-bit +3 is 0000_0011 and -3 is 1000_0011. Problem: there are now two zeros (+0 = 0000_0000 and -0 = 1000_0000), and addition needs a separate "what if signs differ" code path. CPUs hate special cases.
One's complement. A negative number is the bitwise NOT of the corresponding positive number. So +3 is 0000_0011 and -3 is 1111_1100. Cleaner, but still has two zeros (+0 = 0000_0000 and -0 = 1111_1111), and addition still needs an "end-around carry" adjustment.
Two's complement. A negative number is the bitwise NOT of the corresponding positive number, plus one. So +3 is 0000_0011 and -3 is 1111_1101. Only one zero, and ordinary unsigned binary addition just works without any signed-aware code path. This is what every CPU since roughly 1970 uses, and it is what every modern programming language compiles down to.

The "plus one" looks like a kludge. It is what makes the whole system clean.

2. What two's complement actually means¶

For an N-bit integer in two's complement, the leftmost bit (bit N-1) is the sign bit. But it does not just say "negative." It contributes a value of -(2^(N-1)) to the total, while every other bit k contributes +2^k exactly as in unsigned binary.

For an 8-bit signed integer:

  bit:   7        6      5      4      3      2      1      0
  value: -128    +64    +32    +16    +8     +4     +2     +1

So the bit pattern 1111_1101 means:

  -128 + 64 + 32 + 16 + 8 + 4 + 1
= -128 + 125
= -3

That is the entire definition. Every "weird" two's complement behavior follows from this one rule: bit N-1 contributes -2^(N-1); every other bit contributes its positive power of two.

A quick sanity table for 4-bit two's complement (range: -8 to +7):

Bits	As unsigned	As signed (two's complement)
`0000`	0	0
`0001`	1	+1
`0111`	7	+7
`1000`	8	-8
`1001`	9	-7
`1110`	14	-2
`1111`	15	-1

Notice: an N-bit signed integer can hold values from -2^(N-1) to +2^(N-1) - 1. The range is not symmetric. There is one more negative number than positive. We will see why this matters in §6.

3. The "negate a number" recipe¶

To negate a two's complement integer:

Flip every bit (bitwise NOT).
Add 1.

package main

import "fmt"

func main() {
    var x int8 = 5            // 0000_0101
    neg := ^x + 1             // flip bits, add 1
    fmt.Printf("%08b -> %08b = %d\n", uint8(x), uint8(neg), neg)
    // 00000101 -> 11111011 = -5
}

Why this works: flipping every bit of x gives you -x - 1 (every position's contribution flips sign, and the sign-bit contribution shifts by -2^(N-1), with the algebra netting out to that). Adding 1 gives -x. The recipe is a clean two-step.

This is exactly the recipe a CPU uses for the unary - instruction. There is no special "negate" hardware; there is a NOT followed by an ADD-with-carry-in.

4. Why `-1` is "all ones"¶

Apply the recipe to +1:

+1 is 0000_0001.
Flip all bits: 1111_1110.
Add 1: 1111_1111.

So -1 is every bit set. This is why you see 0xFF, 0xFFFF, 0xFFFFFFFF, 0xFFFFFFFFFFFFFFFF in debug output and immediately recognize "that is -1 cast to unsigned." It is also why bitmask code often writes ^uint32(0) to get "all bits set" - that is the two's complement of zero, which is itself, but viewed as the maximum unsigned value.

fmt.Printf("%x\n", int8(-1))       // ff   ... 8 bits, all set
fmt.Printf("%x\n", int32(-1))      // ffffffff
fmt.Printf("%v\n", uint32(0) - 1)  // 4294967295  (which is 0xFFFFFFFF)

Subtracting 1 from unsigned 0 wraps to "all bits set" because of two's complement arithmetic - the underlying hardware does not distinguish signed and unsigned, only the printf format does.

5. Why ordinary addition just works for both signs¶

The whole reason CPUs adopted two's complement: signed addition is the same instruction as unsigned addition. You add the bits, throw away the carry that falls off the top, and the result is the correct two's complement value.

Try 5 + (-3) in 8-bit two's complement:

   0000_0101    (+5)
 + 1111_1101    (-3)
 -----------
 1_0000_0010    (the leading 1 is the carry, discarded)
   0000_0010    (+2)

Throw away the carry, the answer is +2. The CPU's ADD instruction does not care that one operand was "logically negative" - the bit pattern handles itself. This is also true for subtraction (a - b is computed as a + (-b) and -b is one-step-recipe above) and multiplication of small magnitudes.

The only operations that do need a "signed vs unsigned" version: comparison (because "is 1111_1111 bigger than 0000_0001?" depends on whether you think it is -1 or 255), division, and right-shift. We will see right-shift next.

6. Overflow, and why `-INT_MIN == INT_MIN`¶

Apply the negation recipe to the most negative 8-bit number, -128:

-128 is 1000_0000.
Flip all bits: 0111_1111 (which is +127).
Add 1: 1000_0000 (which is -128 again).

Negating -128 gives -128. The asymmetric range bites: there is no +128 in 8-bit two's complement, so when you ask for the negative of -128 the result has to wrap somewhere, and it wraps back to itself.

In Go, int32(math.MinInt32) * -1 == math.MinInt32. In C, signed integer overflow is undefined behavior and modern compilers will optimize aggressively assuming it cannot happen. This is the source of a long list of CVEs (look up the history of -fwrapv and -fno-strict-overflow if you want the war stories). Two's complement gives you a clean mathematical model; the C language's "undefined behavior on overflow" rule lets compilers pretend the model is even cleaner than it is. The two are not the same thing.

Practical rule: assume your signed integers never reach INT_MIN or INT_MAX. If they might, either widen the type, use math/bits.Add64 / math.AddInt32 with explicit overflow checks (Go 1.22+ has these), or switch to unsigned with explicit "wraparound is fine" semantics.

7. Signed vs unsigned right shift¶

Left shift (<<) does the same thing for signed and unsigned: it always fills the new low bits with zeros.

Right shift (>>) does different things depending on the type:

Unsigned right shift (called "logical shift") fills the new high bits with zeros. Half the value, every shift.
Signed right shift (called "arithmetic shift") fills the new high bits with copies of the sign bit. Preserves sign; half the value rounded toward negative infinity.

var a int8 = -8      // 1111_1000
var b uint8 = 0xF8   // 1111_1000  (same bits!)
fmt.Printf("%d\n", a >> 1)         // -4   ... 1111_1100 (sign-extended)
fmt.Printf("%d\n", b >> 1)         // 124  ... 0111_1100 (zero-filled)

Identical bits in memory, opposite high-bit behavior on shift, because Go uses the type to decide. C has the same split. Rust has explicit wrapping_shr and unsigned_shr for when you need to be precise. JavaScript famously has >> (arithmetic) and >>> (logical) as distinct operators because all its numbers look the same to the runtime.

The arithmetic right shift is exactly the sign-extension trick from the Bit operations page: shift left to push the sign bit up, then arithmetic-shift right to copy it back down. Two operations build a full N-bit-to-M-bit sign extender out of nothing but << and >>.

8. Advanced: production consequences¶

8.1 The signed/unsigned comparison trap¶

C compilers will silently convert signed-to-unsigned in mixed comparisons, often producing wrong answers. Classic:

int  i = -1;
unsigned u = 1;
if (i < u) { ... }   // FALSE! i is converted to unsigned 0xFFFFFFFF, which is > 1.

Go forbids the implicit conversion and makes you write int(u) or uint(i) explicitly, which surfaces the question. This is one of the few places Go's strict type rules are obviously protecting you from a real-world bug pattern. Rust does the same.

8.2 Why the GCC option `-Wsign-compare` exists¶

For any function that takes a size_t (which is unsigned) and compares against a signed loop counter, the compiler will warn. Decades of buffer-overflow CVEs have come from "negative length passed in as a size_t looks gigantic" mistakes. The standard pattern: if (len < 0 || len > buf_size) return -1; - the len < 0 check must come first because if len is unsigned the second comparison cannot catch a "negative" value.

8.3 Bit-twiddling negative numbers¶

The negation recipe + the all-ones property give you a small toolbox:

-x == ~x + 1. The recipe, in operator form.
x & -x isolates the lowest set bit of x. Because -x flips every bit above the lowest set bit and leaves the lowest set bit unchanged (the +1 propagates exactly to that position), AND'ing gives you that single bit. This is the trick from bit operations, and it works for any width because two's complement is uniform across widths.
x & (x - 1) == 0 iff x is a power of two or zero. Because subtracting 1 from a power of two flips the high set bit down and turns every bit below it on, so AND'ing with the original gives zero. (Subtracting 1 from anything else leaves at least one bit in common with the original.)

These three identities come up in low-level code constantly. Recognize them on sight; do not re-derive them every time.

8.4 Why CRCs use XOR and shift¶

A cyclic-redundancy-check polynomial operates over GF(2), the field of bits under XOR-as-addition and AND-as-multiplication. Two's complement is irrelevant inside the CRC's math - the data is just bits - but the hardware is using two's complement arithmetic to manipulate the bit register. When you see CRC code that XOR-shifts an integer 8 or 32 times per byte processed, the right shift is logical (uint32 >>) because the CRC has no notion of sign; using a signed shift would inject sign-extension garbage into the high bits and corrupt the polynomial division. Always use unsigned types for CRC, hashing, and cipher state.

8.5 Sign extension at FFI boundaries¶

Calling a C function that takes an int8_t from a Go program that has a byte? The two are 8 bits each, but int8_t is signed and Go's byte is unsigned. Converting byte to int8 re-interprets the same bits with a different sign rule, so byte(0xFF) becomes int8(-1). Passing that to C and then printing as %d will give you -1, not 255. The bits did not change; the sign extension on read did. This is the single most common FFI subtle bug, and it is just two's complement showing up at a language boundary.

9. The mental model to keep¶

N-bit two's complement: bit N-1 is worth -2^(N-1), every other bit k is worth +2^k. That is the whole rule.
Negate by NOT + 1.
-1 is "all bits set," at any width.
Ordinary unsigned ADD is also signed ADD - the CPU has one instruction.
Right shift is type-dependent: zero-fill for unsigned, sign-fill for signed.
The range is asymmetric: one more negative than positive, so -INT_MIN is undefined / wraps.

Once you see two's complement as "the sign bit just contributes a negative power of two," the apparent magic dissolves. Every CPU, every modern programming language, and every binary file format on every machine you have ever touched works exactly this way.

10. Further reading¶

Hacker's Delight by Henry S. Warren - chapter 2 is the canonical reference for two's-complement identities.
Go's math/bits package - the portable wrappers over CPU bit instructions.
The C99 standard's annex on integer overflow, if you ever need to argue with a compiler about -fwrapv.
Bit operations - prerequisite if you skipped it.