Log Base 2 and Binary Logarithms

A common mistake is thinking the 'log' key on a calculator is the only logarithm you need. For computer science, log base 2 is the default. A binary logarithm answers: how many times must 2 be multiplied to reach a given number? log₂(8) = 3 because 2 × 2 × 2 = 8. In computing, this fits digital logic and binary storage. Unlike common log (base 10) or natural log (base e), log base 2 directly measures bits, algorithm steps, and information.

ISO 80000-2 defines lb(x) = log₂(x), lg(x) = log₁₀(x), and ln(x) = logₑ(x). But CLRS 'Introduction to Algorithms' uses lg to mean log₂. Always check the source's convention. log₂(x) is used to avoid ambiguity.

Most calculators lack a log₂ button. Use the change of base formula: log₂(x) = log₁₀(x) / log₁₀(2). On a TI-84 Plus CE, press MATH, select logBASE(, enter 2 and x. In Excel or Google Sheets, use =LOG(x, 2).

Worked Example: log₂(50)

log₂(32) = 5 and log₂(64) = 6, so log₂(50) is between 5 and 6. Using change of base: log₁₀(50) ≈ 1.69897, log₁₀(2) ≈ 0.30103. Divide: 1.69897 / 0.30103 ≈ 5.6439. So log₂(50) ≈ 5.64. This is the exponent: 2^5.64 ≈ 50.

Failure case: if your calculator gives a negative result for log of a number less than 1, check the argument is positive. The domain of log₂ is x > 0.

For common powers of 2, the log₂ result is an integer. This table helps estimate or check calculations:

• 2^0 = 1, log₂(1) = 0
• 2^1 = 2, log₂(2) = 1
• 2^2 = 4, log₂(4) = 2
• 2^3 = 8, log₂(8) = 3
• 2^4 = 16, log₂(16) = 4
• 2^5 = 32, log₂(32) = 5
• 2^6 = 64, log₂(64) = 6
• 2^7 = 128, log₂(128) = 7
• 2^8 = 256, log₂(256) = 8
• 2^9 = 512, log₂(512) = 9
• 2^10 = 1024, log₂(1024) = 10
• 2^11 = 2048, log₂(2048) = 11
• 2^12 = 4096, log₂(4096) = 12

To calculate binary logarithm of a number not in this table, use change of base or estimate by finding the nearest powers of 2.

The number of bits needed to store a positive integer n is ⌊log₂ n⌋ + 1. This directly measures binary logarithm. For n = 256, log₂(256) = 8, so ⌊8⌋ + 1 = 9 bits? Wrong: 2^8 = 256 exactly, so 256 needs 9 bits. The formula works for n > 0. For n = 255, log₂(255) ≈ 7.99, floor is 7, plus 1 = 8 bits. For n = 1000, log₂(1000) ≈ 9.97, floor is 9, plus 1 = 10 bits. That is the number of bits to store 1000 values.

Failure case: remember the formula for n that is a power of 2. 256 = 2^8, log₂(256) = 8, floor is 8, plus 1 = 9, and 256 needs 9 bits. The formula is ⌊log₂ n⌋ + 1, which for exact powers gives the correct number. The correct bit count for n values from 0 to 2^k - 1 is k bits. For n = 256, 0 to 255 is 8 bits. Use the formula with caution.

Binary search runs in O(log n) steps because it halves the search space each iteration. For 1024 items, log₂(1024) = 10 checks. For 4096 items, log₂(4096) = 12 checks. This is the binary logarithm. Balanced trees like AVL and red-black trees have height O(log n), meaning every operation takes that many steps.

Failure case: if the data structure is unbalanced, the height can reach O(n) instead of O(log n). For example, inserting sorted data into a plain binary search tree yields a linked list. Use self-balancing trees or B-trees for databases. B-tree of order 100 has height log₁₀₀(n) ≈ log₂(n) / log₂(100).

Information entropy uses log base 2 to measure bits. A fair coin flip gives 1 bit of information: log₂(2) = 1. A fair die gives log₂(6) ≈ 2.585 bits. This is the binary logarithm of the number of equally likely outcomes. In data compression, Huffman coding uses log₂ to assign optimal bit lengths to symbols based on probability.

Failure case: entropy uses log₂, not log₁₀ or ln. Using wrong base changes bit count by factor of ~3.3219. For 8 equally likely symbols, log₂(8) = 3 bits. Using log₁₀ gives log₁₀(8) ≈ 0.903, which is wrong.

ISO 80000-2 defines lb for log₂, lg for log₁₀, and ln for logₑ. But in computer science, CLRS and many papers use lg to mean log₂. This causes confusion. log₂ is used explicitly. When reading CS literature, check the conventions section or preface to see which base 'lg' uses. In ISO 80000-2, lg means log₁₀, but in CLRS, lg means log₂.

For example, CLRS writes lg(n) for log₂(n) throughout its analysis of binary search and balanced trees. The TI-84 Plus CE has logBASE( function for any base, and Excel has LOG(number, base) for any base. Use these to avoid notation errors.