Cracking The Coding Interview Together – Problem 5.4: Next Number

Imagine you are optimizing a high-frequency trading engine or a low-latency cache where every microsecond—and every byte—matters. You are storing compact state representations using bitmasks. Suddenly, a business requirement demands that you transition to the next valid state configuration while keeping the exact same number of active flags (set bits). How do you do this instantly, without looping through millions of integers?

This is the core conflict of Problem 5.4: Next Number from Cracking the Coding Interview. It forces us to move past high-level abstractions and look directly at how data is structured in silicon. Bit manipulation can often feel like arcane wizardry, but once you understand the underlying mechanics, it becomes an incredibly elegant tool in our architectural toolkit. Today, we are going to demystify this problem together, building a robust, production-ready solution from first principles.

Problem Statement

Next Number: Given a positive integer, print the next smallest and the next largest number that have the same number of 1 bits in their binary representation.

The problem asks us to do the following: Given a positive integer n, print the next smallest and the next largest number that have the same number of 1 bits (also known as the Hamming weight) in their binary representation.

To ensure we are aligned on terminology:

• Next Largest: The smallest integer strictly greater than n that has the same number of set bits.
• Next Smallest: The largest integer strictly less than n that has the same number of set bits.

For example, let's look at n = 139:

• Binary representation: 10001011 (which has 4 set bits).
• The next largest number with 4 set bits is 141 (binary: 10001101).
• The next smallest number with 4 set bits is 135 (binary: 10000111).

Analyze the Problem Together

Let's break down the constraints and the mathematical reality of this challenge. A naive approach is highly tempting: we could simply increment n by 1, count its set bits using a helper function (or Java's built-in Integer.bitCount()), and stop when we find a number with the same count. We would then do the same by decrementing n to find the smaller number.

But as senior engineers, we must ask: What is the worst-case performance of this approach?

Consider an integer like n = 2^30 - 1 (a sequence of thirty 1s followed by a 0). The next larger integer with the same number of 1s is 2^31 - 2, which is over a billion steps away! A linear search would cause a catastrophic CPU spike, making it completely unacceptable for production environments.

This brings us to our "Aha!" moment: We must manipulate the bits directly.

To find the next largest number, we need to make the number slightly bigger while keeping the number of 1s constant. This means we must flip a 0 to a 1 at some position p, and to compensate, flip a 1 to a 0 at some position to the right of p. To make this increase as small as possible, we should find the rightmost 0 that has a 1 to its right (the first non-trailing zero), flip it to 1, and then rearrange the remaining 1s to the right of p to be as small as possible (i.e., packed at the far right).

Let's compare the two approaches side-by-side:

Questions for the Interviewer

Before we write a single line of code, we must clarify the boundaries of our system. In a real interview or design session, asking these questions demonstrates your senior-level foresight:

1. How should we handle overflow boundaries? If n is a number like 11110000..., there may not be a larger 32-bit signed integer with the same number of 1s. Should we return -1, throw an IllegalArgumentException, or return an empty/optional value?
2. Are we restricted to 32-bit signed integers? Or should we design this to support 64-bit long values as well? (For this guide, we will focus on 32-bit signed integers, but the logic scales seamlessly to 64-bit).
3. Can we assume the input is always strictly positive? The problem statement specifies a positive integer, but validating inputs at the entry point is a core defensive programming practice we should maintain.

Think About the Solution

Let's design the step-by-step bitwise algorithms for both operations.

The Next Largest Number (getNext)

To find the next largest number, we must:

1. Traverse from right to left to find the first non-trailing zero. Let's call its index p. This is the first 0 that has a 1 to its right.
2. Let c0 be the number of trailing zeros to the right of p, and c1 be the number of ones to the right of p. Thus, p = c0 + c1.
3. Flip the bit at index p from 0 to 1.
4. Clear all bits to the right of p (indices 0 to p-1).
5. Insert c1 - 1 ones at the very right (indices 0 to c1 - 2). This minimizes the value of the lower bits while maintaining the correct count of set bits.

The Next Smallest Number (getPrev)

To find the next smallest number, we must do the inverse:

1. Traverse from right to left to find the first non-trailing one. Let's call its index p. This is the first 1 that has a 0 to its right.
2. Let c1 be the number of trailing ones to the right of p, and c0 be the number of zeros to the right of p. Thus, p = c0 + c1.
3. Flip the bit at index p from 1 to 0.
4. Clear all bits to the right of p.
5. Insert c1 + 1 ones immediately to the right of p (indices p-1 down to p - 1 - c1). This maximizes the value of the lower bits while maintaining the correct count of set bits.

Edge Cases to Handle

• No Next Largest: If n has no non-trailing zeros (e.g., 11110000... in a 32-bit space where we cannot shift the 1s any further left without overflowing), we must return -1.
• No Next Smallest: If n has no non-trailing ones (e.g., 00001111), we cannot make it any smaller without reducing the number of set bits or going negative. We must return -1.

Write Code and Explain

Let's implement this logic in a clean, production-ready Java class. We will use descriptive variable names and write comprehensive comments to explain the bitwise masks.

public class NextNumberSolver {

    /**
     * Finds the next largest number with the same number of set bits.
     * @param n a positive integer
     * @return the next largest integer, or -1 if none exists
     */
    public static int getNext(int n) {
        if (n <= 0) {
            throw new IllegalArgumentException("Input must be a positive integer.");
        }

        int temp = n;
        int c0 = 0;
        int c1 = 0;

        // Count trailing zeros
        while (((temp & 1) == 0) && (temp != 0)) {
            c0++;
            temp >>>= 1;
        }

        // Count trailing ones
        while ((temp & 1) == 1) {
            c1++;
            temp >>>= 1;
        }

        int p = c0 + c1; // Position of the first non-trailing zero

        // Edge case: If we reached the MSB and there is no non-trailing zero
        // (e.g., 1111000... or 11111...)
        if (p >= 31 || p == 0) {
            return -1;
        }

        // Flip the first non-trailing zero to 1
        n |= (1 << p);

        // Clear all bits to the right of p
        n &= ~((1 << p) - 1);

        // Insert (c1 - 1) ones at the very right
        n |= (1 << (c1 - 1)) - 1;

        return n;
    }

    /**
     * Finds the next smallest number with the same number of set bits.
     * @param n a positive integer
     * @return the next smallest integer, or -1 if none exists
     */
    public static int getPrev(int n) {
        if (n <= 0) {
            throw new IllegalArgumentException("Input must be a positive integer.");
        }

        int temp = n;
        int c0 = 0;
        int c1 = 0;

        // Count trailing ones
        while ((temp & 1) == 1) {
            c1++;
            temp >>>= 1;
        }

        // If temp is 0, it means the number was of the form 000...111
        // There is no smaller positive number with the same number of set bits.
        if (temp == 0) {
            return -1;
        }

        // Count trailing zeros
        while (((temp & 1) == 0) && (temp != 0)) {
            c0++;
            temp >>>= 1;
        }

        int p = c0 + c1; // Position of the first non-trailing one

        // Flip the first non-trailing one to 0
        n &= (~0 << (p + 1));

        // Insert (c1 + 1) ones immediately to the right of p
        int mask = (1 << (c1 + 1)) - 1;
        n |= (mask << (c0 - 1));

        return n;
    }
}

Step-by-Step Walkthrough

Let's trace getNext(139) where 139 is 10001011 in binary:

1. Counting: The trailing bits are 11. Thus, c0 = 0 (no trailing zeros) and c1 = 2 (two trailing ones).
2. Position p: p = 0 + 2 = 2. This is the index of the first non-trailing zero (the bit at index 2 is indeed 0).
3. Flip p: We execute n |= (1 << 2). Binary becomes 10001111.
4. Clear right of p: We execute n &= ~((1 << 2) - 1), which is n &= ~3 (binary ...11111100). Binary becomes 10001100.
5. Insert ones: We execute n |= (1 << (2 - 1)) - 1, which is n |= 1. Binary becomes 10001101, which is 141.

Let's check if 141 (10001101) has 4 set bits. Yes! Is it larger than 139? Yes. Is there any number between 139 and 141 with 4 set bits? 140 is 10001100 (3 set bits). So yes, 141 is indeed the next largest! The code is mathematically precise and correct.

Time & Space Complexity

Let's analyze the efficiency of our bit manipulation solution:

• Time Complexity: O(b), where b is the number of bits in the integer. Since we are dealing with standard 32-bit integers, the loops will run at most 32 times. This makes the time complexity effectively O(1) (constant time). There are no nested loops or dynamic allocations.
• Space Complexity: O(1) auxiliary space. We only use a few primitive integer variables (temp, c0, c1, p) to store state, which are allocated on the stack and cleaned up immediately upon function return.

Why This Problem Matters (The Senior Perspective)

As senior engineers, we don't just solve puzzles; we build systems. Why should you care about bit manipulation in a world dominated by high-level frameworks like Spring, React, or Kubernetes?

First, memory efficiency at scale. When designing high-performance systems (like custom database engines, search indexes, or game servers), storing state in rich objects is incredibly expensive. We often pack multiple boolean flags and small integers into a single 32-bit or 64-bit word. Understanding how to traverse and manipulate these bit fields directly allows you to write highly optimized serialization and state-transition logic.

Second, thread safety and concurrency. Bitwise operations on primitive types are atomic at the hardware level when combined with volatile variables or atomic classes (like AtomicInteger). By avoiding complex object allocations and mutations, we can write lock-free, highly concurrent algorithms that scale beautifully across multi-core processors.

Third, cryptographic and network protocols. Protocols like TCP/IP, TLS, and custom binary protocols rely heavily on precise bit alignments. Knowing how to mask, shift, and manipulate bits is a foundational skill for any engineer working close to the network or security layers.

Final Thoughts

Bit manipulation can feel intimidating because it strips away the comfortable abstractions of modern programming languages. However, as we have seen today, breaking the problem down into logical steps—counting boundaries, clearing masks, and shifting bits—reveals a highly structured and predictable pattern.

The next time you face a performance bottleneck or need to design a compact state machine, remember that the CPU is optimized to perform these exact bitwise operations in a single clock cycle. Use them to your advantage!

What are your thoughts on this approach? Have you ever had to optimize a production system using low-level bitwise operations? Let's discuss in the comments below!

Happy coding, and see you in the next deep dive!