Bit Manipulation: How to Set All Bits Between i and j in N equal to M?

Given two 32-bit integers N and M, write a function to replace N (between bits position i and j) with M, so M becomes a substring of N located at position i, starting at j. For example, if N = 10000000000, M = 10101, i = 2 and j = 6, you should output N = 10001010100.

Bit Manipulation

You could write a loop, but it is the least elegant solution. Bit Manipulation is the way to go. Let’s go through the steps one by one.

First, we set max = ~0; which is the complement’s of zeros and in other words, all ones. Then the following will generate all ones through position j then 0’s.

1

int left = max - ((1 << j) - 1); 

int left = max - ((1 << j) - 1); 

Then, 1’s after position i,

1

int right = ((1 << i) - 1);

int right = ((1 << i) - 1);

If we put these two together, we have a mask value that has 0’s between i and j, but 1’s all other bits.

1

int mask = right | left;

int mask = right | left;

Then our final step is to clear i through j and put m in there.

1

(n & mask) | (m << i);

(n & mask) | (m << i);

The complete C/C++ function is:

1
2
3
4
5
6
7
8
9
10
11

int bits(int n, int m, int i, int j) {
    int max = ~0; /* All 1’s */ 
    // 1’s through position j, then 0’s 
    int left = max - ((1 << j) - 1); 
    // 1’s after position i 
    int right = ((1 << i) - 1); 
    // 1’s, with 0s between i and j 
    int mask = right | left; 
    // Clear i through j, then put m in there 
    return (n & mask) | (m << i); 
}

int bits(int n, int m, int i, int j) {
    int max = ~0; /* All 1’s */ 
    // 1’s through position j, then 0’s 
    int left = max - ((1 << j) - 1); 
    // 1’s after position i 
    int right = ((1 << i) - 1); 
    // 1’s, with 0s between i and j 
    int mask = right | left; 
    // Clear i through j, then put m in there 
    return (n & mask) | (m << i); 
}

Please note that , if the length of M starting the most significant 1, is bigger than abs(i-j), the extra bits will not be ignored. Instead, it will set 1’s outside the region of [i, j].

–EOF (The Ultimate Computing & Technology Blog) —