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++

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++

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++

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++

Output:

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

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 🙂

Get great deals at Amazon