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).

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

Input: n = 1024, m = 21, i = 2, j = 6
Output: 1108
Explanation:
n's binary representation: 10000000000
m's binary representation: 10101
output's bin represention: 10001010100

i = 2, j = 6 
n = 1000| - - - - - | 00
        ^           ^
        6           2
n'= 1000| 1 0 1 0 1 | 00

Bits count start from left to right, starting with index 0.

Solution

Method 1 - Use Bit mask

Here are the steps we can follow:

  1. Create a Mask: Construct a mask to clear the bits from position ( i ) to ( j ) in ( N ).
    • 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.
  2. Shift ( M ): Align ( M ) to the correct position by shifting it left to start from bit ( i ).
  3. Combine ( N ) and ( M ): Apply the mask to ( N ), and then use the bitwise OR operation to combine the modified ( N ) with the shifted ( M ).

Code

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

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);
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def updateBits(N, M, i, j):
    # Create a mask to clear bits from i to j in N
    all_ones = ~0  # Sequence of all 1's

    # 1's before position j, followed by 0's
    left = all_ones << (j + 1)

    # 1's after position i
    right = (1 << i) - 1

    # All 1's, except for 0's between i and j
    mask = left | right

    # Clear bits j through i then put M in there
    N_cleared = N & mask
    M_shifted = M << i

    # OR N_cleared with M_shifted
    return N_cleared | M_shifted

Dry Run

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

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

References

stackoverflow