Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

bitwise

How to set the leftmost unset bit in a number

Ravi

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));
    }
}
Try it out!

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 with n as the parameter.

RELATED TAGS

bitwise
RELATED COURSES

View all Courses

Keep Exploring