## Friday, March 21, 2014

### Set all bits of a number in a range equal to another number

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 |
-------------------
------------------------------------------------------------
//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