Bit Hacks – Part 2 (Playing with k’th bit)

In this post we will discuss few related problems that operates on the k’th bit of a number.

 
Below problems are covered in this post –

 



 
Problem 1. Turn off k’th bit in a number
 

The idea is to use bitwise <<, & and ~ operators. By using expression ~ (1 << (k - 1)), we get a number which has 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 same as n except the k’th bit which will be set to 0.


For example, consider n = 20 and k = 3.

00010100   &             (n = 20)
11111011                 ~ (1 << (3-1))

~~~~~~~~
00010000

C++

Download   Run Code

Output:

20 in binary is 00010100
Turning k’th bit off
16 in binary is 00010000

 



 
Problem 2. Turn on k’th bit in a number
 

The idea is to use bitwise << and | operators. By using expression (1 << (k - 1)), we get a number which has 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 same as n except the k’th bit which will be set to 1.

For example, consider n = 20 and k = 4.

00010100   |             (n = 20)
00001000                 (1 << (4 - 1))

~~~~~~~~
00011100

C++

Download   Run Code

Output:

20 in binary is 00010100
Turning k’th bit on
28 in binary is 00011100

 



 
Problem 3. Check if k’th bit is set for a number
 

The idea is to use bitwise << and & operators. By using expression (1 << (k - 1)), we get a number which has all bits 0, except the k’th bit. If we do bitwise AND of this expression with n i.e. (n | (1 << k)), any non-zero value means that its k-th bit is set.

For example, consider n = 20 and k = 3.

00010100   &             (n = 20)
00000100                 (1 << (3-1))

~~~~~~~~
00000100                 non-zero value

C++

Download   Run Code

Output:

20 in binary is 00010100
k-th bit is set

 



 
Problem 4. Toggle the k-th bit
 

The idea is to use bitwise ^ and << operators. By using expression (1 << (k - 1)), we get a number which has 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).

C++

Download   Run Code

Output:

20 in binary is 00010100
Toggling k’th bit of n
16 in binary is 00010000

Read More –

Bit Hacks – Part 1 (Basic)
Bit Hacks – Part 3 (Playing with rightmost set bit of a number)
Bit Hacks – Part 4 (Playing with letters of English alphabet)
Bit Hacks – Part 5 (Find absolute value of an integer without branching)
Bit Hacks – Part 6 (Random Problems)

 
Suggested Read: https://graphics.stanford.edu/~seander/bithacks.html

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz