Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Check K-th Bit

EASYProblemSolveExternal Links

Description

Given two positive integers n and k, check whether the k-th bit (0-indexed from the LSB — Least Significant Bit) of n is set (i.e., equals 1) or not set (i.e., equals 0).

Return true if the k-th bit is set, and false otherwise.

Note: A bit is called set if it is 1. Bit indexing starts from 0 at the rightmost (least significant) position.

Examples

Example 1

Input: n = 4, k = 0

Output: false

Explanation: The binary representation of 4 is 100. The 0th bit (rightmost) is 0, which is not set. So, return false.

Example 2

Input: n = 4, k = 2

Output: true

Explanation: The binary representation of 4 is 100. The 2nd bit (counting from 0 at the right) is 1, which is set. So, return true.

Example 3

Input: n = 500, k = 3

Output: false

Explanation: The binary representation of 500 is 111110100. The 3rd bit from the right is 0, which is not set. So, return false.

Example 4

Input: n = 7, k = 2

Output: true

Explanation: The binary representation of 7 is 111. All bits at positions 0, 1, and 2 are set. So, checking k = 2 returns true.

Constraints

  • 1 ≤ n ≤ 10^9
  • 0 ≤ k ≤ 31

Editorial

Brute Force - String Conversion

Intuition

The most straightforward way to check if a particular bit is set is to convert the number into its binary string representation and then inspect the character at the desired position.

Since we think of binary as ...bit3 bit2 bit1 bit0 (right to left), but strings are indexed left to right, we need to be careful about indexing. The k-th bit from the LSB corresponds to the character at position (length - 1 - k) from the left of the binary string.

For example, n = 500 has binary representation 111110100. The string has length 9. To check bit k=3, we look at position 9 - 1 - 3 = 5 from the left, which is 0.

This approach is intuitive — we literally "see" the binary and pick out the bit we want — but it requires converting the entire number to a string first.

Step-by-Step Explanation

Let's trace through n = 500, k = 3:

Step 1: Convert n = 500 to binary string. We repeatedly divide by 2 and collect remainders:

  • 500 ÷ 2 = 250 remainder 0
  • 250 ÷ 2 = 125 remainder 0
  • 125 ÷ 2 = 62 remainder 1
  • 62 ÷ 2 = 31 remainder 0
  • 31 ÷ 2 = 15 remainder 1
  • 15 ÷ 2 = 7 remainder 1
  • 7 ÷ 2 = 3 remainder 1
  • 3 ÷ 2 = 1 remainder 1
  • 1 ÷ 2 = 0 remainder 1

Reading remainders bottom-to-top: 111110100

Step 2: The binary string is 111110100 with length 9.

Step 3: Calculate the string index: position = length - 1 - k = 9 - 1 - 3 = 5.

Step 4: Character at index 5 is 0.

Step 5: Since the character is 0, the 3rd bit is NOT set. Return false.

String Conversion: Check k=3 bit of n=500 — Convert 500 to binary string, map k-th bit to string index, and read the character.

Algorithm

  1. Convert the integer n to its binary string representation
  2. Let len = length of the binary string
  3. Compute string index: idx = len - 1 - k
  4. If idx < 0, the k-th bit is beyond the number's binary length → return false
  5. If character at idx is '1' → return true
  6. Else → return false

Code

#include <string>
using namespace std;

class Solution {
public:
    bool checkKthBit(int n, int k) {
        // Convert n to binary string
        string binary = "";
        int temp = n;
        
        while (temp > 0) {
            binary = (char)('0' + temp % 2) + binary;
            temp /= 2;
        }
        
        // Handle edge case: n = 0
        if (binary.empty()) binary = "0";
        
        int len = binary.length();
        
        // Check if k exceeds the number of bits
        if (k >= len) return false;
        
        // Map k-th bit (from LSB) to string index
        int idx = len - 1 - k;
        
        return binary[idx] == '1';
    }
};
class Solution:
    def checkKthBit(self, n: int, k: int) -> bool:
        # Convert n to binary string (bin() returns '0b...')
        binary = bin(n)[2:]  # Remove '0b' prefix
        
        length = len(binary)
        
        # Check if k exceeds the number of bits
        if k >= length:
            return False
        
        # Map k-th bit (from LSB) to string index
        idx = length - 1 - k
        
        return binary[idx] == '1'
class Solution {
    public boolean checkKthBit(int n, int k) {
        // Convert n to binary string
        String binary = Integer.toBinaryString(n);
        
        int len = binary.length();
        
        // Check if k exceeds the number of bits
        if (k >= len) return false;
        
        // Map k-th bit (from LSB) to string index
        int idx = len - 1 - k;
        
        return binary.charAt(idx) == '1';
    }
}

Complexity Analysis

Time Complexity: O(log n)

Converting the integer n to a binary string requires repeatedly dividing by 2, which takes O(log n) iterations (since the number of binary digits in n is ⌊log₂(n)⌋ + 1). After conversion, the lookup is O(1).

Space Complexity: O(log n)

The binary string has ⌊log₂(n)⌋ + 1 characters. For n up to 10⁹, this is at most 30 characters, but asymptotically it is O(log n).

Why This Approach Is Not Efficient

The string conversion approach works but has several inefficiencies:

1. Converts ALL bits when we only need ONE: We build the entire binary string (up to 30 characters for a 32-bit integer) just to check a single bit position. This is like reading an entire book to find one word on one page.

2. Unnecessary memory allocation: Creating a string object allocates heap memory, involves character copying, and needs garbage collection — all overhead for a simple yes/no answer.

3. O(log n) time for an O(1) problem: The CPU already stores n in binary form internally. There's no reason to "convert" what's already binary. We just need to look at the right bit.

Key insight: Since the number is already stored as bits in memory, we can use a bitmask — a number with only the k-th bit set — and use the AND operator to directly test that one bit. This avoids conversion entirely and runs in O(1).

Optimal Approach - Left Shift Masking

Intuition

Instead of converting n to a string, we create a bitmask that has a 1 at exactly the k-th position and 0 everywhere else. Then we AND this mask with n:

  • If the k-th bit of n is 1: n & mask produces a non-zero result (the mask itself)
  • If the k-th bit of n is 0: n & mask produces 0

How to create the mask: Start with the number 1 (which is 000...001 in binary — only bit 0 is set). Left-shift it by k positions: 1 << k. This moves the single 1 from bit 0 to bit k.

Examples of masks:

  • k = 0: 1 << 0 = 0001 (tests bit 0)
  • k = 1: 1 << 1 = 0010 (tests bit 1)
  • k = 2: 1 << 2 = 0100 (tests bit 2)
  • k = 3: 1 << 3 = 1000 (tests bit 3)

The AND operation acts as a spotlight — it illuminates only the k-th bit while darkening everything else. If the spotlight reveals a 1, the bit is set.

Alternative (Right Shift): Instead of moving the mask to the bit, we can move the bit to the mask. Right-shift n by k positions (n >> k), which brings the k-th bit to position 0. Then AND with 1 to isolate it: (n >> k) & 1. Both approaches are equally optimal.

Step-by-Step Explanation

Example A: n = 7 (binary: 0111), k = 2 → Expected: true

Step 1: Create the mask: 1 << 2 = 4 (binary: 0100). This mask has a single 1 at position 2.

Step 2: Perform AND: 0111 & 0100. Compare each bit position:

  • Bit 3: 0 & 0 = 0
  • Bit 2: 1 & 1 = 1 ← the bit we're testing
  • Bit 1: 1 & 0 = 0 (masked out)
  • Bit 0: 1 & 0 = 0 (masked out)

Step 3: Result is 0100 = 4, which is non-zero. The k-th bit is set. Return true.

Example B: n = 500 (binary: 111110100), k = 3 → Expected: false

Step 4: Create the mask: 1 << 3 = 8 (binary: 000001000).

Step 5: Perform AND: 111110100 & 000001000. The mask isolates bit 3.

Step 6: At bit position 3, n has 0. So 0 & 1 = 0. All other positions also become 0 (masked out).

Step 7: Result is 000000000 = 0. The k-th bit is not set. Return false.

Alternative with Right Shift (n = 7, k = 2):

Step 8: Right-shift n by k: 7 >> 2 = 1 (binary: 0111 → 0001). The bit that was at position 2 is now at position 0.

Step 9: AND with 1: 0001 & 0001 = 1. The result is 1, meaning the original k-th bit was set. Return true.

Left Shift Masking: Check bit k=2 of n=7 — Watch how we create a bitmask with 1 << k, then use AND to isolate and test the single target bit — all in O(1) time.

Left Shift Masking: Check bit k=3 of n=500 (not set) — Same technique on a larger number where the target bit is NOT set — demonstrating how AND produces 0 when the bit is clear.

Alternative: Right Shift Approach (n >> k) & 1 — Instead of moving the mask to the bit, move the bit to position 0 using right shift, then isolate with AND 1.

Algorithm

Method 1: Left Shift Masking

  1. Create a mask with only the k-th bit set: mask = 1 << k
  2. AND the mask with n: result = n & mask
  3. If result ≠ 0, the k-th bit is set → return true
  4. Else → return false

Method 2: Right Shift and Isolate

  1. Right-shift n by k positions: shifted = n >> k
  2. AND with 1 to isolate bit 0: bit = shifted & 1
  3. If bit == 1 → return true
  4. Else → return false

Both methods are O(1) and achieve the same result. Method 1 produces the mask 2^k if the bit is set (or 0 if not), while Method 2 produces exactly 0 or 1.

Code

class Solution {
public:
    // Method 1: Left Shift Masking
    bool checkKthBit(int n, int k) {
        // Create mask with only k-th bit set
        int mask = (1 << k);
        
        // If AND is non-zero, k-th bit is set
        return (n & mask) != 0;
    }
    
    // Method 2: Right Shift and Isolate
    bool checkKthBitAlt(int n, int k) {
        // Shift n right by k to bring target bit to position 0
        // AND with 1 to isolate it
        return ((n >> k) & 1) == 1;
    }
};
class Solution:
    # Method 1: Left Shift Masking
    def checkKthBit(self, n: int, k: int) -> bool:
        # Create mask with only k-th bit set
        mask = 1 << k
        
        # If AND is non-zero, k-th bit is set
        return (n & mask) != 0
    
    # Method 2: Right Shift and Isolate
    def checkKthBitAlt(self, n: int, k: int) -> bool:
        # Shift n right by k to bring target bit to position 0
        # AND with 1 to isolate it
        return ((n >> k) & 1) == 1
class Solution {
    // Method 1: Left Shift Masking
    public boolean checkKthBit(int n, int k) {
        // Create mask with only k-th bit set
        int mask = (1 << k);
        
        // If AND is non-zero, k-th bit is set
        return (n & mask) != 0;
    }
    
    // Method 2: Right Shift and Isolate
    public boolean checkKthBitAlt(int n, int k) {
        // Shift n right by k to bring target bit to position 0
        // AND with 1 to isolate it
        return ((n >> k) & 1) == 1;
    }
}

Complexity Analysis

Time Complexity: O(1)

Both the left shift and the AND operation are single CPU instructions that execute in constant time. The number of bits (32 or 64) is a fixed hardware constant, not dependent on the value of n or k. Each operation takes one clock cycle.

Space Complexity: O(1)

Only a constant number of integer variables are used (the mask and/or the shifted value). No arrays, strings, or additional data structures are needed.

Why this is optimal: We cannot do better than O(1) time and O(1) space. The problem asks a single binary question (is the bit set?), and we answer it with at most two hardware operations. The bitwise approach directly queries the internal binary representation — there is nothing to convert, iterate, or allocate.