Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

java

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

Ravi

Problem statement

Given a number nn, ll, and rr set all the bits of nn in the range of ll to rr. Here, the indexing is from the rightmost bit (or LSB). The position of LSB is 11.

Constraint: 1<=l<=r<=1 <= l <= r <= bit count of nn.

Example 1:

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

Example 2:

  • Input: n=34n=34, l=3l=3, r=5r=5

  • Output: 6262

  • bin(3434) = 100010100010

  • bin(6262) = 111110111110

Setting bits of 3434 from 3rd to 5th position, we get 6262.

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=34n=34, l=3l=3, r=5r=5
  • Output: 6262
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 2828, such as 1110011100.

Now, performing the bitwise OR i.e nmaskn | mask.

  • n=34=100010n = 34 = 100010
  • mask=28=011100mask = 28 = 011100
  • nmask=62=111110n | 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) {
        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));
    }
}
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
RELATED COURSES

View all Courses

Keep Exploring