Binary and hex, powers of two, size units, log₂: n bits name 2ⁿ things

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• CPU time formula? from Lesson 0.1.2
• 40% of the time is sped up 2×. Overall speedup? from Lesson 0.1.2
• What does the stored-program concept say? from Lesson 0.1.1

1 · The Hook

🎣

"A 32 KB cache with 64-byte blocks and 32-bit addresses: how many tag bits?" That GATE question looks scary, but the answer is three subtractions of exponents. Once you think of every size as a power of two, most COA arithmetic happens in your head. This lesson builds that habit.

2 · Predict First

🤔

A memory has 64 KB, and every byte has its own address. How many bits must an address have?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

64 KB = 2⁶ × 2¹⁰ = 2¹⁶ bytes. Each byte needs a different address, and 16 bits give exactly 2¹⁶ different patterns, so 16 bits.

Binary and hexadecimal

A bit is 0 or 1. In binary, each position is worth a power of 2: 1011₂ = 8 + 0 + 2 + 1 = 11.

Hexadecimal (base 16) uses digits 0–9, A–F (A = 10 … F = 15). One hex digit = exactly 4 bits, so convert by grouping bits in fours from the right:

• 0x3A7 = 0011 1010 0111₂
• 1101 0110₂ = 0xD6

Prefix 0x (or suffix H) marks hex.

Powers of two to know by heart

Size units (memory sizes are binary)

• 1 K = 2¹⁰ = 1,024; 1 M = 2²⁰; 1 G = 2³⁰; 1 T = 2⁴⁰.
• So 2³⁵ = 2⁵ × 2³⁰ = 32 G, and 512 M = 2⁹ × 2²⁰ = 2²⁹.
• B = byte = 8 bits; b = bit. 1 KB = 2¹⁰ bytes = 2¹³ bits.

n bits name 2ⁿ things

With n bits you can write 2ⁿ different patterns. So:

• A memory with 2ⁿ addressable locations needs an n-bit address.
• To give each of N things its own code you need ⌈log₂ N⌉ bits (round up). 6 registers need ⌈log₂ 6⌉ = 3 bits; 64 registers need 6 bits.

log₂ x is the power you raise 2 to in order to get x: log₂ 1024 = 10. For a power of two, just read the exponent.

Dividing powers of two

2ᵃ / 2ᵇ = 2ᵃ⁻ᵇ. Example: how many 64-byte blocks are in a 32 KB cache? 2¹⁵ / 2⁶ = 2⁹ = 512. You will do this in every cache lesson.

4 · Visual

Converting sizes to exponents (write everything as 2^n first)

  64 KB  = 2^6  * 2^10 = 2^16 bytes   -> 16 address bits
   4 GB  = 2^2  * 2^30 = 2^32 bytes   -> 32 address bits
 256 MB  = 2^8  * 2^20 = 2^28 bytes   -> 28 address bits

hex <-> binary: one hex digit = 4 bits
  0x  3    A    7
     0011 1010 0111

5 · Worked Examples

Example 1 Easy

Convert 0xB4 to binary and to decimal.

Solution

B = 1011, 4 = 0100 → 1011 0100₂ = 128 + 32 + 16 + 4 = 180.

Example 2 Medium

A byte-addressable memory has 256 MB. How many address bits?

Solution

256 MB = 2⁸ × 2²⁰ = 2²⁸ → 28 bits.

Example 3 GATE

A 4 GB memory is divided into pages of 4 KB. How many pages, and how many bits identify a page?

Solution

2³² / 2¹² = 2²⁰ pages (about a million); identifying one needs 20 bits.

6 · GATE Traps

⚠️

• 1 KB here is 1,024 bytes, not 1,000 (memory sizes are binary).
• Bytes vs bits: a "4 Kb" chip holds 4,096 bits, only 512 bytes.
• ⌈log₂ N⌉ rounds up: 5 things need 3 bits, not 2.
• One hex digit is 4 bits; one byte is 2 hex digits.

7 · Memory Hook

🧠

"Write it as 2-to-the-something first." Then multiplying is adding exponents and dividing is subtracting them.

8 · Connect the Dots

You can now turn any size into an exponent and any count into a number of bits. Next lesson: how negative numbers are stored (two's complement), and how to pull fields out of a word, which instructions do constantly.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markAddress bits

A byte-addressable memory holds 2 MB. How many address bits are needed?

Numerical answer: ________

Q2NAT1 markBits for N items

A processor has 40 registers. How many bits does a register number need?

Numerical answer: ________

Q3MCQ1 markHex

0x2F in binary is:

• (A) 0010 1111
• (B) 1111 0010
• (C) 0011 1111
• (D) 0010 0111

Q4NAT2 marksDividing powers

A 16 KB cache is split into blocks of 32 bytes. How many blocks does it hold?

Numerical answer: ________

Q5NAT1 markUnits

How many bits are in 2 KB?

Numerical answer: ________

10 · Rule Card

• One hex digit = 4 bits. 1 K = 2¹⁰, 1 M = 2²⁰, 1 G = 2³⁰.
• 2ⁿ locations ↔ n address bits. N items need ⌈log₂ N⌉ bits.
• 2ᵃ / 2ᵇ = 2ᵃ⁻ᵇ: convert sizes to exponents before dividing.
• B = byte (8 bits), b = bit.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

bitbinaryhexadecimalpowers of twoK/M/G (binary)byte vs bitn bits give 2ⁿ patternslog₂ and ⌈log₂ N⌉dividing powers of two

12 · Answer Vault