Bitwise nuggets: insert a number inside another one

Here we discuss how to insert a number m into a number n between positions i and j.

Let us see an example to better visualize what this means. Suppose we have the number n = 1040 and that we want to insert the number m = 19 into it, between positions i = 2 and j = 6. As shown below, by doing so we obtain the number 1100:

We could go about this in a number of different ways. We’ll just do lazy here , meaning we make two very generous assumptions:

1. The number of bits between i and j is indeed the actual number of bits in number m.
2. There are enough bits in n for inserting m into it.

With that out of the way, we can now focus on the task at hand. The tricky part is to zero-out the bits in number n between positions i and j (in yellow in the figure above). To do this, we must create a bit mask that goes from 0 through j and that has two parts:

• The “left”-most part (between positions i and j) is all zeros (we want to zero-out this part of n). We can obtain it by left-shifting 1 by j + 1 bits, subtracting 1, and finally inverting (logical NOT) the mask.
• The “right”-most part (between positions 0 and i - 1) is all ones (we want to keep this part of n). We can obtain it by left-shifting 1 by i bits, then subtracting 1.

Once that’s done, we must bring together the two parts of the mask using the logical OR operator.

Next, we apply the mask to the number n, thus clearing its bits at positions i through j. Now the only thing that’s left is to “insert” m into n between these indexes, which we can do by left-shifting m by i bits, followed by applying the logical OR operator.

Here is how this algorithm can be implemented in C:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// Insert number `m` into number `n` between positions `j` through `i`.
// Assumption 1: the number of bits between `j` and `i` is the number of bits of `m`.
// Assumption 2: there are enough bits in `n` for inserting `m`.
int insert_number_inside_another(int n, int m, int i, int j)
{
    /*
    Create a mask that zeroes out bits from positions j through i (inclusive)
    in n when using the AND operator between n and the mask.
    The mask has the following form:
          Mask:        1   ...  1   0   ...   0   1   ...   1
          Positions: |n|-1     j+1  j         i  i-1        0
    */
    int mask = ~((1 << (j + 1)) - 1) | ((1 << i) - 1);

    // Apply the mask to turn off bits betwene j and i, then insert m.
    return (n & mask) | (m << i);
}

Whew, that long explanation for only 2 lines of actual code, who would have thought?

Want to see more bitwise logic? There’s a whole repository on my GitHub on bit fiddling.