Creating a mask around a subsection [i,j] for a number

Question

I'm learning bit manipulation and bitwise operators currently and was working on a practice problem where you have to merge a subsection[i,j] of an int M into N at [i,j]. I created the mask in a linear fashion but after googling i found that ~0 << j | ((1 << i) - 1) creates the mask I wanted. However, I am not sure why. If anyone could provide clarification that would great, thanks.

void merge(int N, int M, int i, int j){
    int mask = ~0 << j | ((1 << i) - 1);
    N = N & mask; // clearing the bits [i,j] in N
    mask = ~(mask); // inverting the mask so that we can isolate [i,j] in 
//M
    M = M & mask; // clearing the bits in M outside of [i,j]
    // merging the subsection [i,j] in M into N at [i,j] by using OR
    N = N | M; 
}

duplicates: [What is the best practice way to create a bitmask for a range of bits?](https://stackoverflow.com/q/21465833/995714), [Masking bits within a range given in parameter in C](https://stackoverflow.com/q/28035794/995714), [uint64_t setting a range of bits to 1](https://stackoverflow.com/q/48436659/995714), [Fastest way to produce a mask with n ones starting at position i](https://stackoverflow.com/q/39321580/995714), [Obtain a specific subset of bits of an int in Java](https://stackoverflow.com/q/16001819/995714), [set the m-bit to n-bit](https://stackoverflow.com/q/15917454/995714) — phuclv, Jun 09 '19 at 02:08

score 1 · Answer 1 · answered Jun 08 '19 at 18:44

~0 is the "all 1 bits" number. When you shift it up by j, you make the least significant j bits into 0:

1111111111111111  ==  ~0  ==  ~0 << 0
1111111111111110  ==  ~0 << 1
1111111111100000  ==  ~0 << 5
1111111110000000  ==  ~0 << 7

1 << i is just the i + 1th least significant bit turned on.

0000000000000001  ==  1 << 0
0000000000000010  ==  1 << 1
0000000000001000  ==  1 << 3
0000000001000000  ==  1 << 6

When you subtract 1 from this, there is a one carried all the way from the left, so you are left with all the bits before the 1 bit becoming 1 (So you end up with the first i least significant bits turned on).

0000000000000000  ==  (1 << 0) - 1
0000000000000001  ==  (1 << 1) - 1
0000000000000111  ==  (1 << 3) - 1
0000000000111111  ==  (1 << 6) - 1

When you or them, you end up with a window between the jth least significant bit and the i + 1th least significant bit turned on (inclusive).

1111111110000000  ==  ~0 << 7
0000000000000111  ==  (1 << 3) - 1
1111111110000111  ==  ~0 << 7 | ((1 << 3) - 1)
         7   3

When you & a number with this mask, you clear the bits in the range (i, j] (The ith bit itself is not included).

When you ~ the mask, you get a new mask that will only give you the bits in the range (i, j].

1111111110000111  ==  ~0 << 7 | ((1 << 3) - 1)
0000000001111000  ==  ~(~0 << 7 | ((1 << 3) - 1))

Which could also be constructed with something like ((1 << j) - 1) & ~((1 << i) - 1).

Creating a mask around a subsection [i,j] for a number

1 Answers1

Linked