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.

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`

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.

Data Structures and AlgorithmsBit Manipulation

Gopi is an engineering leader with 12+ of experience in full-stack development—a specialist in Java technology stack. He worked for multiple startups, the European govt, and FAANG in India and Europe.

Members Public

Leetcode 217: Contains Duplicate

This question marks the first problem when working on duplicate data, either integers or strings etc. Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies. Problem statement Given an integer array nums, return true if any

Members Public

Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews. Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe,

Members Public

Bit Manipulation Course Overview

Overview In this course, you will learn how to solve problems using bit manipulation, a powerful technique that can be used to optimize your algorithmic and problem-solving skills. This is one of the most important/critical topics when someone starts preparing for coding interviews for FAANG companies. To kick things