Check whether the Kth bit of a number is set or not

Given a number n and a position k, determine whether the k-th bit of n (from the right, starting from 1) is set to 1 or not. The k-th bit is set if it is 1, otherwise, it is unset (0).

Input/Output Examples

plaintext
Example 1:
Input:
n = 18
k = 2
Output:
True
Explanation: The binary representation of 18 is 10010, and the 2nd bit (from the right) is 1, so the k-th bit is set.

Example 2:
Input:
n = 12
k = 3
Output:
True
Explanation: The binary representation of 12 is 1100, and the 3rd bit (from the right) is 1, so the k-th bit is set.

Example 3:
Input:
n = 8
k = 2
Output:
False
Explanation: The binary representation of 8 is 1000, and the 2nd bit is 0, so the k-th bit is not set.

Approach to Check Whether K-th Bit is Set or Not

  1. Bit Manipulation Using Shift Operation:
    • The idea is to use a bitwise AND operation to check the k-th bit.
    • First, shift 1 left by k-1 positions to create a mask where only the k-th bit is 1 and the rest are 0.
    • Then, perform a bitwise AND between n and this mask. If the result is non-zero, the k-th bit is set; otherwise, it is not set.
  2. Edge Case:
    • If k is greater than the number of bits in n, return False as there are no bits in that position.

C++ Program to Check Whether K-th Bit is Set or Not

cpp
#include <iostream>
using namespace std;

// Function to check if the k-th bit is set
bool isKthBitSet(int n, int k) {
    // Shift 1 to the left by (k-1) positions and perform AND with n
    return (n & (1 << (k - 1))) != 0;
}

int main() {
    int n = 18, k = 2;
    if (isKthBitSet(n, k)) {
        cout << "The " << k << "-th bit is set." << endl;
    } else {
        cout << "The " << k << "-th bit is not set." << endl;
    }
    return 0;
}

Java Program to Check Whether K-th Bit is Set or Not

java
public class KthBitCheck {

    // Function to check if the k-th bit is set
    public static boolean isKthBitSet(int n, int k) {
        // Shift 1 to the left by (k-1) positions and perform AND with n
        return (n & (1 << (k - 1))) != 0;
    }

    public static void main(String[] args) {
        int n = 18, k = 2;
        if (isKthBitSet(n, k)) {
            System.out.println("The " + k + "-th bit is set.");
        } else {
            System.out.println("The " + k + "-th bit is not set.");
        }
    }
}

Python Program to Check Whether K-th Bit is Set or Not

python
# Function to check if the k-th bit is set
def is_kth_bit_set(n, k):
    # Shift 1 to the left by (k-1) positions and perform AND with n
    return (n & (1 << (k - 1))) != 0

# Example usage
if __name__ == "__main__":
    n = 18
    k = 2
    if is_kth_bit_set(n, k):
        print(f"The {k}-th bit is set.")
    else:
        print(f"The {k}-th bit is not set.")
  • Time Complexity: O(1) because bitwise operations like n & (1 << (k-1)) are constant-time operations.
  • Space Complexity: O(1) since only a few variables are used, independent of the input size.

Explanation of the Bitwise Operation:

  • 1 << (k - 1) shifts the 1 left by k-1 positions, creating a binary mask where only the k-th bit is set to 1, and all other bits are 0.
  • n & (1 << (k - 1)) performs a bitwise AND between n and this mask. If the k-th bit in n is set, the result will be non-zero; otherwise, the result will be 0.

DSA

2953

794

Related Articles