Toggling k-th bit of a number
Introduction
Toggling k-th bit of a number involves changing the state of a specific bit in a binary representation of a number from 0 to 1 or vice versa. This operation is commonly used in various algorithms and applications, such as data manipulation, bitwise operations, and setting or clearing flags in control registers.
In this guide, we will explore the concept of toggling the k-th bit and provide examples to help you understand and implement this operation effectively.
Understanding Toggling k-th bit of a number
Toggling k-th bit of a number refers to the process of changing the state of a specific bit at position “k” within the binary representation of that number.
- If the k-th bit is currently 0, it is changed to 1, and if it’s 1, it is changed to 0.
- This operation is typically accomplished using bitwise XOR with a mask that has only the k-th bit set to 1, effectively flipping the bit’s value while leaving the other bits unchanged.
Example :
Example 1:
Input: n = 12, k = 3
Output: 8
Explanation:
The binary representation of 12 is 1100. In binary, it has the third bit set to 1. By toggling the 3rd bit (k=3), we change it from 1 to 0, resulting in the binary representation 1000, which is equal to 8 in decimal.
Example 2:
Input: n = 75, k = 5
Output: 91
Explanation:
The binary representation of 75 is 1001011. In binary, it has the fifth bit set to 0. By toggling the 5th bit (k=5), we change it from 0 to 1, resulting in the binary representation 1011011, which is equal to 91 in decimal.
Toggling a Bit: The XOR Operation
The most common method for toggling the k-th bit of a number is by using the XOR (^) operation. XORing a number with a mask that has only the k-th bit set will change the state of that bit, making it 0 if it was 1 and 1 if it was 0.
- Toggling the k-th bit: number ^ (1 << k)
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Program for Toggling k-th Bit
def toggle_kth_bit(num, k):
# Create a mask with only the k-th bit set to 1
mask = 1 << k
# Use XOR to toggle the k-th bit
result = num ^ mask
return result
#Let us take an example
number = 10 # Binary: 1010 (decimal 10)
k = 2 # Toggle the 2nd bit from the right
result = toggle_kth_bit(number, k)
print("The number after toggling the", k, "-th bit is", result)
Output :
The number after toggling the 2 -th bit is 8.
Explanation :
- The program toggles the 2nd bit of the number 10 using bitwise operations.
- It creates a mask with the 2nd bit set to 1 (binary 0010).
- The XOR (^) operation is used between the original number and the mask.
- This flips the 2nd bit, changing the number from 10 to 14.
- The output of the program is: “The number after toggling the 2 -th bit is 14.”
Time and Space Complexity:
| Complexity Type | Value |
|---|---|
| Time Complexity | O(1) |
| Space Complexity | O(1) |
More Examples on Toggling K-th bit
def toggle_kth_bit(num, k):
# Create a mask with only the k-th bit set to 1
mask = 1 << k
# Use XOR to toggle the k-th bit
result = num ^ mask
return result
# Example usage:
number = 27 # Binary: 11011 (decimal 27)
k = 3 # Toggle the 3rd bit from the right
result = toggle_kth_bit(number, k)
print("The number after toggling the", k, "-th bit is", result)
Output :
The number after toggling the 3 -th bit is 31.
Explanation :
- The program toggles the 3rd bit of the number 27 (binary: 11011).
- It uses the XOR operation to flip the specific bit.
- The 3rd bit changes from 0 to 1, making the binary 11111.
- This results in the decimal value 31 after toggling.
- The output confirms the operation: “The number after toggling the 3 -th bit is 31.”
Time and Space Complexity:
| Complexity Type | Value |
|---|---|
| Time Complexity | O(1) |
| Space Complexity | O(1) |
Practical Applications of Flipping i-th bit
Following are the practical application for toggling k-th bit of a number :
To wrap it up:
The operation of toggling the k-th bit of a number is : By employing bitwise XOR operations, developers can easily manipulate and control specific bits within numbers. This operation has widespread use in settings such as flag management, data compression, error correction, and hardware control.
FAQs
Toggling the k-th bit means changing it from 0 to 1 or from 1 to 0 using bitwise operations. This is commonly done with the XOR (^) operator.
Use the expression num ^ (1 << k) where num is your number and k is the bit index (0-based). This flips only the k-th bit while keeping others unchanged.
Toggling the same bit twice restores it to its original state. This is because XORing twice with the same bit mask cancels out the change.
Setting forces a bit to 1, clearing sets it to 0, and toggling flips it (1→0 or 0→1). Toggling is achieved using XOR, while setting/clearing use OR/AND operations.
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