Related Tags

java

# How to set all bits in the given range of a number

Ravi

## Problem statement

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:

• Input: $n=14$, $l=1$, $r=4$
• Output: $15$

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

## Solution

The idea here is to use bitmasking. The steps to solve the problem are as follows:

1. Generate a bit mask that has set bits in the range [l,r].
2. Perform a bitwise OR of the mask and the given number.

### How to generate the mask?

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.

1. (1 << (l - 1)) - 1
2. (1 << r) - 1
3. Step 1 ^ Step 2

Let’s understand the working of the above expression using an example.

Consider the following example.

• Input: $n=34$, $l=3$, $r=5$
• Output: $62$
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$.

• $n = 34 = 100010$
• $mask = 28 = 011100$
• $n | mask = 62 = 111110$

### Code

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) {
}

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));
}
}
Java code to set bits in the given range

### Explanation

• Lines 3–7: We define the generateMask() method that accepts the range boundaries l and r. This method generates the bit mask using the logic mentioned above.
• Lines 9–12: We define the 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.
• Line 18: We invoke the setBitsRange() method with n, l, and r as parameters.

RELATED TAGS

java

CONTRIBUTOR

Ravi
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time