Powers of 2 and logarithms; floor and ceiling

0 · Recall Warm-up

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

• In a trace table, what is in one row and what is in one column? from Lesson 0.1.2
• An int takes 4 bytes and starts at 3000. What is its address, and which bytes does it use? from Lesson 0.1.2
• What happens when the compiler finds a rule broken in your source code? from Lesson 0.1.1

1 · The Hook

🎣

A friend thinks of a number from 1 to 1000. You guess; she says “higher”, “lower” or “yes”. If you always guess the middle of what is left, how many guesses do you need in the worst case?

Each answer throws away about half of the remaining numbers. So the real question is: how many times can 1000 be halved before only one number is left? That count is a logarithm, and it appears again and again in later lessons, whenever work is cut in half. Halving and doubling are two sides of the same idea.

2 · Predict First

🤔

Start with 1,000,000. Halve it, dropping any fraction (1,000,000 → 500,000 → 250,000 → …). How many halvings until you reach 1? Guess before reading on. Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

19. Because 2^19^ = 524,288 ≤ 1,000,000 < 2^20^ = 1,048,576, you can halve 19 times. In symbols: ⌊log₂ 1,000,000⌋ = 19. A million shrinks to 1 in under 20 halvings.

Powers of 2

2^k^ (read “2 to the power k”) means 2 multiplied by itself k times. 2^0^ = 1 by agreement. From Lesson 0.1.2: n bits have 2^n^ patterns.

Memory sizes use these: 2^10^ = 1024 is called K (kilo), 2^20^ M (mega), 2^30^ G (giga). So 2^10^ ≈ one thousand, 2^20^ ≈ one million, 2^30^ ≈ one billion.

Rules of powers

• 2^a^ × 2^b^ = 2^a+b^ (e.g. 2^10^ × 2^6^ = 2^16^ = 65,536)
• 2^a^ / 2^b^ = 2^a−b^
• (2^a^)^b^ = 2^ab^
• 2^−k^ = 1 / 2^k^ (e.g. 2^−3^ = 1/8)

Logarithm base 2

log₂ x answers: “2 to which power gives x?”

log₂ 1024 = 10 because 2^10^ = 1024. log₂ 1 = 0. log₂ (1/8) = −3. The logarithm undoes the power: log₂(2^k^) = k and 2^log₂ n^ = n.

For numbers that are not powers of 2, the logarithm falls between two whole numbers: 512 < 1000 < 1024, so 9 < log₂ 1000 < 10 (it is about 9.97).

Rules of logarithms

• log(a × b) = log a + log b
• log(a / b) = log a − log b
• log(a^k^) = k · log a (so log₂ 32^3^ = 3 × 5 = 15)
• Change of base: logb x = log₂ x / log₂ b (so log₄ 64 = 6 / 2 = 3)

In data-structure questions “log n” almost always means log₂ n.

Floor and ceiling

The floor ⌊x⌋ is the largest whole number ≤ x (round down). The ceiling ⌈x⌉ is the smallest whole number ≥ x (round up).

Careful with negatives: rounding down −2.5 gives −3. For positive whole numbers a and b, ⌈a/b⌉ = ⌊(a + b − 1)/b⌋, a useful way to round a division up.

Halving and doubling counts

• Halving n (dropping fractions) until it reaches 1 takes ⌊log₂ n⌋ halvings.
• Doubling 1 until it reaches at least n takes ⌈log₂ n⌉ doublings.
• To give n different things different bit patterns you need ⌈log₂ n⌉ bits (26 letters need 5 bits, because 2^4^ = 16 < 26 ≤ 32 = 2^5^).
• The guessing game on 1…n needs at most ⌊log₂ n⌋ + 1 guesses: 10 for n = 1000 (checked by simulating every possible secret number).

4 · Visual

Halving 100 (drop fractions):

100 --> 50 --> 25 --> 12 --> 6 --> 3 --> 1
    1      2      3      4     5     6        6 halvings = floor(log2 100)

Doubling 1 up to 100:

1 --> 2 --> 4 --> 8 --> 16 --> 32 --> 64 --> 128
   1     2     3     4      5      6      7      7 doublings = ceil(log2 100)

Where 100 sits:   2^6 = 64  <=  100  <  128 = 2^7     so  6 < log2 100 < 7

Floor of the logarithm counts halvings; ceiling counts doublings.

Position k holds 2^k: each box doubles the one before it. log₂ of a value is just its position.

5 · Worked Examples

Example 1 Easy

Find log₂ 64, 2^10^ × 2^6^, and log₂ (1/8).

Solution

2^6^ = 64, so log₂ 64 = 6. 2^10^ × 2^6^ = 2^16^ = 65,536. 1/8 = 2^−3^, so log₂(1/8) = −3.

Example 2 Medium

Find ⌊log₂ 1000⌋ and ⌈log₂ 1000⌉. How many bits are needed to give each of 26 letters its own pattern?

Solution

2^9^ = 512 ≤ 1000 < 1024 = 2^10^, so ⌊log₂ 1000⌋ = 9 and ⌈log₂ 1000⌉ = 10. For 26 letters: 16 < 26 ≤ 32, so ⌈log₂ 26⌉ = 5 bits.

Example 3 GATE

In the higher/lower game on 1…1000, always guessing the middle number, what is the worst-case number of guesses? On 1…100?

Solution

After each wrong guess at most half of the remaining numbers are still possible. You can halve 1000 at most ⌊log₂ 1000⌋ = 9 times before one number is left, and that last number costs one more guess: 9 + 1 = 10. For 100: ⌊log₂ 100⌋ + 1 = 6 + 1 = 7. Both values were confirmed by playing the game for every possible secret number.

6 · GATE Traps

⚠️

• ⌊log₂ n⌋ and ⌈log₂ n⌉ differ by 1 unless n is a power of 2 (then both equal log₂ n).
• Floor of a negative number goes further from zero: ⌊−2.5⌋ = −3, not −2.
• log₂(a + b) is not log₂ a + log₂ b; only products split into sums.
• 2^10^ = 1024, not 1000: in memory sizes K means 1024.
• Number of bits to label n items is ⌈log₂ n⌉, not ⌊log₂ n⌋: 100 items need 7 bits, not 6.

8 · Memory Hook

🧠

“Log counts the halvings.” Picture a 1000-page phone book torn in half again and again: about 10 tears and one page is left. Floor = tears that leave at least one whole page; ceiling = the doublings you need to cover the whole book.

9 · Connect the Dots

Lesson 0.1.2 showed that each extra bit doubles the patterns; this lesson named that doubling (2^k^) and its reverse (log₂). Doubling also adds up quickly: 1 + 2 + 4 + 8 + … Next lesson answers: what do long sums like 1 + 2 + 3 + … + n and 1 + 2 + 4 + … come to, and how do we count arrangements and choices?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markFloor

What is ⌊log₂ 1500⌋?

Numerical answer: ________

Q2NAT1 markCeiling

What is ⌈log₂ 1500⌉?

Numerical answer: ________

Q3MCQ1 markLog rules

log₂ (32^3^) equals:

• (A) 96
• (B) 35
• (C) 15
• (D) 8

Q4MSQ2 marksFloor and ceiling

Which are true for every real number x?

• (A) ⌊−x⌋ = −⌊x⌋
• (B) ⌊x⌋ ≤ x ≤ ⌈x⌉
• (C) ⌊x⌋ = ⌈x⌉ exactly when x is a whole number
• (D) ⌈x⌉ − ⌊x⌋ is 0 or 1

Q5NAT2 marksBits needed

Each of 100 students gets a different ID made of bits. What is the smallest number of bits that works?

Numerical answer: ________

11 · Rule Card

• 2^10^ = 1024 (K), 2^20^ ≈ 10^6^ (M), 2^30^ ≈ 10^9^ (G).
• 2^a^·2^b^ = 2^a+b^; 2^a^/2^b^ = 2^a−b^; (2^a^)^b^ = 2^ab^.
• log₂ x = the power of 2 that gives x; log₂ 1 = 0.
• log(ab) = log a + log b; log(a^k^) = k log a; logb x = log₂ x / log₂ b.
• ⌊x⌋ round down, ⌈x⌉ round up; ⌈a/b⌉ = ⌊(a + b − 1)/b⌋ for positive whole a, b.
• Halvings from n to 1 = ⌊log₂ n⌋; doublings from 1 to ≥ n = ⌈log₂ n⌉; bits for n labels = ⌈log₂ n⌉.

12 · Concept Ledger

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

power of 2 (2^k)K, M, Glogarithm log₂change of basefloor ⌊x⌋ceiling ⌈x⌉halving countdoubling count

13 · Answer Vault