Highest power of 2 less than or equal to given number

Problem Statement

Given a number n, find the highest power of 2 that is smaller than or equal to n.

Example 1:

  • Input: n=5
  • Output: 4

Example 2:

  • Input: n=25
  • Output: 16

Example 3:

  • Input: n=32
  • Output: 32

Solution

The simplest solution is to start with powers of 2 from 1, such as 21. For every power of two, check if it’s greater than the given number. If it’s greater than the given number, then return the previous/last power of two.

Example

class Main{
    static int highestPowerofTwoLessThanN(int n) {
        if (n < 1) return 0;
        int pow = 1;
        while((1 << pow) <= n) pow++;
        return (1 << (pow - 1));
    }
    public static void main (String[] args) {
        int n = 10;
        System.out.println("The highest power of 2 less than " + n + " is " + highestPowerofTwoLessThanN(n));
    }
}

Code explanation

  • Line 4: If n is less than 1, then return zero.
  • Line 6: Initialize the power variable to 1.
  • Line 8: While 2power is less than or equal to n, increment the power value by 1.
  • Line 10: Once the control is out of the while loop, it means that we have a power of two that is greater than n. Hence, we return the power of two for the last/previous power value.
  • Line 14: The n number is defined.

Complexity analysis

  • Time Complexity: O(n) in worst case

  • Space Complexity: O(1)

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved