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

Problem 1. Check if an integer is even or odd

This is probably one of the simplest and most commonly used bit hacks. The expression n & 1 returns value 1 or 0 depending upon whether n is odd or even.

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

Following is the C++, Java, and Python program that demonstrates it:

C++


Download  Run Code

Output:

5 is odd

Java


Download  Run Code

Output:

5 is odd

Python


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 if x and y have opposite signs. We know that for a positive number, the leftmost bit is 0, and for a negative number, it is 1. Now for similar sign integers, the XOR operator will set the leftmost bit of output as 0, and for opposite sign integers, it will set the 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

This approach is demonstrated below in C++, Java, and Python:

C++


Download  Run Code

Output:

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

Java


Download  Run Code

Output:

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

Python


Download  Run Code

Output:

4 in binary is 0b100
-8 in binary is -0b1000
4 and -8 have opposite signs

Problem 3. Add 1 to an integer

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

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

The implementation can be seen below in C++ and Java:

C++


Download  Run Code

Output:

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

Java


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 hacks. The idea is to use XOR operators to swap two numbers by their property x ^ x = 0. The following C++ program demonstrates it:

C++


Download  Run Code

Output:

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

 
Also See:

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