Powers Of 2 | Coding Problems In Java

Finding the highest power of 2 that is not bigger than a number is a small problem, but it shows up inside bigger ones: sizing hash tables and buffers, building segment trees, and binary lifting all need it.

Problem

Write a program that prints the highest power of 2 that is less than or equal to a given number. For example, if the input is 9, print 8, because 8 = 2³ and the next power, 16, is bigger than 9.

Input: 9       Output: 8
Input: 16      Output: 16
Input: 1000    Output: 512
Input: 1       Output: 1

Approach 1: keep doubling

Start with result = 1 (which is 2⁰) and keep doubling it as long as the doubled value would still be at most n. When doubling again would overshoot, result is the answer.

For n = 9: 1 → 2 → 4 → 8. Doubling 8 would give 16, which is more than 9, so we stop and print 8.

One small but real detail: the obvious condition result * 2 <= number overflows when the number is close to Integer.MAX_VALUE, because result * 2 can wrap around to a negative value. Writing it as result <= number / 2 checks the same thing without ever going past the limit.

Solution in Java

import java.util.Scanner;

public class PowersOf2 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int number = scan.nextInt();
        if (number < 1) {
            System.out.println("Please enter a positive integer");
            return;
        }
        int result = 1;
        while (result <= number / 2) {   // same as result * 2 <= number, but cannot overflow
            result *= 2;
        }
        System.out.println(result);
    }
}

Approach 2: use the bits

In binary, a power of 2 is a single 1 followed by zeros. The highest power of 2 that is at most n is simply n with every bit except the highest one switched off. 9 is 1001 in binary, and keeping only the top bit gives 1000, which is 8.

Java does this for you: Integer.highestOneBit(n). In C++20 there is std::bit_floor(n), and with GCC you can write 1 << (31 - __builtin_clz(n)) for n > 0.

Complexity

• Doubling loop: O(log n) time, since the result doubles every step. For an int that is at most 31 iterations.
• Bit approach: O(1).
• Both use O(1) space.

Related checks

• To test whether n itself is a power of 2: n > 0 && (n & (n - 1)) == 0.
• To find the smallest power of 2 that is at least n, take the answer above and double it if it is less than n.

The old version of this solution rejected the input 1. But 1 is 2⁰, a perfectly good power of two, so the program above now prints 1 for it.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More Java solutions All coding problems MCQ practice