Problem

Given a positive integer n, compute floor(log2(n)) (the exponent of the highest power of two not exceeding n) without using a language built-in log2 function.

Examples

Example 1

1
2

Input: n = 32
Output: 5  # because 2^5 = 32

Example 2

1
2

Input: n = 64
Output: 6  # because 2^6 = 64

Example 3

1
2

Input: n = 20
Output: 4  # because 2^4 = 16 <= 20 < 32
Similar Problems

Solution

Method 1 — Repeated division (or right shift)

Intuition

floor(log2(n)) is the number of times we can divide n by 2 (or shift right) before it becomes less than 1. Each division by 2 reduces the exponent by 1.

Approach

  1. If n <= 0 the problem is undefined for non-positive integers (handle as error or return -INF depending on your API).
  2. Initialize ans = 0.
  3. While n > 1:
    • n = n / 2 (or n >>= 1 for integer types)
    • ans++
  4. Return ans.

Edge cases:

  • n == 1 -> floor(log2(1)) = 0.
  • Large values should fit in the integer types you choose; use 64-bit if needed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
 public:
  int floorLog2(int n) {
    if (n <= 0) return -1;  // undefined for non-positive input
    int ans = 0;
    while (n > 1) {
      n >>= 1;
      ++ans;
    }
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

package main

func floorLog2(n int) int {
  if n <= 0 {
    return -1 // undefined for non-positive
  }
  ans := 0
  for n > 1 {
    n >>= 1
    ans++
  }
  return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
  public int floorLog2(int n) {
    if (n <= 0) return -1; // undefined
    int ans = 0;
    while (n > 1) {
      n >>= 1;
      ans++;
    }
    return ans;
  }
}
1
2
3
4
5
6
7
8
9

class Solution:
  def floorLog2(self, n: int) -> int:
    if n <= 0:
      return -1
    ans = 0
    while n > 1:
      n >>= 1
      ans += 1
    return ans

Complexity

  • ⏰ Time complexity: O(log n) because we divide/shift n until it becomes 1 (about log2(n) iterations).
  • 🧺 Space complexity: O(1) extra space.

Method 2 — Find highest set bit using exponential + binary search (faster for extremely large ranges)

Intuition

If you repeatedly double a power-of-two value until it exceeds n, you can locate a bracket [2^k, 2^{k+1}) containing n. A small binary search between those exponents finds k = floor(log2(n)) in O(log k) steps. This is useful when bit-length operations are not available but you want fewer comparisons than repeated division in some contexts.

Approach

  1. If n <= 0 return error indicator.
  2. Start with p = 1, k = 0.
  3. While p << 1 <= n: p <<= 1, k++.
  4. Return k.

(This is effectively the same as Method 1 implemented with a power-of-two variable; it runs in O(log n) but uses a different loop variable.)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
 public:
  int floorLog2(int n) {
    if (n <= 0) return -1;
    int p = 1;
    int k = 0;
    while ((p << 1) <= n) {
      p <<= 1;
      ++k;
    }
    return k;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

package main

func floorLog2(n int) int {
  if n <= 0 { return -1 }
  p := 1
  k := 0
  for (p << 1) <= n {
    p <<= 1
    k++
  }
  return k
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
  public int floorLog2(int n) {
    if (n <= 0) return -1;
    int p = 1;
    int k = 0;
    while ((p << 1) <= n) {
      p <<= 1;
      k++;
    }
    return k;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
  def floorLog2(self, n: int) -> int:
    if n <= 0:
      return -1
    p = 1
    k = 0
    while (p << 1) <= n:
      p <<= 1
      k += 1
    return k

Complexity

  • ⏰ Time complexity: O(log n) iterations in the worst case.
  • 🧺 Space complexity: O(1) extra space.