How to get the position rightmost unset bit

Overview

Given a number, we’ll find the index/position of its rightmost unset bit. The indexing is from right to left, where the rightmost bit position starts from 1.

Example 1:

Input: 14
Output: 1

In this example, 14 in binary form is 1110. The rightmost unset bit position is 1 which is 1110.

Example 2:

Input: 15
Output: -1

In this example,15 in binary form is 1111. There aren’t set bits. Hence, the output is -1.

Method

The steps of the algorithm are as follows:

Corner case: If the input number (n) is zero, then return 1.
Corner case: If the input number has no unset bits, then return -1.
Perform a bitwise NOT on n, which is one’s complement of n. Now, the unset bits become set.
Now, the problem is changed to finding the position of the rightmost set bit.

Note: Refer to How to find the position of the rightmost set bit of an integer? to implement step 4.

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

Example

class Main{
    static int positionOfRightmostSetBit(int n) {
        return (int)((Math.log10(n & -n)) / Math.log10(2)) + 1;
    }
    static int positionOfRightmostUnsetBit(int n) {
        if (n == 0) return 1;
        if ((n & (n + 1)) == 0) return -1;
        return positionOfRightmostSetBit(~n);
    }
    public static void main(String args[]) {
        int n = 14;
        System.out.print("The position of rightmost unset bit of " + n + " is " + positionOfRightmostUnsetBit(n));
    }
}

Finding the index/position of its rightmost unset bit

How to get the position rightmost unset bit

Overview

Method

Example

Explanation