SyntaxPilot
Courses/CS Fundamentals for Placements/Lesson 3

CS Fundamentals for Placements · Lesson 3 of 90 · 15 min

Signed numbers and binary arithmetic

unsigned integerssign-magnitude1's complement2's complementrange of n-bit signed and unsigned numbersnegative zerobinary additionbinary subtraction via 2's complementcarryoverflow and its detectionsign extensionbitwise AND/OR/XOR/NOTlogical shiftarithmetic shift

These are the notes for CS Fundamentals for Placements, episode 3. Last episode every number was positive. But a bank balance can go below zero, and a bit has no minus sign. Here you invent negative numbers three times: sign-magnitude and 1's complement fail, and 2's complement is what every computer uses. Then you meet binary addition and the carry, subtraction as addition, overflow (127 + 1 = -128) and how a CPU detects it, sign extension, the bitwise operators AND, OR, XOR and NOT, logical and arithmetic shifts, and the idea behind Booth's algorithm. Every term is explained in plain words, and there is a full glossary at the end. All outputs below are real: C compiled with gcc -O2 -Wno-unused-result main.c -o main -lm (gcc 13.3) and Python 3.13.

A quick refresher: a bit is one 0 or 1, a byte is 8 bits, the MSB (most significant bit) is the leftmost bit and the LSB (least significant bit) is the rightmost.

The six problems

Problem What it teaches
0 minus 1 = 255? Unsigned numbers and their range
5 + (-5) = -10? Sign-magnitude and 1's complement, and why they fail
The odometer trick 2's complement
127 + 1 = -128 Overflow, and how to detect it
-5 becomes 251 Sign extension vs zero extension
Flags and fast maths Bitwise operators, shifts, Booth's algorithm

Problem 1: a balance below zero (unsigned numbers)

An unsigned char in C is one byte with no sign: unsigned means only zero and positive numbers. 8 bits give 2⁸ = 256 patterns, so it holds 0 to 255.

#include <stdio.h>

int main(void) {
    unsigned char balance = 0;    // 8 bits, no sign: 0 to 255
    printf("balance = %d\n", balance);

    balance = balance - 1;        // spend 1 rupee
    printf("balance = %d\n", balance);
    return 0;
}

Output:

balance = 0
balance = 255
  • 0 minus 1 wrapped around to the top. Every pattern is already used for 0 to 255, so there is no room for -1.
  • Wrap-around for unsigned types is guaranteed by C: the result is taken modulo 2ⁿ (here modulo 256, so -1 becomes 255).
  • Rule: n unsigned bits hold 0 to 2ⁿ - 1. To store negatives, we must give up some patterns. Which ones?

Problem 2: two failed attempts

Attempt 1: sign-magnitude

Use the MSB as a sign bit: 0 for plus, 1 for minus. The other 7 bits hold the magnitude (the size of the number, ignoring its sign). This is sign-magnitude.

# attempt 1: sign-magnitude in 8 bits (MSB = sign)
def sm(n):
    sign = "1" if n < 0 else "0"
    return sign + f"{abs(n):07b}"

def add_bits(a, b):              # plain binary addition, 8 bits
    return f"{(int(a, 2) + int(b, 2)) % 256:08b}"

print("+5 =", sm(5))
print("-5 =", sm(-5))
print("+5 + -5 =", add_bits(sm(5), sm(-5)))
print("+0 =", sm(0), " -0 =", "1" + "0" * 7)

Output:

+5 = 00000101
-5 = 10000101
+5 + -5 = 10001010
+0 = 00000000  -0 = 10000000
  • f"{abs(n):07b}" writes the magnitude as 7 binary digits; % 256 keeps only 8 bits, like an 8-bit adder.
  • 5 + (-5) gave 10001010, which reads as -10. The adder doesn't know the first bit is special, so it adds it like any other bit.
  • There are two zeros: +0 = 00000000 and -0 = 10000000 (negative zero). One pattern is wasted, and every "is it zero?" test must check both.

Attempt 2: 1's complement

To make -5, flip every bit of +5 (0 becomes 1, 1 becomes 0). This is 1's complement. We also print the carry: the extra 1 that falls off the left end when a sum needs 9 bits.

# attempt 2: 1's complement (flip every bit)
def ones(n):
    if n >= 0:
        return f"{n:08b}"
    return "".join("1" if b == "0" else "0" for b in f"{-n:08b}")

def add_bits(a, b):
    total = int(a, 2) + int(b, 2)
    return f"{total % 256:08b} carry {total // 256}"

print("-5 =", ones(-5))
print("+5 + -5 =", add_bits(ones(5), ones(-5)))
print("+5 + -3 =", add_bits(ones(5), ones(-3)))

Output:

-5 = 11111010
+5 + -5 = 11111111 carry 0
+5 + -3 = 00000001 carry 1
  • 5 + (-5) = 11111111, which in 1's complement is -0. Still two zeros.
  • 5 + (-3) gave 1 with a carry of 1. The right answer is 2. 1's complement needs an extra step, the end-around carry: add the carry back in at the right end.
   0 0 0 0 0 1 0 1    (+5)
 + 1 1 1 1 1 1 0 0    (-3 in 1's complement)
 = 1 0 0 0 0 0 0 0 1  carry out = 1, 8-bit part = 00000001
 + 0 0 0 0 0 0 0 1    end-around carry: add it back
 =   0 0 0 0 0 0 1 0  (+2) correct

Extra hardware, and still two zeros.

Problem 3: 2's complement (the odometer trick)

A 3-digit car odometer An 8-bit number
At 000, roll back one: it shows 999 00000000 - 1 = 11111111: call it -1
999 + 1 rolls to 000, the extra digit falls off -1 + 1 = 0 if we drop the carry out
Only one 000, no "minus zero" 2's complement: -x = flip every bit, then add 1
# the fix: 2's complement = flip every bit, then add 1
def twos(n):
    return f"{n % 256:08b}"

def add_bits(a, b):
    return f"{(int(a, 2) + int(b, 2)) % 256:08b}"   # carry out is dropped

print("-5 =", twos(-5))
print("+5 + -5 =", add_bits(twos(5), twos(-5)))
print("+5 + -3 =", add_bits(twos(5), twos(-3)))
print("-1 =", twos(-1), " -128 =", twos(-128))

Output:

-5 = 11111011
+5 + -5 = 00000000
+5 + -3 = 00000010
-1 = 11111111  -128 = 10000000
  • n % 256 in Python gives exactly the 8-bit 2's complement pattern (-5 % 256 = 251 = 11111011).
  • Check the recipe: 5 = 00000101, flip → 11111010, add 1 → 11111011. Yes.
  • Plain addition now gives correct answers, and there is one zero. One adder circuit does both adding and subtracting, which is why every modern CPU uses 2's complement.

Reading a 2's complement number

The MSB is worth -128 instead of +128 (in n bits: -2ⁿ⁻¹). So 11111011 = -128 + 64 + 32 + 16 + 8 + 2 + 1 = -5, and 10000000 = -128.

Shortcut for a negative pattern: flip and add 1 to get its magnitude. 11111011 → 00000100 + 1 = 00000101 = 5, so it is -5. Another shortcut for -x: copy bits from the right up to and including the first 1, then flip the rest (5 = 0000 0101 → 1111 1011).

Range table

Bits Unsigned Sign-magnitude 1's complement 2's complement
4 0 to 15 -7 to +7 -7 to +7 -8 to +7
8 0 to 255 -127 to +127 -127 to +127 -128 to +127
16 0 to 65,535 -32,767 to +32,767 -32,767 to +32,767 -32,768 to +32,767
32 0 to 4,294,967,295 -2,147,483,647 to +2,147,483,647 -2,147,483,647 to +2,147,483,647 -2,147,483,648 to +2,147,483,647
n 0 to 2ⁿ - 1 -(2ⁿ⁻¹ - 1) to 2ⁿ⁻¹ - 1 -(2ⁿ⁻¹ - 1) to 2ⁿ⁻¹ - 1 -2ⁿ⁻¹ to 2ⁿ⁻¹ - 1

Sign-magnitude and 1's complement waste a pattern on -0; 2's complement uses it for one extra negative number. All three systems store a positive number the same way.

Problem 4: adding and subtracting

Binary addition, column by column

Rules: 0+0 = 0, 0+1 = 1, 1+1 = 10 (write 0, carry 1), 1+1+1 = 11 (write 1, carry 1). Work from the right, like school.

    1 1 1 1          carries
    0 1 1 0 1 1      (27)
  + 0 0 1 1 1 0      (14)
  = 1 0 1 0 0 1      (41)
Column (from right) Bits + carry in Write Carry out
0 1 + 0 + 0 = 1 1 0
1 1 + 1 + 0 = 2 0 1
2 0 + 1 + 1 = 2 0 1
3 1 + 1 + 1 = 3 1 1
4 1 + 0 + 1 = 2 0 1
5 0 + 0 + 1 = 1 1 0

Subtraction via 2's complement

a - b = a + (2's complement of b). No subtractor circuit is needed.

40 - 25 in 8 bits: 25 = 00011001, so -25 = 11100111.

    0 0 1 0 1 0 0 0    (40)
  + 1 1 1 0 0 1 1 1    (-25)
  = 1 0 0 0 0 1 1 1 1  carry out 1 is dropped → 00001111 = 15

25 - 40: -40 = 11011000.

    0 0 0 1 1 0 0 1    (25)
  + 1 1 0 1 1 0 0 0    (-40)
  =   1 1 1 1 0 0 0 1  no carry out; MSB is 1 → flip+1 = 00001111 → -15

Overflow: 127 + 1 = -128

#include <stdio.h>

int main(void) {
    signed char score = 127;          // the biggest 8-bit signed value
    printf("score = %d\n", score);

    score = score + 1;
    printf("score = %d\n", score);

    int a = 2147483647, sum;          // the biggest 32-bit int
    if (__builtin_add_overflow(a, 1, &sum))
        printf("overflow detected!\n");
    return 0;
}

Output:

score = 127
score = -128
overflow detected!
  • The sum 10000000 has its MSB set, so it reads as the most negative number. A result too big (or too small) for the bits you have is overflow.
  • Precisely: score + 1 is computed as an int (128), then stored back into a signed char. That conversion of an out-of-range value is implementation-defined; gcc wraps modulo 256, giving -128.
  • __builtin_add_overflow is a gcc (and clang) built-in that does the addition and returns true if the result did not fit. Writing a + 1 directly on an int at its maximum would be undefined behaviour in C.

Real life: in December 2014, YouTube posted on Google+: "We never thought a video would be watched in numbers greater than a 32-bit integer (=2,147,483,647 views), but that was before we met PSY. 'Gangnam Style' has been viewed so many times we have to upgrade!" The view counter moved to a 64-bit integer.

How a CPU detects overflow

  • Carry: a 1 falls off the left end. It is the warning sign for unsigned numbers. In 2's complement, 5 + (-3) had a carry and the answer was fine.
  • Overflow: the sign came out wrong. It matters for signed numbers.
  • Same-sign rule: positive + positive giving negative, or negative + negative giving positive, means overflow. Positive + negative can never overflow: the answer lies between them.
  • Hardware rule: overflow happened if the carry into the MSB ≠ carry out of the MSB. The CPU stores this in the overflow flag (V).
8-bit sum Carry into MSB Carry out of MSB Overflow? Result
127 + 1 = 01111111 + 00000001 1 0 Yes 10000000 = -128
-128 + -1 = 10000000 + 11111111 0 1 Yes 01111111 = +127
5 + -3 = 00000101 + 11111101 1 1 No 00000010 = 2
27 + 14 0 0 No 41

Problem 5: widening a number (sign extension)

Copy a byte into a 16-bit short. Both bytes below hold the bits 11111011, but s is signed (-5) and u is unsigned (251).

#include <stdio.h>

int main(void) {
    signed char   s = -5;        // bits 11111011
    unsigned char u = 0xFB;      // the same bits 11111011

    short a = s;                 // widen to 16 bits
    short b = u;

    printf("a = %d  bits %04hx\n", a, a);
    printf("b = %d  bits %04hx\n", b, b);
    return 0;
}

Output:

a = -5  bits fffb
b = 251  bits 00fb
  • %04hx prints a short in hexadecimal, 4 digits (each hex digit = 4 bits; f = 1111, b = 1011).
  • u became 00fb: zeros added on the left. This is zero extension, correct for unsigned numbers. Done to -5, it would give 251. Wrong.
  • s became fffb: C copied the sign bit into all new bits. This is sign extension, and it keeps a 2's complement value unchanged.

Worked: 4-bit 1010 (-6) sign-extended to 8 bits is 11111010 (still -6); zero-extended it is 00001010 (10).

Problem 6: bitwise operators

Hostel room switches Bitwise operator
Light on only if BOTH the main and room switch are on AND &: 1 only if both bits are 1
Bell rings if EITHER the front or back button is pressed OR \|: 1 if at least one bit is 1
Stair light with two switches: flip either, it changes XOR ^: 1 if the bits differ
Flip every switch NOT ~: flip every bit
a b a & b a | b a ^ b ~a
0 0 0 0 0 1
0 1 0 1 1 1
1 0 0 1 1 0
1 1 1 1 0 0
#include <stdio.h>

int main(void) {
    int x = 12, y = 10;          // 1100 and 1010

    printf("x & y = %d\n", x & y);   // AND: 1 if both are 1
    printf("x | y = %d\n", x | y);   // OR:  1 if either is 1
    printf("x ^ y = %d\n", x ^ y);   // XOR: 1 if they differ
    printf("~x    = %d\n", ~x);      // NOT: flip every bit
    return 0;
}

Output:

x & y = 8
x | y = 14
x ^ y = 6
~x    = -13
  • 1100 & 1010 = 1000 (8), 1100 | 1010 = 1110 (14), 1100 ^ 1010 = 0110 (6).
  • ~12 = -13: an int has 32 bits and NOT flips all of them, including the sign bit. In 2's complement, ~x = -x - 1 (that's why -x = ~x + 1).
  • A mask is a number chosen to pick out certain bits: x & 1 tests the LSB (odd or even), x | (1 << k) sets bit k, x & ~(1 << k) clears it, x ^ (1 << k) toggles it. File permissions and settings flags are stored like this.

Problem 7: shifts

5      = 00000101
5 << 1 = 00001010  = 10   (x 2)
-16 >> 2:  11110000 → 11111100 = -4
  • Left shift by k (<<): every bit slides k places left, zeros enter on the right: multiply by 2ᵏ (if nothing important falls off).
  • Right shift by k (>>): bits slide right: divide by 2ᵏ, rounding down.
  • Logical shift right: fill the new left bits with 0s (used for unsigned numbers).
  • Arithmetic shift right: copy the sign bit into the new left bits, like sign extension, so negatives stay negative.
#include <stdio.h>

int main(void) {
    printf("5 << 3   = %d\n", 5 << 3);      // x 2^3
    printf("40 >> 2  = %d\n", 40 >> 2);     // / 2^2

    int s = -16;                            // signed: arithmetic shift
    unsigned char u = 0xF0;                 // unsigned: logical shift
    printf("-16 >> 2 = %d\n", s >> 2);
    printf("0xF0 >> 2 = 0x%X\n", u >> 2);
    return 0;
}

Output:

5 << 3   = 40
40 >> 2  = 10
-16 >> 2 = -4
0xF0 >> 2 = 0x3C
  • gcc does an arithmetic shift on signed numbers, so -16 kept its sign. 0xF0 = 11110000 became 0x3C = 00111100: zeros came in, a logical shift.
  • The C standard leaves right-shifting a negative number implementation-defined. In Java you choose: >> is arithmetic and >>> is logical.

Booth's algorithm: the idea

A simple CPU multiplies by shift and add: for every 1 bit in the multiplier, add a shifted copy of the other number. 126 = 01111110 has six 1s, so six adds. But a run of 1s has a shortcut:

0111 1110 = 1000 0000 - 0000 0010 (126 = 128 - 2). So 13 × 126 = (13 << 7) - (13 << 1): one add, one subtract.

# multiply x by 126 (binary 01111110)
x = 13

# shift-and-add: one add for every 1 bit
adds = [x << i for i in range(8) if (126 >> i) & 1]
print("shift-and-add:", len(adds), "adds ->", sum(adds))

# Booth's idea: a run of 1s = (one big add) - (one small subtract)
# 01111110 = 10000000 - 00000010 = 128 - 2
print("Booth:         2 steps ->", (x << 7) - (x << 1))
print("check:        ", x * 126)

Output:

shift-and-add: 6 adds -> 1638
Booth:         2 steps -> 1638
check:         1638

Booth recoding: give each bit i the digit (bit i-1) - (bit i), with a 0 imagined to the right of the LSB. For 01111110 the digits are +1 0 0 0 0 0 -1 0: +1 where a run of 1s starts above, -1 where it ends below. That is +128 - 2.

Booth's radix-2 algorithm (registers: A = 0, Q = multiplier, Q-1 = 0, M = multiplicand; repeat n times): look at Q0 Q-1. 10 → A = A - M; 01 → A = A + M; 00 or 11 → do nothing. Then arithmetic shift right A, Q, Q-1 together. Example: 7 × -3 in 4 bits (M = 0111, -M = 1001, Q = 1101), generated and checked with Python:

Step Q0 Q-1 Action A Q Q-1
init 0000 1101 0
1 1 0 A = A - M 1001 1101 0
shift 1100 1110 1
2 0 1 A = A + M 0011 1110 1
shift 0001 1111 0
3 1 0 A = A - M 1010 1111 0
shift 1101 0111 1
4 1 1 none 1101 0111 1
shift 1110 1011 1

Result A:Q = 1110 1011 = -21, and 7 × -3 = -21. Booth works directly on 2's complement negatives.

Implementation-defined vs undefined behaviour in C

Situation Category What gcc does here
Right shift of a negative int (-16 >> 2) Implementation-defined: the compiler must choose and document Arithmetic shift: -4
Storing an out-of-range value in a signed type (signed char c = 200;) Implementation-defined Wraps modulo 256: -56
Unsigned arithmetic going past the range (0 - 1 in unsigned char) Fully defined: wraps modulo 2ⁿ 255
Signed int overflow (INT_MAX + 1) Undefined behaviour: the standard makes no promise at all; the optimiser may assume it never happens Do not rely on any result; check first

Common mistakes (and the real output)

Mistake Code Output Fix
Unsigned value below 0 unsigned char balance = 0; balance = balance - 1; balance = 255 Use a signed type for values that can be negative
Signed overflow signed char score = 127; score = score + 1; score = -128 Use a wider type, or check with __builtin_add_overflow
Expecting ~12 to be 3 printf("%d", ~12); -13 Mask it: ~12 & 0xF gives 3
Thinking >> equals / for negatives -7 >> 1 vs -7 / 2 -4 vs -3 / rounds toward zero, >> rounds down
Comparing signed with unsigned -1 < 1u false -1 is converted to unsigned (4294967295); cast or keep types the same
Out-of-range value into a small signed type signed char c = 200; c = -56 Use a type whose range fits
Zero-extending a signed byte unsigned char u = 0xFB; short b = u; 251 Keep it signed char so C sign-extends
Treating carry as overflow 5 + (-3) in 8 bits carry 1, answer 2 is correct Signed: check the overflow flag, not the carry

The program behind four of these rows:

#include <stdio.h>

int main(void) {
    printf("~12       = %d\n", ~12);
    printf("~12 & 0xF = %d\n", ~12 & 0xF);

    printf("-7 / 2    = %d\n", -7 / 2);     // division rounds toward zero
    printf("-7 >> 1   = %d\n", -7 >> 1);    // shift rounds down

    int n = -1;
    unsigned int one = 1;
    if (n < one) printf("-1 < 1u is true\n");
    else         printf("-1 < 1u is false\n");

    signed char c = 200;                    // out of range for signed char
    printf("c = %d\n", c);
    return 0;
}

Output:

~12       = -13
~12 & 0xF = 3
-7 / 2    = -3
-7 >> 1   = -4
-1 < 1u is false
c = -56

Mini project: an 8-bit ALU simulator

An ALU (arithmetic logic unit) is the part of a CPU that adds, subtracts and does bitwise work. Ours adds and subtracts 8-bit numbers and sets four flags (single bits that describe the last result): C carry, V overflow, Z zero, N sign (negative).

# 8-bit ALU simulator: ADD and SUB with C, V, Z, N flags
BITS = 8
MASK = (1 << BITS) - 1               # 0b11111111 = 255

def to_signed(u):
    """Read an 8-bit pattern as a 2's complement number."""
    return u - 256 if u & 0x80 else u

def alu(op, a, b):
    a &= MASK                        # -3 becomes 11111101, and so on
    b &= MASK
    cin = 0
    if op == "SUB":                  # a - b = a + NOT b + 1
        b = ~b & MASK                # flip every bit...
        cin = 1                      # ...and the +1 goes in as a carry
    total = a + b + cin
    result = total & MASK            # keep 8 bits, drop the carry out
    carry_out = total >> BITS                          # carry out of the MSB
    carry_in = ((a & 0x7F) + (b & 0x7F) + cin) >> 7    # carry into the MSB
    flags = {"C": carry_out,
             "V": carry_in ^ carry_out,                # overflow flag
             "Z": int(result == 0),                    # zero flag
             "N": result >> 7}                         # sign flag
    return result, flags

tests = [("ADD", 27, 14), ("ADD", 5, -3), ("ADD", 127, 1), ("ADD", -128, -1),
         ("ADD", 100, 50), ("SUB", 5, 5), ("SUB", 3, 5), ("SUB", 0, -128)]

print(f"{'op':<4}{'a':>5}{'b':>5}   result    signed  C V Z N")
for op, a, b in tests:
    r, f = alu(op, a, b)
    print(f"{op:<4}{a:>5}{b:>5}   {r:08b} {to_signed(r):>7}  "
          f"{f['C']} {f['V']} {f['Z']} {f['N']}")

Output:

op      a    b   result    signed  C V Z N
ADD    27   14   00101001      41  0 0 0 0
ADD     5   -3   00000010       2  1 0 0 0
ADD   127    1   10000000    -128  0 1 0 1
ADD  -128   -1   01111111     127  1 1 0 0
ADD   100   50   10010110    -106  0 1 0 1
SUB     5    5   00000000       0  1 0 1 0
SUB     3    5   11111110      -2  0 0 0 1
SUB     0 -128   10000000    -128  0 1 0 1
  • & MASK keeps 8 bits, exactly like % 256. ^ on two flag bits is 1 when they differ: the "carry in ≠ carry out" rule.
  • 5 + (-3): C = 1 but V = 0, the answer is right. 127 + 1 and 100 + 50: V = 1, the true answers (128, 150) don't fit.
  • SUB feeds the "+1" of the 2's complement in as a carry, as real adders do. That is why 0 - (-128) is correctly flagged as overflow: +128 does not fit in 8 bits.
  • In this design, C = 1 after a SUB means "no borrow" (3 - 5 needed a borrow, so C = 0).

Practice

  1. Write -100 in 8-bit sign-magnitude, 1's complement and 2's complement.
  2. Same for -37.
  3. Read 10110011 as unsigned, sign-magnitude, 1's complement and 2's complement.
  4. What is the range of a 12-bit 2's complement number? Of a 6-bit sign-magnitude number?
  5. In 8-bit 2's complement, which overflow: (a) 100 + 50 (b) -100 + -50 (c) 100 + -50 (d) -64 + -64 (e) 64 + 64?
  6. Add 01101001 + 00110101 (8-bit 2's complement). Result? Overflow?
  7. Compute 25 - 40 in 8 bits using 2's complement.
  8. Sign-extend and zero-extend 10011100 to 16 bits. What values do you get?
  9. For 8-bit a = 0x5A, b = 0x3C, find a & b, a | b, a ^ b, ~a.
  10. For v = 10110100 (8 bits), find a logical right shift by 2, an arithmetic right shift by 2, and a left shift by 1. Interpret as signed.
  11. In C with gcc, what are -25 >> 2 and -25 / 4?
  12. Write C that prints odd/even with x & 1, and sets, clears and toggles bits with masks.
  13. Multiply 13 by 30 using only shifts and one subtraction.
  14. Booth-recode the multiplier 00111100. How many add/subtract operations instead of shift-and-add's four?
  15. 11000000 + 10000000 in 8 bits: carry into MSB, carry out, overflow?
  16. What is -(-128) in 8-bit 2's complement? What is the 2's complement of 0?
  17. What does x & (x - 1) do? Try x = 01101000.
Solutions
  1. Magnitude 100 = 1100100. Sign-magnitude 11100100; 1's 10011011; 2's 10011100.
  2. 37 = 0100101. Sign-magnitude 10100101; 1's 11011010; 2's 11011011.
  3. Unsigned 179; sign-magnitude -51; 1's complement -76 (flip → 01001100); 2's complement -77 (179 - 256).
  4. 12-bit 2's: -2¹¹ to 2¹¹ - 1 = -2048 to 2047. 6-bit sign-magnitude: -31 to +31.
  5. (a) Yes, 150 > 127. (b) Yes, -150 < -128. (c) No, different signs never overflow. (d) No, -128 fits exactly. (e) Yes, 128 > 127.
  6. 105 + 53 = 158 → 10011110 = -98. Positive + positive gave negative: overflow.
  7. 00011001 + 11011000 = 11110001, no carry out, = -15.
  8. Sign extension: 1111111110011100 = -100. Zero extension: 0000000010011100 = 156.
  9. a & b = 00011000 (24), a | b = 01111110 (126), a ^ b = 01100110 (102), ~a = 10100101.
  10. v = -76. Logical 00101101 (45); arithmetic 11101101 (-19, which is -76 / 4 rounded down); left by 1 01101000 (104, not -152: overflow, the sign changed).
  11. -25 >> 2 = -7 (rounds down from -6.25); -25 / 4 = -6 (rounds toward zero).
  12. Run with gcc:
#include <stdio.h>

int main(void) {
    for (int x = 6; x <= 9; x++)
        printf("%d is %s\n", x, (x & 1) ? "odd" : "even");

    int flags = 0;                 // 8 switches, all off
    flags = flags | (1 << 2);      // set bit 2
    flags = flags | (1 << 0);      // set bit 0
    printf("after set:    %d\n", flags);
    flags = flags & ~(1 << 2);     // clear bit 2
    printf("after clear:  %d\n", flags);
    flags = flags ^ (1 << 3);      // toggle bit 3
    printf("after toggle: %d\n", flags);

    int n = 13;
    printf("13 x 30 = %d\n", (n << 5) - (n << 1));   // 32n - 2n
    return 0;
}
6 is even
7 is odd
8 is even
9 is odd
after set:    5
after clear:  1
after toggle: 9
13 x 30 = 390
  1. 30 = 32 - 2, so (13 << 5) - (13 << 1) = 416 - 26 = 390 (see the program above).
  2. 00111100 = 01000000 - 00000100 (64 - 4 = 60). Recoded digits 0 +1 0 0 0 -1 0 0: one add and one subtract instead of four adds.
  3. Carry into MSB 0, carry out 1, they differ: overflow (-64 + -128 = -192 doesn't fit; the 8-bit result 01000000 = +64).
  4. -128 → flip 01111111, add 1 → 10000000 = -128 again (+128 doesn't fit). 2's complement of 0: flip → 11111111, +1 → 00000000 with the carry dropped: still 0, only one zero.
  5. It clears the lowest 1 bit: 104 & 103 = 01100000 (96). If the result is 0, x was a power of two (or 0).

Quick quiz

An 8-bit 2's complement byte holds 1 1 1 1 0 1 1 0. What number is it?

  • A. 246
  • B. -10
  • C. -118
  • D. -9
Answer

B, -10. The MSB is 1, so it is negative. Flip and add 1: 00001001 + 1 = 00001010 = 10, so -10. (246 is the unsigned reading; -118 is the sign-magnitude reading.)

Interview questions

  • Why do computers use 2's complement? One zero, and the same adder circuit does addition and subtraction with no special rules.
  • How do you find -x in 2's complement? Flip every bit and add 1 (equivalently, ~x + 1).
  • Range of an n-bit 2's complement number? -2ⁿ⁻¹ to 2ⁿ⁻¹ - 1; for 32 bits, -2,147,483,648 to 2,147,483,647.
  • Why is the range not symmetric? Zero takes one of the non-negative patterns, leaving one more negative pattern (-128 has no positive partner in 8 bits).
  • Carry vs overflow? Carry: a bit falls off the left end (unsigned problem). Overflow: the signed result has the wrong sign; detected when carry into MSB ≠ carry out of MSB.
  • Can adding a positive and a negative number overflow? No; the result lies between them.
  • What is sign extension and when is it used? Copying the MSB into new high bits when widening a signed value, so its value stays the same.
  • Logical vs arithmetic right shift? Logical fills with 0s; arithmetic copies the sign bit. Java: >> arithmetic, >>> logical.
  • Why is ~x equal to -x - 1? Because -x = ~x + 1 in 2's complement.
  • Is signed int overflow defined in C? No, it is undefined behaviour. Unsigned overflow wraps and is defined.
  • What is the idea of Booth's algorithm? Replace a run of 1s in the multiplier with one add and one subtract (0111 1110 = 1000 0000 - 0000 0010); it handles 2's complement negatives directly.
  • How do you check if a number is a power of two with bit operations? x > 0 && (x & (x - 1)) == 0.

Glossary

Term Plain meaning Example
Bit / byte One 0 or 1 / a group of 8 bits 10110011 is one byte
MSB / LSB Leftmost (biggest place value) / rightmost bit In 10000001, both are 1
Unsigned integer A whole number stored with no sign: only 0 and positives unsigned char: 0 to 255
Signed integer A whole number that can be negative signed char: -128 to 127
Sign bit The MSB used to say plus (0) or minus (1) 10000101
Magnitude The size of a number ignoring its sign magnitude of -5 is 5
Sign-magnitude Sign bit + magnitude in the other bits -5 = 10000101
1's complement Negative = flip every bit of the positive -5 = 11111010
2's complement Negative = flip every bit, then add 1; MSB worth -2ⁿ⁻¹ -5 = 11111011
Negative zero A second pattern meaning 0 in sign-magnitude and 1's complement 10000000 (SM), 11111111 (1's)
Range of n-bit unsigned 0 to 2ⁿ - 1 8 bits: 0 to 255
Range of n-bit signed 2's: -2ⁿ⁻¹ to 2ⁿ⁻¹ - 1; SM and 1's: -(2ⁿ⁻¹ - 1) to 2ⁿ⁻¹ - 1 8 bits: -128 to 127
Binary addition Adding column by column from the right with 0+0=0, 0+1=1, 1+1=10 27 + 14 = 101001
Carry The 1 passed to the next column when a column sums to 2 or 3 1 + 1 = 0, carry 1
Carry out The carry that falls off the left end of the whole number 5 + (-3) in 8 bits: carry out 1
End-around carry In 1's complement, adding the carry out back at the right end 00000001 + 1 = 00000010
Binary subtraction via 2's complement a - b computed as a + (flip b, add 1) 40 - 25 = 40 + 11100111
Overflow The true result doesn't fit in the bits available 127 + 1 in 8 bits gives -128
Overflow detection: same-sign rule Two same-sign operands giving a result of the other sign + plus + = - means overflow
Overflow detection: carries Overflow if carry into the MSB ≠ carry out of the MSB 127 + 1: in 1, out 0
Overflow flag (V) A CPU status bit set when signed overflow happened V = 1 after 100 + 50
Flag A single status bit an ALU sets about the last result (C, V, Z, N) Z = 1 after 5 - 5
Carry flag (C) Status bit holding the carry out C = 1 after 5 + (-3)
Zero flag (Z) / sign flag (N) Status bit set if the result is 0 / copy of the result's MSB 3 - 5: Z = 0, N = 1
Wrap-around Going past the end of the range comes back from the other end 0 - 1 = 255 (unsigned)
Modulo 2ⁿ Keeping only the remainder after dividing by 2ⁿ: keeping n bits 256 mod 256 = 0
Sign extension Widening a signed value by copying its MSB into new bits -5: fb → fffb
Zero extension Widening an unsigned value by adding 0s on the left 251: fb → 00fb
Hexadecimal (hex) Base 16; each digit stands for 4 bits 0xF0 = 11110000
Bitwise AND & Each result bit is 1 only if both bits are 1 1100 & 1010 = 1000
Bitwise OR \| Each result bit is 1 if at least one bit is 1 1100 \| 1010 = 1110
Bitwise XOR ^ Each result bit is 1 if the bits differ 1100 ^ 1010 = 0110
Bitwise NOT ~ Flip every bit ~12 = -13 (32-bit int)
Mask A number chosen to test, set, clear or toggle certain bits x & 1 tests odd/even
Left shift << Slide bits left, 0s enter on the right 5 << 1 = 10
Right shift >> Slide bits right; the bits on the right fall off 40 >> 2 = 10
Logical shift Right shift that fills with 0s 0xF0 >> 2 = 0x3C
Arithmetic shift Right shift that copies the sign bit -16 >> 2 = -4
Multiply/divide by powers of two x << k = x × 2ᵏ; x >> k = x ÷ 2ᵏ rounded down 5 << 3 = 40, -7 >> 1 = -4
Shift-and-add multiplication Add a shifted copy for every 1 bit of the multiplier 13 × 126: six adds
Booth's algorithm Multiplication that turns each run of 1s into one add and one subtract; works with 2's complement 0111 1110 = 1000 0000 - 0000 0010
Booth recoding Digit for bit i = (bit i-1) - (bit i), giving +1, 0, -1 01111110 → +1 0 0 0 0 0 -1 0
ALU The CPU part that does arithmetic and bitwise work the mini project
Implementation-defined behaviour The C standard lets each compiler choose, but it must document its choice gcc: -16 >> 2 = -4, (signed char)200 = -56
Undefined behaviour The C standard makes no promise at all; anything may happen INT_MAX + 1 on a signed int
__builtin_add_overflow A gcc/clang built-in that adds and reports whether it overflowed returns true for 2147483647 + 1
32-bit / 64-bit integer A whole number stored in 32 / 64 bits 32-bit signed max: 2,147,483,647

Summary

  • Unsigned: 0 to 2ⁿ - 1, wraps below 0 (0 - 1 = 255).
  • Sign-magnitude and 1's complement both have two zeros; sign-magnitude gives wrong sums, 1's complement needs an end-around carry.
  • 2's complement: -x = flip + 1, one zero, plain addition works; range -2ⁿ⁻¹ to 2ⁿ⁻¹ - 1; MSB worth -2ⁿ⁻¹.
  • Subtraction is adding the 2's complement. Carry is for unsigned; overflow (wrong sign; carry into MSB ≠ carry out) is for signed.
  • Sign extension copies the MSB when widening; zero extension pads with 0s for unsigned.
  • AND, OR, XOR, NOT work bit by bit; masks test, set, clear and toggle bits; ~x = -x - 1.
  • Shifts: left × 2ᵏ, right ÷ 2ᵏ rounded down; logical fills 0s, arithmetic copies the sign. Booth turns runs of 1s into add + subtract.
  • In C, signed int overflow is undefined; right-shifting negatives and out-of-range signed conversions are implementation-defined.

Next episode: numbers with a decimal point, and text. IEEE 754 floating point, why 0.1 + 0.2 != 0.3, ASCII, Unicode, UTF-8, and big- and little-endian byte order.