Problem

You are given an integer n that contains exactly one set bit (1) in its binary representation. Find the position of that set bit. Positions are 1-based from the least-significant bit (LSB).

If the input does not contain exactly one 1 (e.g., n == 0 or has multiple ones), implementations below return 0 to indicate an invalid input unless otherwise noted.

Examples

Example 1

1
2
3

Input: n = 8
Output: 4
Explanation: 8 = 0b1000, the only set bit is at position 4 (1-based from LSB).

Example 2

1
2

Input: n = 1
Output: 1
Similar Problems

Solution

Method 1 — Power-of-two check (fast)

Intuition

If a number contains exactly one set bit then it is a power of two. The test n != 0 && (n & (n - 1)) == 0 verifies that property in one branch-free check. Once confirmed, the position of the set bit is the number of trailing zeros plus one (1-based). Many languages expose a fast builtin to count trailing zeros; otherwise a small loop or bit-length-based trick yields the same result.

Approach

  • Validate that n has exactly one set bit: return 0 if n == 0 or (n & (n - 1)) != 0.
  • If a builtin trailing-zero count (ctz) is available, return ctz(n) + 1.
  • Otherwise, compute the position by one of:
    • Loop: shift right until the LSB is 1 and count shifts.
    • Bit-length: isolate the lowest set bit lsb = n & -n and use pos = bit_length(lsb) (or equivalent) to get 1-based position.
  • Edge cases: handle n == 0 (invalid) and ensure arithmetic uses unsigned or masks where needed to avoid sign-extension issues.

Code

1
2
3
4
5
6
7
8
9

class Solution {
 public:
  int findSingleSetBitPos(unsigned int n) {
    if (n == 0u || (n & (n - 1u)) != 0u) return 0; // invalid input
    // fast builtin when available
    int ans = __builtin_ctz(n) + 1; // defined for n != 0
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

package main

func FindSingleSetBitPos(n uint) int {
  if n == 0 || (n&(n-1)) != 0 {
    return 0
  }
  // fallback loop to avoid imports
  ans := 1
  for (n & 1) == 0 {
    n >>= 1
    ans++
  }
  return ans
}
1
2
3
4
5
6
7

class Solution {
  public int findSingleSetBitPos(int n) {
    if (n == 0 || (n & (n - 1)) != 0) return 0;
    int ans = Integer.numberOfTrailingZeros(n) + 1;
    return ans;
  }
}
1
2
3
4
5
6
7

class Solution:
    def find_single_set_bit_pos(self, n: int) -> int:
        if n == 0 or (n & (n - 1)) != 0:
            return 0
        # n is power of two; position is bit_length of n (1-based)
        ans: int = n.bit_length()
        return ans

Complexity

  • ⏰ Time complexity: O(1), constant-time checks and either a CPU ctz or a small loop proportional to word-size in fallback.
  • 🧺 Space complexity: O(1), constant extra space.

Method 2 — Scan Bits (naive)

Intuition

Walk from the least-significant bit upward and test each bit until you find the set bit. This is simple and works in O(b) where b is the word-width.

Approach

  • If n == 0 or (n & (n - 1)) != 0 then n does not have exactly one set bit — return 0.
  • Initialize pos = 1 and loop while n != 0:
    • If (n & 1) != 0 return pos.
    • Right-shift n by 1 and increment pos.

Code

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

class Solution {
 public:
  int findSingleSetBitPos(unsigned int n) {
  if (n == 0 || (n & (n - 1)) != 0) return 0; // invalid input
  int pos = 1;
  while ((n & 1u) == 0u) {
    n >>= 1u;
    ++pos;
  }
  return pos;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

package main

func FindSingleSetBitPos(n uint) int {
  if n == 0 || (n&(n-1)) != 0 {
    return 0
  }
  pos := 1
  for (n & 1) == 0 {
    n >>= 1
    pos++
  }
  return pos
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

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

Complexity

  • ⏰ Time complexity: O(b) where b is the number of bits in the word (e.g., 32 or 64). In the worst case you scan up to the set bit.
  • 🧺 Space complexity: O(1).

Method 3 — Use Trailing-Zero Count (fast)

Intuition

The index of the only set bit equals the number of trailing zeros plus one. Many platforms provide an intrinsic to count trailing zero bits (often one CPU instruction) which gives pos = ctz(n) + 1.

Approach

  • Validate input has exactly one set bit: n != 0 && (n & (n - 1)) == 0.
  • Return ctz(n) + 1 using a builtin where available; otherwise fall back to Method 1.

Code

1
2
3
4
5
6
7

class Solution {
 public:
  int findSingleSetBitPos(unsigned int n) {
  if (n == 0 || (n & (n - 1)) != 0) return 0;
  return __builtin_ctz(n) + 1; // counts trailing zeros
  }
};
1
2
3
4
5
6
7
8

import "math/bits"

func FindSingleSetBitPosFast(n uint) int {
  if n == 0 || (n&(n-1)) != 0 {
    return 0
  }
  return bits.TrailingZeros(uint(n)) + 1
}
1
2
3
4
5
6

class Solution {
  public int findSingleSetBitPos(int n) {
    if (n == 0 || (n & (n - 1)) != 0) return 0;
    return Integer.numberOfTrailingZeros(n) + 1;
  }
}
1
2
3
4
5
6
7
8
9

import math

class Solution:
  def find_single_set_bit_pos_fast(self, n: int) -> int:
    if n == 0 or (n & (n - 1)) != 0:
      return 0
    # Python 3.11+: int.bit_count available, but trailing zero helper not built-in until 3.11
    # Fallback: use (n & -n) to isolate lowest set bit and compute position via bit_length
    return (n & -n).bit_length()

Complexity

  • ⏰ Time complexity: O(1) for fixed-size machine words when using an intrinsic (or effectively constant time).
  • 🧺 Space complexity: O(1).