Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

bitwise

How to set the rightmost unset bit in a number

Ravi

Overview

In this shot, we’re going to look at how to set the rightmost unset bit of an input number and return the number obtained.

For example, given an input of 1414, we’ll obtain an output of 1515. This is because 1414 in binary form is 11101110. When we set its rightmost unset bit, we get 11111111, that is, 1515.

As another example, we get an output of 77 when we provide an input of 77. This is because 77 in binary form is 111111. There are no unset bits in the binary representation of 77. Hence, the value returned is also 77.

Note: Refer to How to check if all bits are set in a number? to check if all bits in a number are set.

Test expression

Now, let’s test the following expression:

n | (n + 1)

The above expression sets the rightmost unset bit. But it may set a leading zero bit if the given number doesn’t contain any unset bits. For example, consider setting n=7 in the above function:

Expression Result
n=7 0111
n+1=8 1000
n (n + 1)

Though there are no unset bits in 77, the expression n | (n + 1) still sets the rightmost unset bit.

Hence, it’s essential first to check if there are no unset bits in the given number.

Code

class Main{

    static int setRightmostUnsetBit(int n){
        if((n & (n+1)) == 0) return n;
        return (n | (n+1));
    }

    public static void main(String[] args) {
        int n = 8;
        System.out.println("Setting the rightmost unset bit of " + n + " we get " + setRightmostUnsetBit(n));
    }
}
Setting the rightmost unset bit

Explanation

  • Lines 3–6: We define the setRightmostUnsetBit() such that it implements the solution discussed above to set the rightmost unset bit of n.
  • Line 9: We define n.
  • Line 10: We call setRightmostUnsetBit() with n as a parameter.

RELATED TAGS

bitwise
RELATED COURSES

View all Courses

Keep Exploring