How to set the leftmost unset bit in a number
Overview
A leftmost unset bit is the first unset bit after the most significant bit of a number.
Given a number n, we’ll set the leftmost unset bit of n. If there are no unset bits in the number, then return it as it is.
Example 1:
- Input: n=23
- Output: 31
Example 2:
- Input: n=5
- Output: 7
Example 3:
- Input: n=15
- Output: 15
Example
First, we check if all bits of the number are set using How to check if all bits are set in a number?.
Only if there are unset bits do we proceed. Otherwise, we return the input number as is.
The idea here is to find the position of the leftmost unset bit using the logic described in How to get the position of a leftmost unset bit?. Then generate a bit mask where the position of the leftmost unset is set, and all other bits are unset. Finally, perform bitwise OR on the bit mask and the input number.
Code
Let's view a code example.
class Main{
static int positionOfLeftmostUnsetBit(int n){
int pos = 0;
int temp = n;
int count = 0;
while(temp > 0){
if((temp & 1) == 0) pos = count;
temp = temp >> 1;
count++;
}
return pos;
}
static int setLeftmostUnsetBit(int n) {
if ((n & (n + 1)) == 0) return n;
int position = positionOfLeftmostUnsetBit(n);
int bitMask = 1 << position;
return (n | bitMask);
}
public static void main (String[] args) {
int n = 5;
System.out.println("Setting the leftmost unset bit of " + n + " we get " + setLeftmostUnsetBit(n));
}
}Explanation
- Lines 3-14: We’ll use the
positionOfLeftmostUnsetBit()method to get the position of the leftmost unset bit. - Lines 16-21: We’ll define the
setLeftmostUnsetBit()method that sets the leftmost unset bit by performing a bitwise OR on the bit mask and the input number. - Line 24: We’ll define the
n. - Line 25: We’ll call the
setLeftmostUnsetBit()method withnas the parameter.
RELATED TAGS
CONTRIBUTOR
View all Courses
