Cracking The Coding Interview Together – Problem 5.1: Insertion

Bit manipulation is one of those topics that often strikes fear into the hearts of software engineers. Why? Because in our day-to-day work building microservices, designing APIs, and querying databases, we rarely have to think about individual bits. We operate in a comfortable world of high-level abstractions, objects, and serialization formats. But when you dive into performance-critical systems, network protocols, or embedded devices, bit manipulation becomes your bread and butter.

Today, we are going to tackle a classic problem from Cracking the Coding Interview: Problem 5.1 (Insertion). This problem is a fantastic playground for mastering bitwise masks. It forces us to think about how numbers are represented in memory and how we can surgically alter specific regions of a 32-bit integer without disturbing the surrounding data. Our goal is to build a solution that is not only correct but also robust enough to handle tricky edge cases that many junior developers overlook.

Problem Statement

Let's define the operational goals of the problem clearly. You are given two 32-bit numbers, N and M, and two bit positions, i and j. Your task is to write a method to insert M into N such that M starts at bit j and ends at bit i.

You can assume that the bits j through i have enough space to fit all of M. That is, if M = 10011, you can assume that there are at least 5 bits between j and i. You can also assume that j and i are valid bit indices (where 0 is the least significant bit on the far right, and 31 is the most significant bit on the far left).

Example:

• Input: N = 10000000000 (binary), M = 10011 (binary), i = 2, j = 6
• Output: N = 10001001100 (binary)

Analyze the Problem Together

Let's break down the constraints and highlight the core conflict. A naive approach might be to simply shift M to the left by i bits and perform a bitwise OR operation: N | (M << i). Why doesn't this work? Let's trace it. If N already has 1s in the range [i, j], those 1s will persist after the OR operation, corrupting the value of M we are trying to insert. For example, if we try to insert 0 into a position where N has a 1, the OR operation will keep it as 1.

Therefore, the "Aha!" moment is realizing that we must clear the bits in N from index i to j before we insert M. Clearing bits means setting them to 0. Once that region in N is completely zeroed out, we can safely use the bitwise OR operator to merge the shifted version of M into N.

Let's compare a loop-based approach versus a mask-based approach to see why the latter is superior:

Questions for the Interviewer

As senior engineers, we never jump straight into coding without clarifying the boundaries of the problem. Here are three critical questions we should ask our interviewer:

• Q1: Are we guaranteed that M fits within the range [i, j]? If M is larger than the allocated space, should we truncate M, throw an exception, or assume the input is always well-formed? (For this problem, we will assume it fits, but we should mention how to handle truncation).
• Q2: How should we handle the edge case where j = 31? In Java, shifting a 32-bit integer by 32 bits (e.g., ~0 << 32) does not result in 0 due to shift-amount masking (it actually shifts by 32 % 32 = 0 bits, resulting in ~0). We must handle this explicitly.
• Q3: Are we dealing with signed or unsigned integers? Java integers are signed 32-bit values. We need to ensure our bitwise shifts do not introduce unexpected sign-extension bugs.

Think About the Solution

Let's design our bitmask step-by-step. We want to create a mask that has 1s everywhere except in the range [i, j], where it should have 0s. Once we have this mask, we can perform N & mask to clear the target range.

How do we build a mask like 111110000011 (for i=2, j=6)? We can split it into two parts:

1. The Left Part: All 1s from the most significant bit down to j + 1, followed by 0s. We can get this by shifting a sequence of all 1s (which is ~0) to the left by j + 1 bits.
   left = ~0 << (j + 1)
2. The Right Part: All 0s from the most significant bit down to i, followed by 1s from i - 1 down to 0. We can get this by taking 1, shifting it left by i, and subtracting 1.
   right = (1 << i) - 1

By combining these two parts using a bitwise OR (left | right), we get our perfect mask. Let's trace this with our example: i = 2, j = 6.

• ~0 is 11111111111111111111111111111111
• left = ~0 << 7 is 11111111111111111111111110000000
• right = (1 << 2) - 1 is 00000000000000000000000000000011
• mask = left | right is 11111111111111111111111110000011

This is exactly what we need! Now we can clear the bits in N, shift M by i, and merge them.

Write Code and Explain

Here is the production-ready Java implementation. Note how we handle the edge case where j = 31 to prevent the shift-overflow bug.

public class BitInsertion {

    /**
     * Inserts M into N such that M starts at bit j and ends at bit i.
     * 
     * @param n The destination 32-bit integer.
     * @param m The source 32-bit integer to be inserted.
     * @param i The starting bit position (inclusive).
     * @param j The ending bit position (inclusive).
     * @return The modified integer.
     */
    public static int insertBits(int n, int m, int i, int j) {
        // Validation check
        if (i < 0 || j >= 32 || i > j) {
            throw new IllegalArgumentException("Invalid bit boundaries: i and j must be between 0 and 31, and i <= j.");
        }

        // Create the left part of the mask
        // If j is 31, shifting by (j + 1) i.e. 32 bits in Java is a no-op due to shift masking.
        // We handle this by setting left to 0 when j is 31.
        int left = (j >= 31) ? 0 : (~0 << (j + 1));

        // Create the right part of the mask
        int right = (1 << i) - 1;

        // Combine left and right to form the complete mask
        int mask = left | right;

        // Clear bits j through i in N
        int nCleared = n & mask;

        // Shift M so that it aligns with bits j through i
        int mShifted = m << i;

        // Merge the cleared N and shifted M
        return nCleared | mShifted;
    }
}

Step-by-Step Walkthrough

Let's walk through the execution of insertBits(1024, 19, 2, 6). In binary:

• N = 1024 which is 0100 0000 0000 in binary.
• M = 19 which is 10011 in binary.
• i = 2, j = 6.

First, we calculate the mask:

• Since j = 6 (which is less than 31), left = ~0 << 7, which gives us ...1111 1000 0000.
• right = (1 << 2) - 1, which is 3 in decimal, or ...0000 0000 0011 in binary.
• mask = left | right, which is ...1111 1000 0011.

Next, we clear the target bits in N:

• nCleared = N & mask. Since N is 0100 0000 0000, applying the mask zeroes out bits 2 through 6. In this specific case, those bits were already zero, so nCleared remains 0100 0000 0000.

Then, we align M:

• mShifted = M << 2. 19 << 2 shifts 10011 to 1001100 (which is 76 in decimal).

Finally, we merge them:

• result = nCleared | mShifted. This performs a bitwise OR between 0100 0000 0000 and 0000 0100 1100, resulting in 0100 0100 1100 (which is 1100 in decimal).

Time & Space Complexity

Let's analyze the efficiency of our solution. In bit manipulation, we are operating directly on the CPU registers, which makes these operations incredibly fast.

• Time Complexity: O(1) We perform a constant number of bitwise operations (shifts, ANDs, ORs, and negations). The execution time does not depend on the size of the inputs N or M.
• Space Complexity: O(1) We only allocate a few local variables (left, right, mask, etc.) on the stack. No dynamic memory allocation occurs.

Why This Problem Matters (The Senior Perspective)

You might ask: "When will I ever need to clear a range of bits in a real-world enterprise application?"

Consider network packet parsing. When you write high-performance networking code (like a custom TCP/IP stack or a game server protocol), bandwidth is at a premium. Instead of sending JSON over the wire, you pack multiple fields into a single 32-bit integer. For example, the first 4 bits might represent the protocol version, the next 8 bits the packet type, and the remaining 20 bits the payload size. To update the packet type field dynamically, you must use the exact insertion technique we implemented today.

Another critical consideration is thread safety. If multiple threads are reading and writing to a shared configuration register represented as an integer, bitwise operations are not thread-safe by default. In a production environment, you would need to wrap these operations using atomic classes, such as Java's AtomicInteger, and perform a Compare-And-Swap (CAS) loop to ensure updates are atomic:

public void updateRegister(AtomicInteger reg, int m, int i, int j) {
    int currentValue, newValue;
    do {
        currentValue = reg.get();
        newValue = insertBits(currentValue, m, i, j);
    } while (!reg.compareAndSet(currentValue, newValue));
}

Final Thoughts

We've successfully demystified bitwise insertion! By breaking down the problem into creating a left mask, a right mask, and merging them, we avoided the classic pitfalls of bit manipulation. We also highlighted how language-specific quirks (like Java's shift-masking behavior) can introduce silent bugs if not handled with care.

What other bit manipulation problems have you found challenging? Try modifying this code to handle cases where M is too large for the range and needs to be truncated. Let's discuss in the comments below!

Until next time, happy coding!