Solution Review: Get The First Set Bit Position Using the Left 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 & (1 << (k - 1))) == 0)
increment the pointerk
. - Else, return
k
- If
Pseudocode
The above algorithm representation in pseudocode is as follows:
if(n == 0) return;
k = 1
while(true) {
if((n & (1 << (k - 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 & (1 << (k - 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 & (1 << (k - 1))) == 0) :
k+=1
else:
return k
print("First setbit position for number: 18 is -> ", helper(18))
print("First setbit position for number: 18 is -> ", helper(5))
print("First setbit position for number: 18 is -> ", helper(32))
JavaScript
const FirstSetBitPosition = (number) => {
function helper (n) {
if(n === 0) {
return 0;
}
let k = 1;
while (true) {
if((n & (1 << (k - 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 & (1 << (k - 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 & (1 << (k - 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)
time, 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.