Trusted answers to developer questions

Ravi

Given a number `n`

, find the position of the only set bit in the number. If more than one bits are set, then the output will be `-1`

.

Example 1

- Input:
`n = 8`

- Output:
`4`

Example 2

- Input:
`n = 15`

- Output:
`-1`

The solution to this problem is a simple algorithm that has the following three steps.

- We use
`n & n-1`

to unset the rightmost bit of the number. We do this because when we subtract one from an integer, all the bits following the rightmost set bit are inverted, turning 1 to 0 and 0 to 1. - We check if the result from step 1 becomes zero or not. If the result is not zero, then there are other bits set in the result and hence, the input number is invalid.
- If the result from step 1 becomes zero, then the input is valid and we can find the position of the only set bit using
`log_2(n) + 1]`

.

Consider n = 7

`n & (n-1)`

= `7 & 6`

= 6 (011)

As `n & (n-1)`

is not zero, that means there are more than one set bits in the number and the input is invalid.

Consider n = 4

`n & (n-1)`

= `4 & 3`

= 0

As `n & (n-1)`

is zero, that means the number has only one set bit.

Hence, the position of the only set bit is `log2(4)+1`

. that is, `2+1`

, which is `3`

.

public class Main { static int positionOfOnlySetBit(int n){ if((n & (n-1)) != 0) return -1; return (int) (Math.log(n) / Math.log(2)) + 1; } public static void main(String[] args) { int n = 7; int pos = positionOfOnlySetBit(n); if(pos == -1) System.out.println("Invalid input"); else System.out.println("The position of only set bit in " + n + " is " + pos); n = 8; pos = positionOfOnlySetBit(n); if(pos == -1) System.out.println("Invalid input"); else System.out.println("The position of only set bit in " + n + " is " + pos); } }

- Lines 3-6: We define the
`positionOfOnlySetBit()`

method to implement the solution above, to find the position of the only set bit. - Lines 8-18: We invoke the
`positionOfOnlySetBit()`

method for different`n`

values.

RELATED TAGS

java

CONTRIBUTOR

Ravi

RELATED COURSES

View all Courses

Keep Exploring

Related Courses