Find the largest power of 2 less than a given number

Problem

Given a non-negative integer N, find the largest power of two less than or equal to N.

Return 0 if N == 0.

Examples

Example 1

Input: N = 1
Output: 1

Example 2

Input: N = 15
Output: 8

Example 3

Input: N = 21
Output: 16

Solution

We show three approaches: bit-propagation trick (fast constant-time for fixed width), using bit-length/clz builtins, and a simple loop.

Method 1 — Bit propagation (turn lower bits to 1)

Intuition

Propagate the most-significant 1 to all lower positions by repeated OR with right-shifted versions of N. After propagation the number becomes 2*x - 1 where x is the desired power of two; compute (propagated + 1) >> 1 to get x.

Approach

• If N == 0 return 0.
• Let x = N and perform successive x |= x >> k for k = 1,2,4,8,... up to word size.
• After propagation x = 2*ans - 1; return (x + 1) >> 1.

Code

C++

class Solution {
 public:
  unsigned int largestPower(unsigned int n) {
  if (n == 0) return 0ULL;
  unsigned int x = n;
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  x |= x >> 32; // covers up to 64-bit
  return (x + 1ULL) >> 1;
  }
};

Go

package main

func LargestPower(n uint32) uint32 {
  if n == 0 { return 0 }
  x := n
  x |= x >> 1
  x |= x >> 2
  x |= x >> 4
  x |= x >> 8
  x |= x >> 16
  x |= x >> 32
  return (x + 1) >> 1
}

Java

class Solution {
  public int largestPower(int n) {
    if (n == 0) return 0;
    int x = n;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x |= x >> 32;
    return (x + 1) >> 1;
  }
}

Python

class Solution:
  def largestPower(self, n: int) -> int:
    if n == 0:
      return 0
    x = n
    x |= x >> 1
    x |= x >> 2
    x |= x >> 4
    x |= x >> 8
    x |= x >> 16
    x |= x >> 32
    return (x + 1) >> 1

Complexity

• ⏰ Time complexity: O(1) for fixed-size words — a constant number of bit operations.
• 🧺 Space complexity: O(1).

Method 2 — Use bit-length / leading-zero builtins

Intuition

Find the index of the highest set bit and return 1 << index (or 1ULL << index for larger types).

Approach

• If N == 0 return 0.
• Use platform builtin to obtain the number of leading zeros or bit_length.
• Compute index = bit_length - 1, then return 1 << index.

Code

C++

class Solution {
 public:
  unsigned int largestPower(unsigned int n) {
  if (n == 0) return 0ULL;
  int idx = 31 - __builtin_clz(n); // index of MSB (0-based) for 32-bit
  return 1U << idx;
  }
};

Go

import "math/bits"

func LargestPower(n uint32) uint32 {
  if n == 0 { return 0 }
  idx := 31 - bits.LeadingZeros32(n)
  return 1 << idx
}

Java

class Solution {
  public int largestPower(int n) {
    if (n == 0) return 0;
    int idx = 31 - Integer.numberOfLeadingZeros(n);
    return 1 << idx;
  }
}

Python

class Solution:
  def largestPower(self, n: int) -> int:
    if n == 0:
      return 0
    return 1 << (n.bit_length() - 1)

Complexity

• ⏰ Time complexity: O(1) (builtin operations are constant-time for fixed words).
• 🧺 Space complexity: O(1).

Method 3 — Simple loop (logarithmic)

Intuition

Keep doubling a power-of-two until it would exceed N, then return the previous value.

Approach

• If N == 0 return 0.
• Initialize ans = 1.
• While (ans << 1) <= N: ans <<= 1.
• Return ans.

Code

C++

class Solution {
 public:
  unsigned int largestPower(unsigned int n) {
  if (n == 0) return 0ULL;
  unsigned int ans = 1ULL;
  while ((ans << 1) <= n) ans <<= 1;
  return ans;
  }
};

Go

func LargestPower(n uint32) uint32 {
  if n == 0 { return 0 }
  ans := uint32(1)
  for (ans << 1) <= n { ans <<= 1 }
  return ans
}

Java

class Solution {
  public int largestPower(int n) {
    if (n == 0) return 0;
    int ans = 1;
    while ((ans << 1) <= n) ans <<= 1;
    return ans;
  }
}

Python

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

Complexity

• ⏰ Time complexity: O(log N) — number of loop iterations is the index of the MSB.
• 🧺 Space complexity: O(1).