Problem

Find the position of the most-significant set bit (MSB) in the binary representation of a non-negative integer n.

Positions are zero-based from the least-significant bit (LSB). For example:

  • n = 4 (0b100) → MSB position = 2.
  • n = 99 (0b1100011) → MSB position = 6.

Examples

Example 1

1
2

Input: n = 4
Output: 2

Example 2

1
2

Input: n = 99
Output: 6

Solution

Below are three approaches: naive scan, binary-search-like mask, and using builtins for leading-zero / bit-length.

Method 1 — Right-shift scan (naive)

Intuition

Shift n right until it becomes 0. The number of shifts performed is the MSB position.

Approach

  • If n == 0 return -1 (no set bits) or a sentinel as required.
  • Initialize pos = 0.
  • While (n >>= 1) != 0: increment pos.
  • Return pos.

Code

1
2
3
4
5
6
7
8
9

class Solution {
 public:
  int msb_pos(unsigned int n) {
    if (n == 0) return -1;
    int pos = 0;
    while (n >>= 1) ++pos;
    return pos;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

package main

func MSBPos(n uint) int {
    if n == 0 { return -1 }
    pos := 0
    for n >>= 1; n != 0; n >>= 1 {
        pos++
    }
    return pos
}
1
2
3
4
5
6
7
8

class Solution {
    public int msbPos(int n) {
        if (n == 0) return -1;
        int pos = 0;
        while ((n >>= 1) != 0) pos++;
        return pos;
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def msb_pos(self, n: int) -> int:
        if n == 0:
            return -1
        pos = 0
        while n >> 1:
            n >>= 1
            pos += 1
        return pos

Complexity

  • ⏰ Time complexity: O(b), where b is the number of bits (e.g., 32 or 64).
  • 🧺 Space complexity: O(1).

Method 2 — Binary-search-like mask

Intuition

Check ranges of bit widths using masks (e.g., check high half of bits). Repeatedly narrow to the half that contains any set bit — this requires at most O(log b) mask checks.

Approach

  • Set low = 0, high = w-1 for word width w (e.g., 31 for 32-bit signed).
  • While high - low > 1, compute mid = (high + low)/2 and a mask for bits mid+1..high.
  • If (n & mask) != 0 then the MSB lies in the high half: set low = mid; else high = mid.
  • Return low as the MSB position.

Code (sketch)

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

class Solution {
 public:
  int msb_pos_binsearch(unsigned int n) {
    if (n == 0) return -1;
    int low = 0, high = 31; // assumes 32-bit word
    while (high - low > 1) {
      int mid = (high + low) / 2;
      unsigned int mask = ((1u << (high - mid)) - 1u) << (mid + 1);
      if (n & mask) low = mid; else high = mid;
    }
    return low;
  }
};
Go (sketch)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func MSBPosBinSearch(n uint32) int {
    if n == 0 { return -1 }
    low, high := 0, 31
    for high - low > 1 {
        mid := (high + low) / 2
        mask := ((uint32(1) << (high - mid)) - 1) << (mid + 1)
        if n & mask != 0 { low = mid } else { high = mid }
    }
    return low
}

Complexity

  • ⏰ Time complexity: O(log b) (log of the bit-width).
  • 🧺 Space complexity: O(1).

Method 3 — Use builtins (fast, recommended)

Intuition

Most platforms expose operations for counting leading zeros or bit-length. MSB position equals bit_length(n) - 1 or w - 1 - clz(n).

Approach

  • Validate n != 0 then use a builtin (__builtin_clz, Integer.numberOfLeadingZeros, int.bit_length()), then compute MSB position.

Code

1
2
3
4

int msb_pos_builtin(unsigned int n) {
  if (n == 0) return -1;
  return 31 - __builtin_clz(n); // for 32-bit
}
1
2
3
4

int msbPos(int n) {
  if (n == 0) return -1;
  return 31 - Integer.numberOfLeadingZeros(n);
}
1
2
3
4

def msb_pos(n: int) -> int:
    if n == 0:
        return -1
    return n.bit_length() - 1

Complexity

  • ⏰ Time complexity: O(1) for fixed-size words (builtin operations compile to a few CPU instructions).
  • 🧺 Space complexity: O(1).

Notes & References

  • Choose Method 3 when available — it’s simple and fast. Method 1 is portable and trivial. Method 2 can be useful in environments without clz/bit_length.
  • Sample runs and additional discussion originally from the referenced tutorial (see source_links in frontmatter).