Check the whether the kth bit from right is SET ?

 

 

In this blog post, we’ll explore how to check whether the k-th bit (from the right) of a number is set (i.e., is equal to 1) using bitwise operations in Python. This is a common problem that’s useful in programming challenges and low-level bit manipulation.

Problem Explanation

We are given a number n in its binary form and an integer k, which indicates the position of the bit we want to check, starting from the right (with the least significant bit being the 1st bit). The goal is to determine whether the bit at position k is set (i.e., 1) or not set (i.e., 0).

Example Walkthrough

Let’s take an example to clarify the concept. Suppose we have the number n = 6, which is 110 in binary. Now, we want to check if the 1st bit from the right is set.

1. Convert the number to binary:

   • The binary representation of 6 is 110.

2. Identify the bit position:

   • We want to check the 1st bit from the right.

3. Bitwise AND Operation:

   • To check if the k-th bit is set, we perform a bitwise AND between the number n and 1 shifted left (k - 1) positions. This is done using the expression: $$n \& (1 << (k - 1))$$
   • If the result is non-zero, the k-th bit is set; otherwise, it is not set.

Example 1: Check the 1st Bit in 6

• Binary of 6: 110
• We are checking the 1st bit: $$1 << (1 - 1) = 1 << 0 = 1$$
• Perform the AND operation: $$110 \& 001 = 001$$
  • Since the result is non-zero (001), the 1st bit is set.

Example 2: Check the 2nd Bit in 6

• Binary of 6: 110
• We are checking the 2nd bit: $$1 << (2 - 1) = 1 << 1 = 10$$
• Perform the AND operation: $$110 \& 010 = 010$$
  • Since the result is non-zero (010), the 2nd bit is set.

Example 3: Check the 3rd Bit in 6

• Binary of 6: 110
• We are checking the 3rd bit: $$1 << (3 - 1) = 1 << 2 = 100$$
• Perform the AND operation: $$110 \& 100 = 100$$
  • Since the result is non-zero (100), the 3rd bit is set.

Now that we understand the concept, let’s write the Python code to implement this.

Python Code

python: 

def kthbit(n, k):

    # Check if the k-th bit is set by using bitwise AND with a left-shifted 1

    if n & (1 << (k - 1)):

        print("SET")

    else:

        print("NOT SET")

# Input: number and bit position to check

n, k = map(int, input("Enter a number and the bit position to check: ").split())

# Print binary representation of the number

print("The binary representation of", n, "is", bin(n)[2:])

# Check and print whether the k-th bit is set

print(f"The bit at position {k} from the right is:")

kthbit(n, k)

How the Code Works

1. Input Handling: The user is prompted to input a number n and the bit position k they want to check.

2. Binary Representation: The binary representation of the number is printed for clarity, using Python’s bin() function, which converts a number into its binary format.

3. Checking the k-th Bit: The function kthbit() checks whether the bit at position k from the right is set or not by using the bitwise AND operation between the number n and the result of 1 << (k - 1).

4. Output:

   • If the bit is set, the program outputs "SET".
   • If the bit is not set, it outputs "NOT SET".

Example Input and Output

Input:

Enter a number and the bit position to check: 6 1

Output:

The binary representation of 6 is 110
The bit at position 1 from the right is:
SET

---

Input:

Enter a number and the bit position to check: 6 3

Output:

The binary representation of 6 is 110
The bit at position 3 from the right is:
SET

---

Input:

Enter a number and the bit position to check: 6 4

Output:

The binary representation of 6 is 110
The bit at position 4 from the right is:
NOT SET

Conclusion

By using bitwise operations, specifically the left shift (<<) and bitwise AND (&), we can efficiently check whether the k-th bit of a number is set. This method works in constant time $O(1)$ and is a common technique in low-level programming, competitive programming, and situations where bit manipulation is necessary.

This approach is both simple and powerful, allowing you to quickly analyze bits in a number and perform operations like checking, setting, or flipping bits.