Code is like humor. When you have to explain it, it's bad.

Set Bits in Range

Welcome back, dear reader. So, in this article, we will discuss a
very interesting problem called SET
BITS IN RANGE. So, what does this
question say? We are given two binary numbers A and B. We will also be given
a range i.e. left and right. We have to set all the bits of B in the range left to
right only at those places where the bits of A are set. What do we mean by
this? Look at the image given below:

As shown in the figure above, we have set only those bits in B which were lying
in the range and the corresponding bits in A were also set. For instance, the bit
at position 3 in B was set because it was in the range, and the bit at position 3
in A was also set. We did not set the bit at position 6 in B although it was lying
in the range because the bit at position 6 in A was not set. So, we have to set
the bits which are in range and corresponding bits in A are also set for them.
The rest of the bits of B will remain the same.

We hope that you have understood the question now. If you still have any
doubts regarding the question, refer to the SET BITS IN A RANGE VIDEO to clear all your doubts regarding
the question. We recommend you try
to solve this problem on your own first and then refer to the solution to
understand the concepts in depth.

We will first create a mask that will have all the bits set in the range
provided to us.

We will take the AND of this mask with A. This will give us all the bits in A
within the range and the rest all the bits which are not in the range will
be zero.

We will take the OR of this mask that we have obtained from step-2
above with complete binary number B. This will give us our desired
output.

Explanation:

We hope that you have already understood the question and have also tried to
solve the problem once yourself. Now let us discuss this problem. See, we have
to set only the bits in a particular range. This means that we do not need the
entire binary number A to check which of its bits are set; rather, we need only
the part of A which lies in the range.

Have a look at the image given below:

What have we done here? We have somehow created a mask from A in such a
way that all the bits in the range are copied from A whereas all the other bits
that are not in the range are 0.

In the second step, we have taken the OR of this mask with B. So, the bits that
are not in range will directly be copied from B as we have 0 '''s at those
positions in the mask and either 0 or 1 OR 0 is always the bit itself.

The bits that are in the range undergo the logical OR operation with the
corresponding bits of A stored in the mask. So, if a bit in A is 0, the bit of B will
be copied to the answer whether it is 0 or 1. If a bit is 1 in A, 1 will be copied in
our answer whether the bit in B is 0 or 1. (This is the basic property of logical
OR)

So, this is what we have to do. So, this question is not so difficult, is it? Wait!!!

We have not yet talked about the mask that we got. How did we get the mask?
Have a look at the image given below:

We have generated a mask0. This mask has all the bits 1 in the given range.
When we take the AND of this mask with A, all the bits that are not in range
become 0 as whatever may be the bits in A, the bits at those positions in
mask0 are 0 and 1 or 0 AND 0 is 0. Now, the bits in the range are 1 in mask0.
This means that the bits that will be copied in mask 1 depend on the bits in A.
If the bit at a particular position in A is 0, 0 will be copied to mask1 and if it is 1,
1 will be copied to mask1. (This is the basic property of logical AND).

So, we have now understood how we have generated mask1 and we have
already talked about the procedure of generating the solution from B and
mask1.

Focus

What do you think has been the focus of this question till here? The question is
not too difficult. It focuses on the fact that in the case of AND, '0' is dominant
as whatever may be the other bit, if one bit is 0, the answer will be 0. Similarly,
in the case of OR, '1' is dominant as whatever may be the other bit, the answer
will be 1 if one bit is 1.

So dear leader we hope that you have understood the procedure till here. If
you have any doubts about it you may refer to the solution video to
understand the procedure completely.

So we used mask0 to produce mask1. Now, we will have a look at the
procedure of creating mask0.

Have a look at the image given below.

In the image above, we can see how we have generated the mask0. We have
taken binary number 1 as mask m. We have also calculated the range which is
given by right minus left plus one. Then we have left-shifted the mask m by the
range. After this, we have subtracted 1 from the mask obtained above and
then we have left-shifted this mask by left-1 and we got the mask0.

We recommend you watch the solution video to understand the
above procedure completely.

So, dear reader, this was the whole procedure that we are going to follow. We
have discussed everything in detail above as well as in the solution video. We hope that you have
understood everything. The code for this is really
simple if you have understood the process completely. We strongly
recommend that you try to code this yourself and then have a look at the code
below:

import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scn = new Scanner(System.in);
int a = scn.nextInt();
int b = scn.nextInt();
int left = scn.nextInt();
int right = scn.nextInt();
int mask = (1 << (right - left + 1)) - 1;
mask = ((mask << (left - 1)) & a);
b |= mask;
System.out.println(b);
}
}

java;
true";

Time and Space Complexity Analysis

Time Complexity:

O(1) because we have just performed some bitwise
operations which take constant time.

Space Complexity:

O(1) because we have not used any extra memory.

So, dear reader, we hope that you have understood the complete procedure
and the code also. If you still have any doubts about them, refer to the
complete solution video. With this, we have completed this problem.

Suggestions:

Here are some suggestions from our side that you do not want to miss

We recommend you watch the solution video once. This will help you
understand every concept in depth.

We also recommend that you try to solve this problem by another
method too, where we can traverse every bit to solve this problem.
Think about this solution. So, keep practicing and moving forward. Till
then, Happy Coding!!!