# Check If Kth Bit Is Set/Unset Using Left Shift

In the kth bit set/unset problem, we need to write a program that checks whether the kth bit of a number is either 1 or 0.

In this lesson, we try to find a bit in the binary representation of a number at the kth position and check if it is set/un-set.

## Introduction

In this question, input a number and check whether the kth bit is set.

## Problem statement

Given two positive integers `n` and `k` check whether the bit at position k, from the right in the binary representation of n, is set `1` or unset `0`.

``````Input: n = 5, k = 1

Output: true``````
``````Input: n = 10, k = 2

Output: true``````
``````Input: n = 10, k = 1

Output: false``````

## Algorithm

• If `n == 0` return;
• Initialize `k = 1`
• Loop
• If `(n & (1 << (k - 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 & (1 << (k - 1))) == 0)
increment k
else {
return k
}
}
``````

## Solution

Here is the logic for 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 : 5 is -> ",helper(5))
print("First setbit position for number : 32 is -> ",helper(32))
``````

### JavaScript

``````function checkKthBitSet(n) {
if (n === 0) {
return 0;
}

let k = 1;

while (true) {
if ((n & (1 << (k - 1))) === 0) {
k++;
} else {
return k;
}
}
}

console.log("First setbit position for number: 18 is -> " + checkKthBitSet(18));
console.log("First setbit position for number: 5 is -> " + checkKthBitSet(5));
console.log("First setbit position for number: 32 is -> " + checkKthBitSet(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 helper = (n: number): number => {
if (n === 0) {
return 0;
}

let k: number = 1;

while (true) {
if ((n & (1 << (k - 1))) === 0) {
k++;
} else {
return k;
}
}
}

console.log("First setbit position for number: 18 is -> " + helper(18));
console.log("First setbit position for number: 5 is -> " + helper(5));
console.log("First setbit position for number: 32 is -> " + helper(32));``````

### Complexity analysis

#### Time Complexity

`O``(1)`, this is always constant time, as we deal 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.

## Optimal solution (refactored)

### Java

``````class CheckKthBitSetOrNot {
private static boolean checkKthBitSet(int n, int k) {
return (n & (1 << (k - 1))) != 0;
}

public static void main(String[] args) {
System.out.println("n = 5, k = 3 : " + checkKthBitSet(5, 3));
System.out.println("------------");
System.out.println("n = 10, k = 2 : " + checkKthBitSet(10, 2));
System.out.println("------------");
System.out.println("n = 10, k = 1 : " + checkKthBitSet(10, 1));
}
}``````

### Python

``````def checkKthBitSet(n,k):
return (n & (1 << (k- 1))) !=0
print("n=5,k=3  : ",checkKthBitSet(5,3))
print("--------------------")
print("n=10,k=2 : ",checkKthBitSet(10,2))
print("--------------------")
print("n=10,k=1 : ",checkKthBitSet(10,1))``````

### JavaScript

``````const checkKthBitSet = (n, k) => {
return (n & (1 << (k - 1))) !== 0;
}

console.log ("n = 5, k = 3 : " + checkKthBitSet (5, 3));
console.log ("------------");
console.log ("n = 10, k = 2 : " + checkKthBitSet (10, 2));
console.log ("------------");
console.log ("n = 10, k = 1 : " + checkKthBitSet (10, 1));``````

### C++

``````#include <iostream>
#include <string>
using namespace std;

string checkKthBitSet(int n, int k) {
return (n & (1 << (k - 1))) != 0 ? "true" : "false";
}

int main() {
cout << "n = 5, k = 3 :  " << checkKthBitSet(5, 3) << endl;
cout << "-------------" << endl;
cout << "n = 10, k = 2 : " << checkKthBitSet(10, 2) << endl;
cout << "-------------" << endl;
cout << "n = 10, k = 1 : " << checkKthBitSet(10, 1) << endl;
cout << "-------------" << endl;
return 0;
}
``````

### TypeScript

``````export const checkKthBitSet = (n: number, k: number): boolean => {
return (n & (1 << (k - 1))) !== 0;
}

console.log("n = 5, k = 3 : " + checkKthBitSet(5, 3));
console.log("------------");
console.log("n = 10, k = 2 : " + checkKthBitSet(10, 2));
console.log("------------");
console.log("n = 10, k = 1 : " + checkKthBitSet(10, 1));``````

### Explanation

We used the left shift operation to shift the bits to kth position and then used the `&` operation with number `1` and check if it is not-equals to `0`.

Let’s see these in 32-bit binary representation

Case #1:

``````Input n = 5, k = 3

n    = 5 = 00000000 00000000 00000000 00000101
1    = 1 = 00000000 00000000 00000000 00000001
k    = 3 = 00000000 00000000 00000000 00000011
(k - 1) = 2 = 00000000 00000000 00000000 00000010``````

Now shift `1` with `(k - 1)` positions. We are shifting the number `1` two-bit positions to the left side.

``(1 << (k - 1)) = 4 = 00000000 00000000 00000000 00000100``

Now, doing `&` operation of `n` and `(1 << (k - 1))` will give us a decimal number. If that is not equal to `0`, then the bit is set, and we return `true`.

Finally, let’s see this in action.

``````         n         = 5 = 00000000 00000000 00000000 00000101
1 << (k - 1))   = 4 = 00000000 00000000 00000000 00000100
-------------------------------------------------------------n & (1 << (k - 1)) = 4 = 00000000 00000000 00000000 00000100
-------------------------------------------------------------``````

So, `n & (1 << (k - 1)) = 4`, which is not `0`, so we return true.

### Complexity analysis

#### Time Complexity

`O``(1)`, this is always constant time, as we deal with the bit representation of the decimals or ASCII. They are represented in either 32/64 bits.

#### Space Complexity

`O(1)` extra space, as we are not using any extra space in our code.

We can solve this problem using the right shift as well. We will see how to solve the same problem using the `>>` operator in the next chapter.

Coding Interview QuestionsData 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