Check whether kth bit is set or not
| Measure | Complexity |
|---|---|
| Time Complexity | O(1) |
| Space Complexity | O(1) |
Introduction to Check nth bit
To check whether nth bit is set or not, we have to consider the position of nth bit to be set or not. “Check whether nth bit is set or not” refers to the process of determining the state of a specific bit within the binary representation of a number.
In binary, each digit is a bit, and these bits are numbered from right to left, starting with 0. The term “nth bit” indicates the bit at position n in the binary representation of a number.
Understanding "Check nth bit"
Checking nth bit means it is the process where we examine a binary number to see if the digit at a specific position, referred to as the nth bit, is either 1 (set) or 0 (not set).
- In binary, each digit is a bit, and these bits are numbered from right to left, starting with 0.
- The term “nth bit” indicates the bit at position n in the binary representation of a number.
Example :
Example 1 :
Let’s break it down with an example:
Consider the binary number 101001. Each digit in this binary number is a bit, and we number them from right to left starting with 0. So, in this case:
- The 0th bit is 1
- The 1st bit is 0
- The 2nd bit is 0
- The 3rd bit is 1
- The 4th bit is 0
- The 5th bit is 1
Now, if we want to check whether the 3rd bit is set or not, we look at the digit at the 3rd position, which is 1. Since it’s 1, we say that the 3rd bit is set.
In simple terms, checking whether the nth bit is set or not involves inspecting a binary number and determining if the digit at the specified position (nth bit) is 1 or 0.
Example 2 :
Binary number: 101001
Check whether the 4th bit is set or not.
Result: The 4th bit is set because the digit at the 4th position is 0.
Idea for "Check whether nth bit is set or not"
- Right-shift n by (k – 1) positions and assign the result to temp.
- If the bitwise AND operation between temp and 1 equals 1, then
- Return True
- Return False
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Program to check whether nth bit is set or not
To check whether the kth bit is set, we can use a bitwise AND operation. The AND operation compares each bit of two binary numbers and produces a result where a bit is set to 1 only if the corresponding bits in both numbers are 1.
Method 1: Using Bitwise AND with Left Shift (1 << k)
This method checks if the k-th bit is set by creating a mask with only the k-th bit set and performing a bitwise AND with the number. If the result is non-zero, it means the bit is set.
Code:
def is_kth_bit_set_method1(n, k):
if n & (1 << k):
return "Yes"
else:
return "No"
# Example
number = 10 # Binary: 1010
k = 1
print("Method 1 Output:", is_kth_bit_set_method1(number, k))
Output:
Yes
Explanation:
- 1 << k shifts 1 to the k-th bit position.
- Bitwise AND checks whether that specific bit in n is set.
- In this case, the 1st bit in 10 is 1, so the result is “Yes”.
Method 2: Using Right Shift and Bitwise AND with 1 ((n >> k) & 1)
This method shifts the number n right by k bits, bringing the k-th bit to the least significant position. A bitwise AND with 1 then checks if that bit is set.
def is_kth_bit_set_method2(n, k):
if (n >> k) & 1:
return "Yes"
else:
return "No"
# Example
number = 10 # Binary: 1010
k = 1
print("Method 2 Output:", is_kth_bit_set_method2(number, k))
Output:
Yes
Explanation:
- n >> k brings the k-th bit to the 0-th position.
- (n >> k) & 1 then checks if that bit is 1 (set).
- Since the result is 1, it means the k-th bit is set.
Practical Applications
Following are the practical application :
To wrap it up:
The ability to check whether the nth bit is set or not involves leveraging bitwise operations to examine the binary representation of a number and determine the state of a specific bit. This operation finds utility in low-level programming, device driver development, cryptography, and other domains where direct control over individual bits is essential.
FAQs
It means verifying whether the bit at position ‘k’ (starting from 0) in the binary representation of a number is 1 (set) or 0 (unset). This is commonly used in bitwise operations and masking.
Use the expression (n & (1 << k)) != 0. It shifts 1 to the kth position and checks if that bit is set in number n.
The time complexity is O(1) since it involves only a few bitwise operations regardless of the number size.
In most implementations including Python, the bit position k is 0-indexed, meaning the least significant bit is position 0.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment