Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

bitwise

How to get the position rightmost unset bit

Ravi

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:

  1. Corner case: If the input number (n) is zero, then return 1.
  2. Corner case: If the input number has no unset bits, then return -1.
  3. Perform a bitwise NOT on n, which is one’s complement of n. Now, the unset bits become set.
  4. 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

Explanation

  • Lines 3–4: We’ll define the positionOfRightmostSetBit() method that returns the position of the rightmost set bit.
  • Lines 7–11: We’ll define the positionOfRightmostUnsetBit() method to implement the above solution to find the rightmost unset bit of the number.
  • Line 14: We’ll define n.
  • Line 15: We’ll invoke the positionOfRightmostSetBit() with n.

RELATED TAGS

bitwise
RELATED COURSES

View all Courses

Keep Exploring