5 Basics of Computers · 5.1 Computer basics: number systems, codes, logic, algorithms and spreadsheets
5.1.5 Binary arithmetic and complements; logic gates and logical operations
The ALU does arithmetic on binary numbers (adding, and subtracting by adding the 2's complement) and logical operations (AND, OR, NOT, XOR) bit by bit; these are built from logic gates, and NAND or NOR alone can build every other gate.
- APPSC Paper I
- Advanced level
- 8 min read
- Free
Core facts
- Binary addition: 0 + 0 = 0; 0 + 1 = 1; 1 + 1 = 10 (0, carry 1); 1 + 1 + 1 = 11 (1, carry 1).
- Binary subtraction: 0 − 0 = 0; 1 − 0 = 1; 1 − 1 = 0; 0 − 1 = 1, borrow 1.
- Multiplication: 0 × 0 = 0 × 1 = 0, 1 × 1 = 1 (shift and add). Division: repeated shift and subtract.
- 1's complement: flip every bit (0 ↔ 1). 2's complement = 1's complement + 1.
- Decimal analogues: 9's complement (each digit from 9) and 10's complement (9's + 1).
- Computers subtract by adding the 2's complement of the number to be subtracted.
- n-bit 2's complement range: −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1; 8 bits: −128 to +127. The MSB is the sign bit (0 = +, 1 = −).
- Basic gates: AND, OR, NOT. Universal gates: NAND, NOR. Others: XOR, XNOR.
| Gate | Expression | Output is 1 when |
|---|---|---|
| AND | A·B | all inputs are 1 |
| OR | A + B | at least one input is 1 |
| NOT | A′ | input is 0 |
| NAND | (A·B)′ | not all inputs are 1 |
| NOR | (A + B)′ | all inputs are 0 |
| XOR | A ⊕ B | inputs differ |
| XNOR | (A ⊕ B)′ | inputs are equal |
- Truth table for n inputs has 2ⁿ rows.
- De Morgan: (A + B)′ = A′·B′ and (A·B)′ = A′ + B′.
Example 1. Add 10110₂ and 01101₂. Solution. 22 + 13 = 35. Column by column with carries gives 100011. Answer: 100011₂
Explained
1. The four operations.
Example 2. Find 10110₂ − 01101₂. Solution. 22 − 13 = 9. Answer: 1001₂
Example 3. Multiply 1011₂ by 101₂. Solution. 1011 × 1 = 1011; next bit 0 → 00000; next bit 1 → 101100. Sum 1011 + 101100 = 110111. Check: 11 × 5 = 55. Answer: 110111₂
Example 4. Divide 110110₂ by 110₂. Solution. 54 ÷ 6 = 9. Answer: 1001₂
2. Complements.
Example 5. Find the 1's and 2's complements of 01011010. Solution. Flip: 10100101. Add 1: 10100110. Answer: 10100101 and 10100110 Shortcut for the 2's complement: copy bits from the right up to and including the first 1, then flip the rest.
Example 6. Write −25 in 8-bit 2's complement. (a) 10011001 (b) 11100110 (c) 11100111 (d) 00011001 Solution. +25 = 00011001; flip → 11100110; + 1 → 11100111. Answer: (c) ((a) is sign-magnitude, (b) is 1's complement)
3. Subtraction by complements (4 bits).
Example 7. 9 − 5 using 2's complement. Solution. 5 = 0101 → 2's complement 1011. 1001 + 1011 = 1 0100. A carry out means the result is positive: discard it. Answer: 0100 = +4
Example 8. 5 − 9 using 2's complement. Solution. 9 = 1001 → 2's complement 0111. 0101 + 0111 = 1100, no carry, so the answer is negative: take the 2's complement of 1100 = 0100. Answer: −4
Example 9. 9 − 5 using 1's complement. Solution. 1's complement of 0101 = 1010. 1001 + 1010 = 1 0011. Add the carry back (end-around carry): 0011 + 1 = 0100. Answer: +4
Example 10. 8754 − 4567 using 10's complement. Solution. 10's complement of 4567 = 5433. 8754 + 5433 = 14187; drop the carry 1. Answer: 4187
4. Logical (bitwise) operations. The ALU applies a gate to each pair of bits.
With A = 1100 and B = 1010:
| Operation | Result |
|---|---|
| A AND B | 1000 |
| A OR B | 1110 |
| A XOR B | 0110 |
| NOT A | 0011 |
Uses: AND clears chosen bits (masking), OR sets bits, XOR toggles bits; A XOR A = 0. Spreadsheets use the same logic in the functions AND(), OR() and NOT(), which return TRUE or FALSE.
5. Universal gates. Each gate can be built from NAND gates only (or NOR gates only):
| Gate wanted | NAND gates | NOR gates |
|---|---|---|
| NOT | 1 | 1 |
| AND | 2 | 3 |
| OR | 3 | 2 |
| XOR | 4 | 5 |
Deeper
- Signed representations of −5 in 8 bits: sign-magnitude 10000101, 1's complement 11111010, 2's complement 11111011. Sign-magnitude and 1's complement have two zeros (+0 and −0) and range −127 to +127; 2's complement has one zero and range −128 to +127, which is why computers use it.
- Overflow: happens when adding two numbers of the same sign gives a result of the opposite sign. In 8 bits, 100 + 50 = 150 > 127 gives 10010110, which reads as −106. Adding numbers of opposite signs never overflows.
- Boolean laws:
- Identity A + 0 = A, A·1 = A; null A + 1 = 1, A·0 = 0.
- Idempotent A + A = A, A·A = A; complement A + A′ = 1, A·A′ = 0; involution (A′)′ = A.
- Absorption A + AB = A, A(A + B) = A; also A + A′B = A + B.
- Distributive A + BC = (A + B)(A + C) holds in Boolean algebra (not in ordinary algebra).
- Duality: swap + with · and 0 with 1 to get another valid law.
- Adders: a half adder adds 2 bits: sum = A ⊕ B, carry = A·B. A full adder adds 3 bits (with carry in C): sum = A ⊕ B ⊕ C, carry = AB + BC + CA. A half subtractor gives difference A ⊕ B and borrow A′B.
- Multi-input XOR gives 1 when the number of 1 inputs is odd (this is how a parity bit is generated).
- Shifts: shifting left by one place multiplies by 2; shifting right divides by 2 (unsigned whole numbers).
- Number of Boolean functions of n variables = 2^(2ⁿ); for 2 variables, 16.
Example 11. Simplify AB + AB′. Solution. A(B + B′) = A·1. Answer: A
Example 12. Which gate gives output 1 only when both inputs are 0? (a) NAND (b) NOR (c) XOR (d) XNOR Solution. NOR is 1 only for 0, 0. XNOR is also 1 for 1, 1. Answer: (b) NOR
Example 13. Add 3A₁₆ + 2F₁₆ and 57₈ + 26₈. Solution. Hex: A + F = 10 + 15 = 25 = 16 + 9 → write 9, carry 1; 3 + 2 + 1 = 6 → 69₁₆ (58 + 47 = 105). Octal: 7 + 6 = 13 = 8 + 5 → write 5, carry 1; 5 + 2 + 1 = 8 = 10₈ → 105₈ (47 + 22 = 69). Answer: 69₁₆ and 105₈
Common traps
- ✗ "1 + 1 = 2 in binary." ✓ 1 + 1 = 10 (write 0, carry 1).
- ✗ "2's complement = flip the bits." ✓ That is the 1's complement; 2's complement adds 1.
- ✗ "In 2's complement subtraction, add the end carry back." ✓ Discard it; end-around carry is for 1's complement.
- ✗ "No carry means the answer is positive." ✓ No carry means the result is negative, in complement form.
- ✗ "8-bit signed range is −127 to +128." ✓ −128 to +127.
- ✗ "AND, OR and NOT are the universal gates." ✓ The universal gates are NAND and NOR.
- ✗ "XOR is 1 when both inputs are 1." ✓ XOR is 1 when inputs differ; for 1, 1 it is 0.
- ✗ "(A + B)′ = A′ + B′." ✓ De Morgan: (A + B)′ = A′·B′.
Quick revision
- 1 + 1 = 10; 1 + 1 + 1 = 11; 0 − 1 = 1 borrow 1.
- 1's complement: flip; 2's complement: flip + 1.
- 2's complement subtraction: carry → discard, positive; no carry → negative, re-complement.
- 1's complement: end-around carry.
- 8-bit signed: −128 to +127; −25 = 11100111.
- Overflow: same-sign inputs, opposite-sign result.
- Universal gates NAND, NOR; XOR = 4 NANDs.
- De Morgan: (A + B)′ = A′B′; (AB)′ = A′ + B′.
- Half adder: sum A ⊕ B, carry AB.
- Truth table: 2ⁿ rows.
Practise this topic. Questions on Arithmetic & logic operations, algorithms & flowcharts, with answers explained.
All Computer basics: number systems, codes, logic, algorithms and spreadsheets notes · APPSC Paper I syllabus · APPSC Paper I Mock 1 with answers · Start free
Medha AI writes its own notes and checks them against the sources listed. Medha AI is an independent preparation service. It is not affiliated with, endorsed by or connected to APPSC, TSPSC, MPSC, UPSC or any other commission or government body.