How to find the position of the rightmost set bit of an integer

Problem statement

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

Example 1

  • Input: 14
  • Output: 2

Note: The value of 14 in binary form is 1110. The rightmost set bit position is 2.

Example 2

  • Input: 15
  • Output: 1

Note: The value of 15 in binary form is 1111. The rightmost set bit position is 1, meaning 1111.

Solution

The steps of the algorithm are as follows:

  1. Unset the rightmost bit of number n.
  2. XOR the result of step 1 with n.
  3. Find the position of the only set bit.

All the steps above can be skipped if the number is odd as odd numbers always have the rightmost bit/LSB set or 1.

Step 1: Unset the rightmost bit of number n

To unset the rightmost bit of number n:

  1. Subtract one from n. The idea is that when we subtract one from an integer, all the bits following the rightmost set bits are inverted, turning 1 to 0 and 0 to 1.
  2. Perform AND (&) operation on the result of step 1 and n.

Code wise: n & (n - 1)

Let’s see an example:

Consider n = 18,

Operation Result
18 10010
18 - 1 = 17 10001
18 & 17 (n & (n - 1)) 10000

As we can see, the result of (n & (n - 1)) is 10000.

Step 2: XOR the result of step 1 with n

Now we XOR the result from step 1 with n itself. This step results in the rightmost set bit in n the only set bit.

Continuing the example above:

(n & (n - 1)) ^ n = 10000 ^ 10010 = 00010.

Step 3: Find the position of the only set bit

The result from step 2 is 00010. In order to find the position of the only set bit, we can do it in two ways.

  1. Log(result) + 1
  2. Use right shift operator by keeping a counter until the number becomes zero.

Code

public class Main {
    static int findOnlySetBitPos(int n){
        return (int)((Math.log10(n)) / Math.log10(2)) + 1;
    }
    static int positionOfRightmostSetBit(int num){
        if((num & 1) != 0) return 1;
        // Step 1
        int andOp = num & (num - 1);
        // Step 2
        int xorOp = num ^ andOp;
        // Step 3
        return findOnlySetBitPos(xorOp);
    }
    public static void main(String[] args) {
        int num = 18;
        System.out.println("Position of the rightmost set bit of " + num + " is " + positionOfRightmostSetBit(num));
        num = 7;
        System.out.println("Position of the rightmost set bit of " + num + " is " + positionOfRightmostSetBit(num));
    }
}

Explanation

  • Lines 3–4: We define the findOnlySetBitPos() method. It returns the position of the only set bit.
  • Lines 7–16: We define the positionOfRightmostSetBit() method. It implements the solution above to return the position of the rightmost set bit.
  • Lines 18–23: We define the main() method where positionOfRightmostSetBit() is invoked for different n values.

Free Resources

License: Creative Commons-Attribution NonCommercial-ShareAlike 4.0 (CC-BY-NC-SA 4.0)