Problem
You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to set all bits between i and j in N equal to M (e.g., M becomes a substring of N located at i and starting at j).
**Example **
Consider the integer N, where we want to fit in M between bits i and j of N.
Input: N = 10000000000, M = 10101, i = 2, j = 6 Output: N = 10001010100
i=2 j = 6 1000 | ----- | 00
6 2
```Bits count start from left to right, starting with index 0.
Solution
**Method 1**
* Set the bits being modified to 0 via the mask
* Set the bits being modified to the values of m via the `| (m << i)`
int fitInteger(int n,int n, int i, int j)
{
/* bitwise not of (1s from j to the end) - (1s from i to the end) */
unsigned int mask = ~ ( ((1 « (j-i)) - 1) - ((1 « i) - 1) );
return (n & mask ) | (m « i);
}
Writing in simpler terms:
Logic is basically to create a mask that consists of 1's in all positions except from position i to position j.
* Create a mask with 1s but only 0s between positions i and j. AND the mask with N to clear the bits between i and j to 0s.
* Create another mask with 0s but only 1s between positions i and j. AND the mask with M to clear the bits outside i and j to 0s.
* OR N and M.
public static int updateBits(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);// here should be j+1 not j.
// 1's after position i
int right = ((1 << i) - 1);
// 1's with 0s between i and j
int mask = left | right;
// Clear i through j, then put m in there
return (n & mask) | (m << i);
}
Dry running the program:
N = 1010 1011 1101 1110
M = 1001 0110
i = 4, j = 11. i.e : should be doing: 1010|—- —-|1110
11 4
max = 1111 1111 1111 1111
left(j) = 1111 1000 0000 0000
right(i) = 0000 0000 0000 0111
mask = 1111 1000 0000 0111
//Computing left = max - ((1 « (j+1)) - 1)
-———————— left —————————–
(1«(j+1)) 0001 0000 0000 0000 //shift 1 - 12 times as j+1 is 12
1 0000 0000 0000 0001 - // minus
——————-
(temp) 0000 1111 1111 1111
(max) 1111 1111 1111 1111
(temp) 0000 1111 1111 1111 - // minus
——————-
(left) 1111 0000 0000 0000
-———————————————————–
//Computing right=((1 « i) - 1);
-———- right ———– —————————–
(1«i) 0000 0000 0001 0000 //left rotate 1 4 times (as i=4)
1 0000 0000 0000 0001 - // minus
——————-
(right) 0000 0000 0000 1111
-———————————————————–
//Compute mask = left | right
(left) 1111 0000 0000 0000
(right) 0000 0000 0000 1111 |
——————-
(mask) 1111 0000 0000 1111
-———————————————————–
//Compute result = (n & mask) | (m « i)
-—————————- —————————-
(n) 1010 1011 1101 1110
(mask) 1111 0000 0000 1111 & //and operator
——————-
(tmp1) 1010 0000 0000 1110
——————-
(tmp1) 1010 0000 0000 1110
(m«i) 0000 1001 0110 0000 | //or operator
(result) 1010 1001 0110 1110
-————————————————————
Reference - [stackoverflow](http://stackoverflow.com/questions/6507102/fitting-one-integer-in-another)