Number systems and logic gates: Class 11 Computer Science Notes, Short Questions and Numericals

Decimal, binary, octal and hexadecimal systems, conversions, binary arithmetic, signed numbers with two's complement, character codes, Boolean algebra, logic gates, truth tables and simple logic circuits.

Key points

A number system uses a fixed set of digits and a base (radix). The value of a digit depends on its position, so each place has a weight equal to the base raised to the place number. In 345 the weights are 10², 10¹ and 10⁰, giving 3×100 + 4×10 + 5×1.

The four systems used in computing are:

Decimal, base 10, digits 0 to 9. Used by people.
Binary, base 2, digits 0 and 1. Used inside computers because a circuit has two easy states, off and on.
Octal, base 8, digits 0 to 7. One octal digit stands for three bits.
Hexadecimal, base 16, digits 0 to 9 and A to F (A is 10, F is 15). One hex digit stands for four bits.

To convert binary to decimal, write the weight of each place (1, 2, 4, 8, 16 and so on from the right) and add the weights where the bit is 1. Example: 101101₂ = 32 + 8 + 4 + 1 = 45.

To convert decimal to binary, divide the number by 2 again and again and note each remainder. Read the remainders from the last one to the first. For 45: 45÷2 = 22 r 1, 22÷2 = 11 r 0, 11÷2 = 5 r 1, 5÷2 = 2 r 1, 2÷2 = 1 r 0, 1÷2 = 0 r 1. Reading upward gives 101101. The same method with 8 or 16 gives octal or hex.

To convert between binary and hex, group the bits in fours from the right. 10110111 splits into 1011 and 0111, which are B and 7, so the hex value is B7. For octal, group in threes. To go back, replace each hex or octal digit by its 4-bit or 3-bit group.

Binary arithmetic follows these rules:

0+0 = 0, 0+1 = 1, 1+0 = 1, 1+1 = 10 (write 0, carry 1), 1+1+1 = 11 (write 1, carry 1).
Subtraction: 0−0 = 0, 1−0 = 1, 1−1 = 0, and 0−1 needs a borrow from the next left bit.
Example: 1011 + 0110 = 10001, which is 11 + 6 = 17.

Computers store negative numbers in two's complement. To find the two's complement of a number, invert every bit and then add 1. In this form the leftmost bit is the sign bit: 0 means positive and 1 means negative. Subtraction becomes addition of the two's complement, so the processor needs no separate subtractor.

A bit is one binary digit. A byte is 8 bits. A nibble is 4 bits. Larger units are the kilobyte (1,024 bytes), megabyte, gigabyte and terabyte, each 1,024 times the one before in the binary convention. With n bits there are 2ⁿ different patterns.

Characters are stored as numbers by a coding scheme. ASCII uses 7 bits (128 characters), and the letter A is 65 and a is 97. Extended ASCII uses 8 bits (256 characters). Unicode gives a code to characters of almost all world languages, including Urdu, and is written in forms such as UTF-8.

Boolean algebra works on two values, true (1) and false (0). The basic gates are:

AND: output is 1 only when all inputs are 1. Written A·B.
OR: output is 1 when at least one input is 1. Written A+B.
NOT: output is the opposite of the input. Written A̅ or A'.
NAND: AND followed by NOT. Output is 0 only when all inputs are 1.
NOR: OR followed by NOT. Output is 1 only when all inputs are 0.
XOR: output is 1 when the inputs are different.
XNOR: output is 1 when the inputs are the same.

A truth table lists every input combination and the output. A circuit with n inputs has 2ⁿ rows, so two inputs give four rows. NAND and NOR are called universal gates because any other gate can be built from NAND gates alone or from NOR gates alone.

Useful Boolean laws:

Identity: A+0 = A and A·1 = A. Null: A+1 = 1 and A·0 = 0.
Complement: A+A' = 1 and A·A' = 0. Double negation: (A')' = A.
Commutative, associative and distributive laws hold as in ordinary algebra, with A+(B·C) = (A+B)·(A+C) also true.
De Morgan's laws: (A·B)' = A'+B' and (A+B)' = A'·B'.

To draw a circuit from an expression, build one gate for each operator. For F = A·B + C, an AND gate takes A and B, and its output goes with C into an OR gate. To find a truth table from a circuit, work gate by gate across each row.

Study tip: Practise conversions until they are quick, and always check by converting back. In truth table questions write all 2ⁿ rows in counting order and fill intermediate columns for each gate. Draw gate symbols neatly and label inputs and outputs.

Definitions and flashcards

Say the meaning first, then open the card to check.

Radix

The base of a number system, the count of distinct digits it uses.

Bit

A single binary digit, 0 or 1.

Byte

A group of 8 bits.

Two's complement

A way to store signed numbers: invert the bits and add 1.

ASCII

A 7-bit code that gives a number to each English letter, digit and symbol.

Truth table

A table showing the output of a logic circuit for every input combination.

Universal gate

A gate, NAND or NOR, from which every other gate can be built.

De Morgan's laws

Rules that change an AND into an OR, or the reverse, when a complement is taken.

Sign bit

The leftmost bit of a signed number: 0 for positive, 1 for negative.

Formula sheet

Name	Formula	What it means
Number of patterns	2ⁿ	Different values that n bits can hold
Unsigned range	0 to 2ⁿ − 1	Smallest and largest value in n bits, no sign
Signed range (two's complement)	−2ⁿ⁻¹ to 2ⁿ⁻¹ − 1	Range of n-bit signed numbers
De Morgan 1	(A·B)' = A' + B'	Complement of AND is OR of complements
De Morgan 2	(A+B)' = A'·B'	Complement of OR is AND of complements

Short questions with model answers

These are the kind of questions asked for 2, 3 and 5 marks. Try each one before opening the answer.

Why do computers use the binary system? (2 marks)

A digital circuit has two stable states, such as low and high voltage or off and on. These match the two binary digits 0 and 1. Two states are easy to build, cheap and less affected by noise than many voltage levels.

What is a universal gate? Name two. (2 marks)

A universal gate is a gate that can be used alone to build every other gate. NAND and NOR are universal gates. For example, joining both inputs of a NAND gate together gives a NOT gate.

State De Morgan's laws. (3 marks)

First law: the complement of a product equals the sum of the complements, (A·B)' = A' + B'. Second law: the complement of a sum equals the product of the complements, (A+B)' = A'·B'. They are used to simplify expressions and to change a circuit from AND-OR form to NAND or NOR form.

Explain how a negative number is stored using two's complement. (3 marks)

First write the positive value in binary using the fixed number of bits. Invert every bit, changing 0 to 1 and 1 to 0. Add 1 to the result. The leftmost bit then becomes 1, showing that the number is negative. For −5 in 8 bits: 5 is 00000101, inverted is 11111010, plus 1 gives 11111011. Addition of this pattern works like subtraction.

Describe the AND, OR and NOT gates with their truth tables. (5 marks)

AND gives 1 only when both inputs are 1: 00→0, 01→0, 10→0, 11→1. OR gives 1 if any input is 1: 00→0, 01→1, 10→1, 11→1. NOT has one input and reverses it: 0→1 and 1→0. Their symbols are a D-shaped gate for AND, a curved-back gate for OR, and a triangle with a small circle for NOT. Each has a Boolean expression: A·B, A+B and A'.

Convert hexadecimal 2F to binary and decimal. (3 marks)

Write each hex digit as four bits: 2 is 0010 and F is 1111, so 2F is 00101111. In decimal, 2×16 + 15×1 = 32 + 15 = 47.

Numericals with worked steps

Convert decimal 45 to binary.

45 ÷ 2 = 22 remainder 1
22 ÷ 2 = 11 remainder 0
11 ÷ 2 = 5 remainder 1
5 ÷ 2 = 2 remainder 1
2 ÷ 2 = 1 remainder 0
1 ÷ 2 = 0 remainder 1
Read the remainders from the bottom up: 101101
Check: 32 + 8 + 4 + 1 = 45

Answer: 45₁₀ = 101101₂

Convert binary 10110111 to hexadecimal.

Split into groups of four from the right: 1011 and 0111
1011 = 8 + 2 + 1 = 11 = B
0111 = 4 + 2 + 1 = 7

Answer: B7₁₆

Find the 8-bit two's complement representation of −18.

18 in 8 bits is 00010010
Invert all bits: 11101101
Add 1: 11101101 + 1 = 11101110
Check: 11101110 as unsigned is 238, and 256 − 238 = 18

Answer: −18 is 11101110

Add the binary numbers 1011 and 0110.

Bit 0: 1+0 = 1, carry 0
Bit 1: 1+1 = 10, write 0, carry 1
Bit 2: 0+1+1 = 10, write 0, carry 1
Bit 3: 1+0+1 = 10, write 0, carry 1
Final carry gives a fifth bit 1
Result 10001; check 11 + 6 = 17 = 16 + 1

Answer: 10001₂ (17 in decimal)

Common mistakes

Reading the remainders from top to bottom when converting decimal to binary. They must be read from the last to the first.
Forgetting that 1+1 = 10 in binary, not 2.
Adding 1 before inverting when finding two's complement. First invert, then add 1.
Grouping bits from the left instead of the right when converting to hex or octal, which gives the wrong digits.
Mixing up NAND with NOT AND, and XOR with OR. XOR gives 0 when both inputs are 1.

Practise this chapter

Practice questions and timed test Printable worksheet