Estimate log base 2 of 10 million to two decimal places without a calculator, and give the check that fixes the integer part.

Estimate log base 2 of 10 million to two decimal places without a calculator, and give the check that fixes the integer part.

Approach: Derive the log base 2 of ten from the relation between 2^10 and 10^3, then multiply through by the exponent and bracket the answer with two neighbouring powers of two.

23.25. Start from 2^10 = 1024, so log base 2 of 1000 is 10 - log2(1.024) = 10 - 0.0342 = 9.9658, and dividing by 3 gives log2(10) = 3.3219. Then log2(10^7) = 7 * 3.3219 = 23.253, which is 23.25 to two places. Neighbouring powers of two fix the integer part, since 2^23 = 8388608 and 2^24 = 16777216, so the answer sits between 23 and 24, and the ratio (10^7)/(2^23) is 1.192 with log2(1.192) = 0.25. The single number to hold is log2(10) = 3.32, which turns any power of ten into a bit count and settles most sizing questions about hash tables, sort depths and price levels in one multiplication.

Follow-up: How many bits are needed to index every one of 10 million records, and how much does that change if the count triples?

Key concepts: log base 2, powers of two, bit count.