I've been trying to work through the first problem in CTCI, which involves bit manipulation, and I just can't figure out how the author accurately made the mask in his final solution. Could someone explain the calculations for "int left", "int right", and "int mask"? It would be great to see what these lines are calculating specifically for the example he provided.
The Question is: 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: Input: N = 10000000000, M = 10101, i = 2, j = 6 Output: N = 10001010100
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’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);
}
explain the calculations for "int left", "int right", and "int mask"
// 1’s through position j, then 0’s int left = max - ((1 << j) - 1);
(1 << j)
has just the bit at position j
set to 1
((1 << j) - 1)
(subtracting 1
) yields all j
bits below (to the right of) position j
set to 1
max - ((1 << j) - 1)
(subtracting from all 1) yields the bitwise complement of the above, i. e. all bits above (to the left of) and including position j
set to 1
, and the j
bits below set to 0
e. g.
j 1<<j (1<<j)-1 ~0-((1<<j)-1)
-------------------------------------------------------
0 000000000001 000000000000 111111111111
1 000000000010 000000000001 111111111110
2 000000000100 000000000011 111111111100
3 000000001000 000000000111 111111111000
4 000000010000 000000001111 111111110000
5 000000100000 000000011111 111111100000
6 000001000000 000000111111 111111000000
...
// 1’s after position i int right = ((1 << i) - 1);
(1 << i)
has just the bit at position i
set to 1
((1 << i) - 1)
(subtracting 1
) yields all i
bits below (to the right of) position i
set to 1
e. g.
i 1<<i (1<<i)-1
-------------------------------------
0 000000000001 000000000000
1 000000000010 000000000001
2 000000000100 000000000011
...
// 1’s, with 0s between i and j int mask = left | right;
i = 2, j = 6:
left 111111000000
right 000000000011
| ------------
mask 111111000011
// Clear i through j, then put m in there return (n & mask) | (m << i);
(n & mask)
, unlike commented, clears bits i
through j
-1 only (see mask
above)(m << i)
shifts the value to be set to the desired bit position(n & mask) | (m << i)
ORs the shifted value bits to the masked n
with your example:
n 010000000000
mask 111111000011
& ------------
n&mask 010000000000
m<<i 000001010100
| ------------
010001010100
Now, although this example values yield a correct result, we can see that the implementation of updateBits()
is actually wrong, because the left
part of the mask
needs 1
bits only to the left of and not including position j
, since bit position j
belongs to the substring that is to be masked out. The wrongness shows e. g. with the values n = 11111111111, m = 00000, i = 2, j = 6:
n 011111111111
mask 111111000011
& ------------
n&mask 011111000011
m<<i 000000000000
| ------------
011111000011
The value m has been put into bit positions i to j-1 only.
The error can be corrected by changing
int left = max - ((1 << j) - 1);
to
int left = max - ((1 << j+1) - 1);