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 2. Detect if two integers have opposite signs or not
Problem 3. Add 1 to a given integer
Problem 4. Swap two numbers without using any third variable
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++
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++
|
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> #include <bitset> using namespace std; // main function 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 iff 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
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++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <iostream> using namespace std; // main function 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
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++
|
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> using namespace std; void swap(int &x, int &y) { if (x != y) { x = x ^ y; y = x ^ y; x = x ^ y; } } // main function 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
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