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 $14$, we’ll obtain an output of $15$. This is because $14$ in binary form is $1110$. When we set its rightmost unset bit, we get $1111$, that is, $15$.

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

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

CONTRIBUTOR

Ravi
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time