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:

Unset the rightmost bit of number n.
XOR the result of step 1 with n.
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:

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.
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.

Log(result) + 1
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));
    }
}

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

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments