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