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

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

How to set the leftmost unset bit in a number

Overview

Example

Code

Explanation