Posts First Set Bit (geeksforgeeks - SDE Sheet)
Post
Cancel

First Set Bit (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

Given an integer N. The task is to return the position of first set bit found from the right side in the binary representation of the number. Note: If there is no set bit in the integer N, then return 0 from the function.

geeksforgeeks

SOLUTION

APPROACH 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution
{
    public static int getFirstSetBit(int n){

        int idx = 1;

        while(n != 0){

            if( (n&1) != 0 ){
                return idx;
            }

            idx++;
            n = n >> 1;

        }

        return 0;

    }
}

APPROACH 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution
{

    public static int getFirstSetBit(int n){

        if(n == 0)
            return 0;

        // In two's complement, the negative of a number flips all the bits up to and including the first set bit (from the right),
        // and leaves the remaining bits unchanged.
        // By performing the bitwise AND operation between n and -n, all bits except the lowest set bit are turned to 0.
        int x = (n&-n);

        // by default, math.log(x) uses base e
        // we know, log2x = logx/log2, so we could do:
        int idx = (int)(Math.log(x)/Math.log(2));

        return idx + 1;

    }
}
This post is licensed under CC BY 4.0 by the author.