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

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of