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.
Table of Contents
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 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 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.
Gopi Gorantala Newsletter
Join the newsletter to receive the latest updates in your inbox.