Trusted answers to developer questions

Ravi

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 11**1**0.

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`

.

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.

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

- 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

CONTRIBUTOR

Ravi

RELATED COURSES

View all Courses

Keep Exploring

Related Courses