Computers store all data as binary (base-2) numbers. Negative integers are represented using two's complement, where you flip all the bits and add 1. You need to be able to convert between decimal and binary, represent negatives in two's complement, and add binary numbers by hand, including mixed-sign additions.
Difficulty: Foundational | Prerequisites: None, though familiarity with decimal place values helps.
Number representation is the foundation of everything a processor does. Before you can understand how MIPS instructions are encoded, how memory addresses work, or how arithmetic instructions behave, you need to understand how integers map to binary strings. This topic sits right at the start of CS 2340 because every subsequent topic (instruction encoding, machine code, addressing) builds on it.
Two's complement is the standard scheme for representing signed integers in hardware. If you are shaky on this, instruction-encoding questions and binary arithmetic on the exam will be significantly harder than they need to be.
Binary (base-2)
A number system that uses only the digits 0 and 1. Each digit position represents a power of 2, just as each position in decimal represents a power of 10. Think of it as the language your CPU actually speaks.
Bit
A single binary digit, either 0 or 1. In simple terms, this is the smallest unit of data a computer can work with.
Most significant bit (MSB)
The leftmost bit in a binary number. In a signed integer, this bit indicates the sign: 0 for positive, 1 for negative. Think of it as the bit that carries the most weight.
Least significant bit (LSB)
The rightmost bit in a binary number. It represents 2^0, which equals 1. In simple terms, this is the bit that tells you whether the number is odd or even.
Two's complement
The standard method for representing signed integers in binary. To get the two's complement (i.e. the negative) of a number: flip every bit, then add 1. Think of it as the computer's way of doing subtraction using addition hardware.
One's complement
The result of flipping every bit in a binary number (all 0s become 1s, all 1s become 0s). This is the intermediate step when computing two's complement. In simple terms, it is the bitwise inverse.
Sign extension
The process of extending a binary number to a wider bit width while preserving its sign. You copy the sign bit (MSB) into all the new positions. For example, the 8-bit value 1110 0101 becomes the 16-bit value 1111 1111 1110 0101.
Overflow
Occurs when the result of an arithmetic operation exceeds the range that can be represented in the available number of bits. In simple terms, the answer is too big (or too negative) to fit.
Repeatedly divide the decimal number by 2 and record the remainder at each step.
Read the remainders from bottom to top to get the binary representation.
Example: 42 in decimal
42 / 2 = 21 remainder 0
21 / 2 = 10 remainder 1
10 / 2 = 5 remainder 0
5 / 2 = 2 remainder 1
2 / 2 = 1 remainder 0
1 / 2 = 0 remainder 1
Result: 101010
Alternatively, sum powers of 2: 42 = 32 + 8 + 2 = 2^5 + 2^3 + 2^1 = 00101010 (8-bit).
Multiply each bit by its positional power of 2, then sum them.
Example: 101010 = 1(32) + 0(16) + 1(8) + 0(4) + 1(2) + 0(1) = 42.
To negate a binary number (find its two's complement):
Step 1: Write the positive value in binary.
Step 2: Flip every bit (0 becomes 1, 1 becomes 0). This gives the one's complement.
Step 3: Add 1 to the result.
Example: find the 8-bit representation of -67.
67 in binary: 01000011
Flip bits: 10111100
Add 1: 10111101
So -67 = 10111101 in 8-bit two's complement.
For an n-bit two's complement number, the representable range is -2^(n-1) to 2^(n-1) - 1.
8-bit: -128 to 127
16-bit: -32,768 to 32,767
32-bit: roughly -2.1 billion to 2.1 billion
Works exactly like decimal addition, but you carry at 2 instead of 10.
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10 (write 0, carry 1)
1 + 1 + 1 = 11 (write 1, carry 1)
Convert the negative number to two's complement.
Add the two binary numbers as normal.
If there is a carry out of the MSB, discard it (for same-width addition).
The result is in two's complement. If the MSB is 1, the result is negative; convert back to find the magnitude.
If the MSB is 1, the number is negative.
To find the magnitude: flip all bits and add 1, then put a minus sign in front.
Alternatively: the MSB in an n-bit number contributes -2^(n-1), and all other bits contribute their usual positive powers of 2. Sum them.
This mirrors the style of question on the exam (question 6 on the review).
Step 1: Convert 67 to 8-bit binary.
67 = 64 + 2 + 1 = 2^6 + 2^1 + 2^0 = 01000011
Step 2: Find two's complement of 67 to get -67.
Flip bits: 10111100. Add 1: 10111101. So -67 = 10111101.
Step 3: Convert 42 to 8-bit binary.
42 = 32 + 8 + 2 = 2^5 + 2^3 + 2^1 = 00101010
Step 4: Add -67 and 42 in binary.
10111101 (-67)
+ 00101010 ( 42)
----------
11100111Step 5: Interpret the result.
The MSB is 1, so the result is negative. To find the magnitude, flip and add 1:
Flip 11100111: 00011000. Add 1: 00011001.
00011001 = 16 + 8 + 1 = 25. So the result is -25.
Check: -67 + 42 = -25. Correct.
Students often think that to negate a binary number you just flip the MSB. You do not. You flip every bit and then add 1. Flipping only the MSB gives you a completely different number.
Students sometimes forget to add 1 after flipping the bits. That gives you the one's complement, not the two's complement, and your answer will be off by 1.
Students assume a carry out of the MSB during addition means overflow. For mixed-sign addition, a carry out of the MSB is normal and should be discarded. Overflow can only happen when adding two numbers of the same sign and getting a result of the opposite sign.
Students confuse "two's complement" (the representation system) with "taking the two's complement" (the operation of negating). The system uses the operation to represent negatives, but they are not the same thing.
⚠️ The exam includes a question where you convert two small integers to binary (one negative) and add them. This is worth 5 or 6 points. Show every step: the positive binary, the bit flip, the +1, the column-by-column addition, and the final decimal conversion.
⚠️ Understanding binary representation is also needed for the machine code encoding questions. Instruction fields (opcode, rs, rt, rd, shamt, funct, immediate) are all binary.
⚠️ Know the difference between signed and unsigned representations. Two's complement is for signed arithmetic (add, sub, slt). Unsigned operations (addu, subu, sltu) treat the same bit patterns differently.
True or False: In 8-bit two's complement, the range of representable values is -127 to 128.
Answer: False. The range is -128 to 127.
Fill in the blank: To negate a binary number using two's complement, you flip all the bits and then ______.
Answer: Add 1.
True or False: If you add two positive 8-bit numbers and the MSB of the result is 1, overflow has occurred.
Answer: True. Two positives should produce a positive result; an MSB of 1 means the result is negative, which is overflow.
What is the 8-bit two's complement representation of -1?
Answer: 11111111.
True or False: Discarding the carry-out bit is always wrong when adding binary numbers.
Answer: False. When adding a positive and negative number in two's complement, a carry-out is normal and is discarded.
Q: Convert the decimal number -25 to 8-bit two's complement binary.
A: 25 = 00011001. Flip: 11100110. Add 1: 11100111. So -25 = 11100111.
Q: Add the 8-bit two's complement representations of -30 and 50. What is the result in decimal?
A: -30 = 11100010. 50 = 00110010. Sum: 00010100 (carry out of MSB discarded). 00010100 = 20. Check: -30 + 50 = 20. Correct.
Q: What is the range of values that can be stored in a 16-bit two's complement integer?
A: -32,768 to 32,767 (that is, -2^15 to 2^15 - 1).
Q: You add two negative 8-bit two's complement numbers and get a result whose MSB is 0. Has overflow occurred?
A: Yes. Two negatives added together should produce a negative. A result with MSB = 0 indicates a positive number, which means the true result was too negative to fit in 8 bits.
Q: What is the decimal value of the 8-bit two's complement binary number 11111111?
A: Flip: 00000000. Add 1: 00000001. Magnitude = 1. So the value is -1. Alternatively, -128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = -1.
binary arithmetic, two's complement, ones complement, sign bit, MSB, LSB, signed integer, unsigned integer, bit flipping, binary addition, carry bit, overflow, sign extension, radix, base-2, negation, magnitude, 8-bit integer range, MIPS binary representation, converting decimal to binary, converting negative numbers to binary