Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

java

How to find the position of the only set bit in an integer

Ravi

Problem statement

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

Solution

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

  1. 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.
  2. 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.
  3. 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].

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

Example 2

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.

Code example

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

Code explanation

  • 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
RELATED COURSES

View all Courses

Keep Exploring