Trusted answers to developer questions

Ravi

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.

- Input:
`14`

- Output:
`2`

Note: The value of

`14`

in binary form is`1110`

. The rightmost set bit position is`2`

.

- Input:
`15`

- Output:
`1`

Note: The value of

`15`

in binary form is`1111`

. The rightmost set bit position is`1`

, meaning 111`1`

.

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`

.

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

.

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

.

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.

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)); } }

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

RELATED TAGS

java

CONTRIBUTOR

Ravi

RELATED COURSES

View all Courses

Keep Exploring

Related Courses