Problem Statement

Sometimes, it becomes essential to check whether a specific bit is set (equals 1) or not in a binary representation of a number. Let's consider the problem of determining if the k'th bit is set in a given number. Given an integer num and a positive integer k, our task is to find out whether the k'th bit is set or not.

Understanding the Problem

Consider the following scenario:

Input: num = 21, k =3

Our goal is to check if the 3rd bit (from the right, considering 0-based index) is set in the binary representation of 21.
Binary representation of 21: 10101.
Here, the 3rd bit is set (equals 0). So, for the given input, the expected output should be false.

Solution

To solve this problem efficiently, we can use bitwise AND operation (&) along with the left shift operation (<<).

The idea is to create a mask with the k'th bit set and then perform a bitwise AND operation with the given number. If the result is not zero, then the k'th bit is set; otherwise, it is not set.

#include <iostream>

bool isKthBitSet(int num, int k) {
    // Create a mask with the k'th bit set
    int mask = 1 << k;

    // Perform bitwise AND operation
    // If result is not zero, k'th bit is set
    return (num & mask) != 0;
}

int main() {
    // Example usage
    int num = 21, k = 3;
    
    // Check if the k'th bit is set
    if (isKthBitSet(num, k)) {
        std::cout << "The " << k << "'th bit is set in " << num << std::endl;
    } else {
        std::cout << "The " << k << "'th bit is not set in " << num << std::endl;
    }

    return 0;
}

// Output
The 3'th bit is not set in 21

Complexity Analysis:

• Time Complexity:O(1) Each operation is constant time.
• Space Complexity:O(1) No extra space used.