Bit Hacks – Part 1 (Basic)

With this post, we will start a series of amazing bit manipulation hacks that every programmer should know.

 

Below problems are covered in this post –

 



 
Problem 1. Check if an given integer is even or odd
 

This is probably one of the simplest and most commonly used bit hack. The expression (n & 1) will return value 1 or 0 depending upon n is odd or even.


00010100   &                 (n = 20)
00000001                     (1)
~~~~~~~~
00000000
 

00010101   &                 (n = 21)
00000001                     (1)
~~~~~~~~
00000001

C++

Download   Run Code

Output:

5 is odd

 



 
Problem 2. Detect if two integers have opposite signs or not
 

The expression output (x ^ y) is negative iff x and y have opposite signs. We know that for a positive number, leftmost bit is 0 and for a negative number, it is 1. Now for similar sign integers, the XOR operator will set leftmost bit of output as 0 and for opposite sign integers, it will set leftmost bit as 1.


00…000100   ^              (x = 4)
00…001000                  (y = 8)
~~~~~~~~~
00…001100                  positive number
 

00…000100   ^              (x = 4)
11…111000                  (y = -8)
~~~~~~~~~
11…111100                  negative number

C++

Download   Run Code

Output:

4 in binary is 00000000000000000000000000000100
-8 in binary is 11111111111111111111111111111000
4 and -8 have opposite signs

 



 
Problem 3. Add 1 to a given integer
 

The expression -~x will add 1 to a given integer. We know that to get negative of a number, we invert its bits and add 1 to it (Remember negative numbers are stores in 2’s compliment form). i.e.

-x = ~x + 1;
-~x = x + 1 (by replacing x by ~x)

C++

Download   Run Code

Output:

4 + 1 is 5
-5 + 1 is -4
0 + 1 is 1

 



 
Problem 4. Swap two numbers without using any third variable
 

This is again one of the simplest and most commonly used bit hack. The idea is to use XOR operators for swapping two numbers by their property that (x ^ x = 0).

C++

Download   Run Code

Output:

Before swap: x = 3 and y = 4
After swap: x = 4 and y = 3

Read More –

Bit Hacks – Part 2 (Playing with k’th bit)
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