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;% 256keeps 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 =
00000000and -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 % 256in 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
10000000has 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 + 1is computed as anint(128), then stored back into asigned char. That conversion of an out-of-range value is implementation-defined; gcc wraps modulo 256, giving -128. __builtin_add_overflowis a gcc (and clang) built-in that does the addition and returns true if the result did not fit. Writinga + 1directly on anintat 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
%04hxprints a short in hexadecimal, 4 digits (each hex digit = 4 bits;f=1111,b=1011).ubecame00fb: zeros added on the left. This is zero extension, correct for unsigned numbers. Done to -5, it would give 251. Wrong.sbecamefffb: 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: aninthas 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 & 1tests 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=11110000became0x3C=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
& MASKkeeps 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
- Write -100 in 8-bit sign-magnitude, 1's complement and 2's complement.
- Same for -37.
- Read
10110011as unsigned, sign-magnitude, 1's complement and 2's complement. - What is the range of a 12-bit 2's complement number? Of a 6-bit sign-magnitude number?
- In 8-bit 2's complement, which overflow: (a) 100 + 50 (b) -100 + -50 (c) 100 + -50 (d) -64 + -64 (e) 64 + 64?
- Add
01101001 + 00110101(8-bit 2's complement). Result? Overflow? - Compute 25 - 40 in 8 bits using 2's complement.
- Sign-extend and zero-extend
10011100to 16 bits. What values do you get? - For 8-bit
a = 0x5A,b = 0x3C, finda & b,a | b,a ^ b,~a. - 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. - In C with gcc, what are
-25 >> 2and-25 / 4? - Write C that prints odd/even with
x & 1, and sets, clears and toggles bits with masks. - Multiply 13 by 30 using only shifts and one subtraction.
- Booth-recode the multiplier
00111100. How many add/subtract operations instead of shift-and-add's four? 11000000 + 10000000in 8 bits: carry into MSB, carry out, overflow?- What is -(-128) in 8-bit 2's complement? What is the 2's complement of 0?
- What does
x & (x - 1)do? Try x =01101000.
Solutions
- Magnitude 100 =
1100100. Sign-magnitude11100100; 1's10011011; 2's10011100. - 37 =
0100101. Sign-magnitude10100101; 1's11011010; 2's11011011. - Unsigned 179; sign-magnitude -51; 1's complement -76 (flip →
01001100); 2's complement -77 (179 - 256). - 12-bit 2's: -2¹¹ to 2¹¹ - 1 = -2048 to 2047. 6-bit sign-magnitude: -31 to +31.
- (a) Yes, 150 > 127. (b) Yes, -150 < -128. (c) No, different signs never overflow. (d) No, -128 fits exactly. (e) Yes, 128 > 127.
- 105 + 53 = 158 →
10011110= -98. Positive + positive gave negative: overflow. 00011001 + 11011000 = 11110001, no carry out, = -15.- Sign extension:
1111111110011100= -100. Zero extension:0000000010011100= 156. a & b = 00011000(24),a | b = 01111110(126),a ^ b = 01100110(102),~a = 10100101.- v = -76. Logical
00101101(45); arithmetic11101101(-19, which is -76 / 4 rounded down); left by 101101000(104, not -152: overflow, the sign changed). -25 >> 2= -7 (rounds down from -6.25);-25 / 4= -6 (rounds toward zero).- 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
- 30 = 32 - 2, so
(13 << 5) - (13 << 1)= 416 - 26 = 390 (see the program above). 00111100=01000000 - 00000100(64 - 4 = 60). Recoded digits0 +1 0 0 0 -1 0 0: one add and one subtract instead of four adds.- Carry into MSB 0, carry out 1, they differ: overflow (-64 + -128 = -192 doesn't fit; the 8-bit result
01000000= +64). - -128 → flip
01111111, add 1 →10000000= -128 again (+128 doesn't fit). 2's complement of 0: flip →11111111, +1 →00000000with the carry dropped: still 0, only one zero. - 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
intoverflow 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.