Bit Hacks – Part 2 (Playing with k’th bit)
This post will discuss a few related problems that operate on the k’th bit of a number.
The following problems are covered in this post:
Problem 1. Turn off k’th bit in a number
The idea is to use bitwise <<, &, and ~ operators. Using the expression ~ (1 << (k - 1)), we get a number with all its bits set, except the k'th bit. If we do a bitwise AND of this expression with n, i.e., n & ~(1 << (k - 1)), we get a number which has all bits the same as n except the k'th bit which will be set to 0.
For example, consider n = 20 and k = 3.
11111011 ~ (1 << (3-1))
~~~~~~~~
00010000
Following is the C++, Java, and Python implementation of the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <iostream> #include <bitset> using namespace std; // Function to turn off k'th bit in `n` int turnOffKthBit(int n, int k) { return n & ~(1 << (k - 1)); } int main() { int n = 20; int k = 3; cout << n << " in binary is " << bitset<8>(n) << endl; cout << "Turning k'th bit off\n"; n = turnOffKthBit(n, k); cout << n << " in binary is " << bitset<8>(n) << endl; return 0; } |
Output:
20 in binary is 00010100
Turning k’th bit off
16 in binary is 00010000
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Main { // Function to turn off k'th bit in `n` public static int turnOffKthBit(int n, int k) { return n & ~(1 << (k - 1)); } public static void main(String[] args) { int n = 20; int k = 3; System.out.println(n + " in binary is " + Integer.toBinaryString(n)); System.out.println("Turning k'th bit off…"); n = turnOffKthBit(n, k); System.out.println(n + " in binary is " + Integer.toBinaryString(n)); } } |
Output:
20 in binary is 10100
Turning k’th bit off…
16 in binary is 10000
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
# Function to turn off k'th bit in `n` def turnOffKthBit(n, k): return n & ~(1 << (k - 1)) if __name__ == '__main__': n = 20 k = 3 print(f'{n} in binary is {bin(n)}') print('Turning k\'th bit off…') n = turnOffKthBit(n, k) print(f'{n} in binary is {bin(n)}') |
Output:
20 in binary is 0b10100
Turning k’th bit off…
16 in binary is 0b10000
Problem 2. Turn on k’th bit in a number
The idea is to use bitwise << and | operators. Using the expression 1 << (k - 1), we get a number with all bits 0, except the k'th bit. If we do bitwise OR of this expression with n, i.e., n | (1 << (k - 1)), we get a number which has all bits the same as n except the k'th bit which will be set to 1.
For example, consider n = 20 and k = 4.
00001000 (1 << (4 – 1))
~~~~~~~~
00011100
Following is the C++, Java, and Python program that demonstrates it:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <iostream> #include <bitset> using namespace std; // Function to turn on k'th bit in `n` int turnOnKthBit(int n, int k) { return n | (1 << (k - 1)); } int main() { int n = 20; int k = 4; cout << n << " in binary is " << bitset<8>(n) << endl; cout << "Turning k'th bit on\n"; n = turnOnKthBit(n, k); cout << n << " in binary is " << bitset<8>(n) << endl; return 0; } |
Output:
20 in binary is 00010100
Turning k’th bit on
28 in binary is 00011100
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Main { // Function to turn on k'th bit in `n` public static int turnOnKthBit(int n, int k) { return n | (1 << (k - 1)); } public static void main(String[] args) { int n = 20; int k = 4; System.out.println(n + " in binary is " + Integer.toBinaryString(n)); System.out.println("Turning k'th bit on…"); n = turnOnKthBit(n, k); System.out.println(n + " in binary is " + Integer.toBinaryString(n)); } } |
Output:
20 in binary is 10100
Turning k’th bit on…
28 in binary is 11100
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
# Function to turn on k'th bit in `n` def turnOnKthBit(n, k): return n | (1 << (k - 1)) if __name__ == '__main__': n = 20 k = 4 print(f'{n} in binary is {bin(n)}') print('Turning k\'th bit on…') n = turnOnKthBit(n, k) print(f'{n} in binary is {bin(n)}') |
Output:
20 in binary is 0b10100
Turning k’th bit on…
28 in binary is 0b11100
Problem 3. Check if k’th bit is set for a number
The idea is to use bitwise << and & operators. Using the expression 1 << (k - 1), we get a number with all bits 0, except the k'th bit. If we do bitwise AND of this expression with n, i.e., n & (1 << (k - 1)), any non-zero value indicates that its k'th bit is set.
For example, consider n = 20 and k = 3.
00000100 (1 << (3-1))
~~~~~~~~
00000100 non-zero value
Following is the C++, Java, and Python implementation of the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include <iostream> #include <bitset> using namespace std; // Function to check if k'th bit is set for `n` or not bool isKthBitSet(int n, int k) { return (n & (1 << (k - 1))) != 0; } int main() { int n = 20; int k = 3; cout << n << " in binary is " << bitset<8>(n) << endl; if (isKthBitSet(n, k)) { cout << "k'th bit is set"; } else { cout << "k'th bit is not set"; } return 0; } |
Output:
20 in binary is 00010100
k’th bit is set
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Main { // Function to check if k'th bit is set for `n` or not public static boolean isKthBitSet(int n, int k) { return (n & (1 << (k - 1))) != 0; } public static void main(String[] args) { int n = 20; int k = 3; System.out.println(n + " in binary is " + Integer.toBinaryString(n)); if (isKthBitSet(n, k)) { System.out.println("k'th bit is set"); } else { System.out.println("k'th bit is not set"); } } } |
Output:
20 in binary is 10100
k’th bit is set
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
# Function to check if k'th bit is set for `n` or not def isKthBitSet(n, k): return (n & (1 << (k - 1))) != 0 if __name__ == '__main__': n = 20 k = 3 print(f'{n} in binary is {bin(n)}') if isKthBitSet(n, k): print('k\'th bit is set') else: print('k\'th bit is not set') |
Output:
20 in binary is 0b10100
k’th bit is set
Problem 4. Toggle the k’th bit
The idea is to use bitwise ^ and << operators. By using the expression 1 << (k - 1), we get a number with all bits 0, except the k'th bit. If we do bitwise XOR of this expression with n, i.e., n ^ (1 << k), we can easily toggle its k'th bit as 0 ^ 1 = 1 and 1 ^ 1 = 0.
This approach is demonstrated below in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <iostream> #include <bitset> using namespace std; // Function to toggle k'th bit of `n` int toggleKthBit(int n, int k) { return n ^ (1 << (k - 1)); } int main() { int n = 20; int k = 3; cout << n << " in binary is " << bitset<8>(n) << endl; cout << "Toggling k'th bit of n\n"; n = toggleKthBit(n, k); cout << n << " in binary is " << bitset<8>(n) << endl; return 0; } |
Output:
20 in binary is 00010100
Toggling k’th bit of n
16 in binary is 00010000
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Main { // Function to toggle k'th bit of `n` public static int toggleKthBit(int n, int k) { return n ^ (1 << (k - 1)); } public static void main(String[] args) { int n = 20; int k = 3; System.out.println(n + " in binary is " + Integer.toBinaryString(n)); System.out.println("Toggling k'th bit of n…"); n = toggleKthBit(n, k); System.out.println(n + " in binary is " + Integer.toBinaryString(n)); } } |
Output:
20 in binary is 10100
Toggling k’th bit of n…
16 in binary is 10000
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
# Function to toggle k'th bit of `n` def toggleKthBit(n, k): return n ^ (1 << (k - 1)) if __name__ == '__main__': n = 20 k = 3 print(f'{n} in binary is {bin(n)}') print('Toggling k\'th bit of n…') n = toggleKthBit(n, k) print(f'{n} in binary is {bin(n)}') |
Output:
20 in binary is 0b10100
Toggling k’th bit of n…
16 in binary is 0b10000
Also See:
Bit Hacks – Part 1 (Basic)
Bit Hacks – Part 3 (Playing with the rightmost set bit of a number)
Bit Hacks – Part 4 (Playing with letters of the English alphabet)
Bit Hacks – Part 5 (Find the absolute value of an integer without branching)
Suggested Read:
https://graphics.stanford.edu/~seander/bithacks.html
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)