Given a number $n$, $l$, and $r$ set all the bits of $n$ in the range of $l$ to $r$. Here, the indexing is from the rightmost bit (or LSB). The position of LSB is $1$.
Constraint: $1 <= l <= r <=$ bit count of $n$.
Example 1:
Example 2:
Input: $n=34$, $l=3$, $r=5$
Output: $62$
bin($34$) = $100010$
bin($62$) = $111110$
Setting bits of $34$ from 3rd to 5th position, we get $62$.
The idea here is to use bitmasking. The steps to solve the problem are as follows:
The bit mask that has set bits in the range [l,r] can be generated using the following expression.
(((1 << (l - 1)) - 1) ^ ((1 << r) - 1))
Let’s break the above expression into smaller expressions for our understanding.
Let’s understand the working of the above expression using an example.
Consider the following example.
Expression | Result | Binary form |
---|---|---|
(1 << (l - 1)) - 1 = (1 << 2) - 1 | 4 - 1 = 3 | 00011 |
(1 << r) - 1 = (1 << 5) - 1 | 32 - 1 = 31 | 11111 |
3 ^ 31 | 28 | 11100 |
So, the bit mask is $28$, such as $11100$.
Now, performing the bitwise OR i.e $n | mask$.
class Main{ static int generateMask(int l, int r){ int temp1 = (1 << (l - 1)) - 1; int temp2 = (1 << r) - 1; return (temp1 ^ temp2); } static int setBitsRange(int n, int l, int r) { int mask = generateMask(l, r); return (n | mask); } public static void main(String[] args) { int n = 34; int l = 3; int r = 5; System.out.println("Setting bits of " + n + " from positions " + l + " to " + r + " we get " + setBitsRange(n, l, r)); } }
generateMask()
method that accepts the range boundaries l
and r
. This method generates the bit mask using the logic mentioned above.setBitsRange()
method that generates the bit mask for given n
, l
, and r
by invoking
generateMask()
method and performs a bitwise OR of n
and the bit mask.setBitsRange()
method with n
, l
, and r
as parameters.RELATED TAGS
CONTRIBUTOR
View all Courses