Bit Hacks – Part 1 (Basic)
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.
00000001 (1)
~~~~~~~~
00000000
00010101 & (n = 21)
00000001 (1)
~~~~~~~~
00000001
Following is the C++, Java, and Python program that demonstrates it:
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include <iostream> using namespace std; int main() { int n = 5; if (n & 1) { cout << n << " is odd"; } else { cout << n << " is even"; } return 0; } |
Output:
5 is odd
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Main { public static void main(String[] args) { int n = 5; if ((n & 1) != 0) { System.out.println(n + " is odd"); } else { System.out.println(n + " is even"); } } } |
Output:
5 is odd
Python
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…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++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> #include <bitset> using namespace std; int main() { int x = 4; int y = -8; cout << x << " in binary is " << bitset<32>(x) << endl; cout << y << " in binary is " << bitset<32>(y) << endl; // true if `x` and `y` have opposite signs bool isOpposite = ((x ^ y) < 0); if (isOpposite) { cout << x << " and " << y << " have opposite signs"; } else { cout << x << " and " << y << " don't have opposite signs"; } return 0; } |
Output:
4 in binary is 00000000000000000000000000000100
-8 in binary is 11111111111111111111111111111000
4 and -8 have opposite signs
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class Main { public static String toBinaryString(int n) { return String.format("%32s", Integer.toBinaryString(n)) .replaceAll(" ", "0"); } public static void main(String[] args) { int x = 4; int y = -8; System.out.println(x + " in binary is " + toBinaryString(x)); System.out.println(y + " in binary is " + toBinaryString(y)); // true if `x` and `y` have opposite signs boolean isOpposite = ((x ^ y) < 0); if (isOpposite) { System.out.println(x + " and " + y + " have opposite signs"); } else { System.out.println(x + " and " + y + " don't have opposite signs"); } } } |
Output:
4 in binary is 00000000000000000000000000000100
-8 in binary is 11111111111111111111111111111000
4 and -8 have opposite signs
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
if __name__ == '__main__': x = 4 y = -8 print(f'{x} in binary is {bin(x)}') print(f'{y} in binary is {bin(y)}') # true if `x` and `y` have opposite signs isOpposite = ((x ^ y) < 0) if isOpposite: print(f'{x} and {y} have opposite signs') else: print(f'{x} and {y} don\'t have opposite signs') |
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 (by replacing x by ~x)
The implementation can be seen below in C++ and Java:
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include <iostream> using namespace std; int main() { int x = 4; cout << x << " + " << 1 << " is " << -~x << endl; x = -5; cout << x << " + " << 1 << " is " << -~x << endl; x = 0; cout << x << " + " << 1 << " is " << -~x << endl; return 0; } |
Output:
4 + 1 is 5
-5 + 1 is -4
0 + 1 is 1
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Main { public static void main(String[] args) { int x = 4; System.out.println(x + " + " + 1 + " is " + -~x); x = -5; System.out.println(x + " + " + 1 + " is " + -~x); x = 0; System.out.println(x + " + " + 1 + " is " + -~x); } } |
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++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> using namespace std; void swap(int &x, int &y) { if (x != y) { x = x ^ y; y = x ^ y; x = x ^ y; } } int main() { int x = 3, y = 4; cout << "Before swap: x = " << x << " and y = " << y; swap(x, y); cout << "\nAfter swap: x = " << x << " and y = " << y; return 0; } |
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
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)