# Solution Review: Get the First Set Bit Position Using the Right Shift

In the kth bit set/unset problem, we first write the algorithm, then some pseudocode, and then implement the solution.

## Table of Contents

In this lesson, we try to solve this algorithm using the left shift operator. Try solving it on your own.

## Solution review

Imagine we check the right-most significant bit to see if the bit and `&`

operation of `1`

yields to `1`

.

In other words, we shift bits until the right MSB and `&`

operation with `1`

, and it yields `1`

.

### Algorithm

- If
`n == 0`

, return. - Initialize
`k = 1`

- Loop
- If
`((n >> (k - 1)) & 1) == 0`

increment the pointer`k`

. - Else, return
`k`

- If

### Pseudocode

The above algorithm representation in pseudocode is as follows:

```
if(n == 0) return;
k = 1
while(true) {
if(((n >> (k - 1)) & 1) == 0)
increment k
else {
return k
}
}
```

## Solution

Here is the logic behind this solution.

### Java

```
class FirstSetBitPosition {
private static int helper(int n) {
if (n == 0) {
return 0;
}
int k = 1;
while (true) {
if (((n >> (k - 1)) & 1) == 0) {
k++;
} else {
return k;
}
}
}
public static void main(String[] args) {
System.out.println("First setbit position for number: 18 is -> " + helper(18));
System.out.println("First setbit position for number: 5 is -> " + helper(5));
System.out.println("First setbit position for number: 32 is -> " + helper(32));
}
}
```

### Python

```
def helper(n):
if(n == 0):
return 0
k=1
while True:
if(((n >> (k - 1))& 1) == 0):
k+=1
else:
return k
print("First setbit position for number : 18 is -> ",helper(18))
print("First setbit position for number : 5 is -> ",helper(5))
print("First setbit position for number : 32 is -> ",helper(32))
```

### JavaScript

```
const FirstSetBitPosition = (number) => {
function helper (n) {
if(n === 0) {
return 0;
}
let k = 1;
while (true) {
if(((n >> (k - 1)) & 1) === 0) {
k++;
}else {
return k;
}
}
}
return helper (number);
}
console.log (`First setbit position for number: 18 is -> ${FirstSetBitPosition (18)}`);
console.log (`First setbit position for number: 5 is -> ${FirstSetBitPosition (5)}`);
console.log (`First setbit position for number: 32 is -> ${FirstSetBitPosition (32)}`);
```

### C++

```
#include <iostream>
using namespace std;
int helper(int n) {
if (n == 0) {
return 0;
}
int k = 1;
while (true) {
if (((n >> (k - 1)) & 1) == 0) {
k++;
} else {
return k;
}
}
}
int main() {
cout << "First setbit position for number: 18 is -> " << helper(18) << endl;
cout << "First setbit position for number: 5 is -> " << helper(5) << endl;
cout << "First setbit position for number: 32is -> " << helper(32) << endl;
return 0;
}
```

### TypeScript

```
export const FirstSetBitPosition = (n: number): number => {
function helper(value: number): number {
if (value === 0) {
return 0;
}
let k: number = 1;
while (true) {
if (((value >> (k - 1)) & 1) === 0) {
k++;
} else {
return k;
}
}
}
return helper(n);
}
console.log(`First setbit position for number: 18 is -> ${FirstSetBitPosition(18)}`);
console.log(`First setbit position for number: 5 is -> ${FirstSetBitPosition(5)}`);
console.log(`First setbit position for number: 32 is -> ${FirstSetBitPosition(32)}`);
```

## Complexity analysis

### Time Complexity:

`O`

`(1)`

, this is always constant time as we are dealing with the bit representation of the decimals or ASCII. They are represented in either 32 or 64 bits.

### Space Complexity:

`O(1)`

extra space, as we are not using any extra space in our code.

## Gopi Gorantala Newsletter

Join the newsletter to receive the latest updates in your inbox.