Bit Manipulation Problems

Insertion

You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to insert M int N such that M starts at bit j and ends at bit i. You can assume that bits j through i have enough space to fit all of M.

Example :

Input:  N = 0b10000000000,    M = 0b10011,    i = 2,  j = 6
Output: N = 0b10001001100

This problem can be approached in three keys steps:

1. Clear the bits j through i in N
2. Shift M So that it lines up with bits j through i
3. Merge M and N

The trickiest part is Step 1. How do we clear the bits in N? We can do this with a mask. This mask will have all 1s, except for 0s in the bits j through i. We create this mask by creating the left half of the mask first, and then the right half.

int UpdateBits(int N, int M, int i, int j)
{
    int allOnes = ~0;
    int leftMask = allOnes << (j + 1);
    int rightMask = (1 << i) - 1;
    int mask = leftMask | rightMask;

    int N_Cleared = N & mask;
    int M_Shifted = M << i;

    return N_Cleared | M_Shifted;
}

Explanation:

Assume a 8-bit number. Let i = 2 and j = 4 , the mask should be 11100011. So left mask should be 11100000 and right mask 00000011