Computer Science › Section B · Data storage › Topic B.1
Bits, gates, and flip-flops
Everything a computer holds, from a photo to a program, comes down to millions of switches that are either on or off. This topic shows how those two-state values are combined by logic gates, how a circuit can remember a single bit, and how people write long bit patterns compactly.
Bits are symbols
A modern computer stores everything as strings of two-valued digits called bits, short for binary digits, written 0 and 1. Bits are not really numbers; they are symbols, and a pattern's meaning depends on how it is used. The same eight bits might be a number, a letter, part of a colour or a sliver of sound. Physically, a bit is usually a voltage level, low for 0 and higher for 1. Two states are easy to tell apart reliably, even when electrical noise blurs the signal.
Boolean operations
To see how bits are manipulated, read 1 as true and 0 as false. Operations on true and false values are called Boolean operations, after the 19th-century mathematician George Boole. AND outputs 1 only when both inputs are 1, like a statement "P and Q" that is true only if both parts are true. OR outputs 1 when at least one input is 1. XOR, exclusive or, outputs 1 when its inputs differ: one or the other, but not both. NOT, also called an inverter, has a single input and outputs its opposite. Adding NOT after AND gives NAND, and after OR gives NOR.
Truth tables
A truth table lists every combination of inputs with the output for each, so it defines an operation completely. Two inputs give four rows: 00, 01, 10 and 11. For AND the outputs are 0, 0, 0, 1. For OR they are 0, 1, 1, 1. For XOR they are 0, 1, 1, 0. For NAND they are 1, 1, 1, 0, and for NOR they are 1, 0, 0, 0. With three inputs there are \(2^3 = 8\) rows, and in general \(n\) inputs give \(2^n\) rows, because each input doubles the number of combinations.
Gates: Boolean operations in hardware
A gate, or logic gate, is a small device that computes a Boolean operation on its inputs. Gates have been built from gears, relays and even light, but in modern computers they are made from transistors acting as tiny electronic switches. In 1937 Claude Shannon showed in his master's thesis that Boolean algebra could describe circuits of switches, linking logic to electrical engineering. NAND is especially useful: every Boolean operation can be built from NAND gates alone. For example, feeding the same signal into both inputs of a NAND gate gives NOT. NOR gates are universal in the same way.
Worked example: a half adder
Gates can do arithmetic. Adding two single bits A and B gives a sum bit and a carry bit. 1. List the cases: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1 and 1 + 1 = 2, which is 10 in binary (carry 1, sum 0). 2. Read off the sum column: 0, 1, 1, 0. That is exactly XOR. 3. Read off the carry column: 0, 0, 0, 1. That is exactly AND. 4. So one XOR gate and one AND gate add two bits: a half adder. 5. Check A = 1, B = 1: sum 1 XOR 1 = 0, carry 1 AND 1 = 1, the pattern 10, which is two. Extended with an input for an incoming carry and chained, such circuits add long numbers.
A circuit that remembers
A plain gate's output depends only on its present inputs, making it a combinational circuit; circuits with stored state are sequential. To store data, a circuit needs feedback: an output wired back into an input. A flip-flop is a circuit whose output stays at 0 or 1 until a brief pulse on one of its inputs switches it. One common design, the set-reset latch, uses two NOR gates, each feeding its output into one input of the other. The output Q holds its value while both control inputs, S (set) and R (reset), are 0. A pulse on S forces Q to 1, and a pulse on R forces it to 0. (Engineers often reserve flip-flop for clock-controlled versions and call this simple form a latch.) Different wirings behave identically from outside, so designers use a flip-flop as an abstract tool; a processor's registers are built from them.
Worked example: setting the latch
In the NOR latch, Q = NOR(R, Q̄) and Q̄ = NOR(S, Q), where Q̄ is the opposite output. Start with Q = 0, Q̄ = 1, S = 0 and R = 0. 1. Check that this is stable: Q = NOR(0, 1) = 0 and Q̄ = NOR(0, 0) = 1, so nothing changes. 2. Pulse S to 1: Q̄ = NOR(1, 0) = 0. 3. Now Q = NOR(0, 0) = 1. 4. Update Q̄ with the new Q: NOR(1, 1) = 0, unchanged. 5. Return S to 0: Q̄ = NOR(0, 1) = 0 and Q = NOR(0, 0) = 1. The latch now holds 1 even though the pulse has ended, so it has stored one bit. A pulse on R would reset it to 0 in the same way.
Hexadecimal notation
Long bit strings are hard to read and easy to miscopy, so people use hexadecimal, base 16, as shorthand. Each hex digit stands for exactly four bits: 0000 to 1001 are 0 to 9, then 1010 is A, 1011 B, 1100 C, 1101 D, 1110 E and 1111 F. To convert, split the bits into fours from the right and replace each group by its digit. Programmers often write the prefix 0x to mark a hex value, so 10110010 becomes 0xB2. Going the other way, expand each hex digit into its four bits: 0xA7 is 1010 0111.
Worked example: converting with hex
1. Write the 16-bit pattern 1101011000111010 in hex. Group it in fours: 1101 0110 0011 1010. Replace each group: 1101 is D, 0110 is 6, 0011 is 3, 1010 is A. The result is 0xD63A. 2. Expand 0x7F2 into bits. 7 is 0111, F is 1111 and 2 is 0010, giving 0111 1111 0010, a 12-bit pattern. 3. Check the lengths: 16 bits gave 4 hex digits and 3 hex digits gave 12 bits, four bits per digit both times. If a pattern's length is not a multiple of four, pad it with 0s on the left before grouping: 111100 becomes 0011 1100, which is 0x3C.
Common mistakes to avoid
First, confusing OR with XOR: OR gives 1 when both inputs are 1, XOR gives 0. Second, assuming a bit pattern has one fixed meaning. Third, grouping bits for hex from the left when the length is not a multiple of four; group from the right, or pad on the left. Fourth, treating A to F as letters rather than the digit values 10 to 15. Fifth, thinking a gate on its own stores anything; storage needs feedback, as in a flip-flop.
Key takeaways
A bit is a two-state symbol whose meaning depends on interpretation. AND, OR, XOR and NOT are the basic Boolean operations, NAND and NOR add a NOT, and truth tables with \(2^n\) rows define them. Gates built from transistors carry out these operations; NAND alone can build any of them. A half adder is an XOR gate for the sum and an AND gate for the carry. A flip-flop uses feedback to hold one bit until it is set or reset. Hexadecimal writes each group of four bits as one digit, 0 to F.
Flashcards
Flashcard
A binary digit, 0 or 1
Test your understanding
Question 1 of 5
An XOR gate receives the inputs 1 and 1. What does it output, and how would an OR gate differ?
Question 2 of 5
What is the bit pattern 1011010011100001 in hexadecimal?
Question 3 of 5
In a half adder, which gates produce the sum bit and the carry bit?
Question 4 of 5
What allows a flip-flop to keep its value after the input pulse has ended?
Question 5 of 5
How many rows does a complete truth table for a circuit with four inputs have?
