Here are 10 bitwise operator tricks for competitive programming. A thread ⬇️
Before we get started, remember that bitwise operators are really very fast. They are slightly faster than addition (+) and subtraction (-), and a lot faster than multiplication (*), division (/) and modulo (%)
Don't be suprised if 10^9 bitwise operations fit in 1 second.
Don't be suprised if 10^9 bitwise operations fit in 1 second.
1️⃣Check if a number (X) is odd or even
X & 1 = 0 means X is an even number
X & 1 = 1 means X is an odd number
X & 1 = 0 means X is an even number
X & 1 = 1 means X is an odd number
2️⃣Check if a number (X) is a power of 2
X & (X - 1) = 0 means X is a power of 2
X & (X - 1) > 0 means X is not a power of 2
X & (X - 1) = 0 means X is a power of 2
X & (X - 1) > 0 means X is not a power of 2
3️⃣Check if the kth bit in a number (X) is set or unset
(X >> k) & 1 = 0 means kth bit is unset
(X >> k) & 1 = 1 means kth bit is set
Some more cool tricks:
X xor (1 << k) toggles the kth bit
X | (1 << k) sets the kth bit
X & ~(1<<k) unsets the kth bit
(X >> k) & 1 = 0 means kth bit is unset
(X >> k) & 1 = 1 means kth bit is set
Some more cool tricks:
X xor (1 << k) toggles the kth bit
X | (1 << k) sets the kth bit
X & ~(1<<k) unsets the kth bit
4️⃣If number of set bits in A = X, and number of set bits in B = Y, then number of set bits in (A xor B) is even if (X + Y) is even and odd if (X + Y) is odd.
5️⃣Find out the remainder of a number (X) when divided by 2^k
X & ((1 << k) - 1) will give the remainder
Explanation:
(1 << k) = 10000... (k bits)
(1 << k) - 1 = 0111111... (k bits)
Clearly, when you do X & ((1 << k) - 1) this will return the set bits in X before the kth bit.
X & ((1 << k) - 1) will give the remainder
Explanation:
(1 << k) = 10000... (k bits)
(1 << k) - 1 = 0111111... (k bits)
Clearly, when you do X & ((1 << k) - 1) this will return the set bits in X before the kth bit.
5️⃣ Finding number of set bits in a number (X)
__builtin_popcount(X) if X is an integer
__builtin_popcountll(X) if X is a long long
This function returns the number of set bits in O(1). Yes, you heard that right O(1) but this is only available in C++.
__builtin_popcount(X) if X is an integer
__builtin_popcountll(X) if X is a long long
This function returns the number of set bits in O(1). Yes, you heard that right O(1) but this is only available in C++.
6️⃣Two important Identities:
A + B = (A xor B) + 2 * (A & B)
A + B = (A | B) + (A & B)
A + B = (A xor B) + 2 * (A & B)
A + B = (A | B) + (A & B)
7️⃣ Clear all the trailing ones in a number (X)
X & (X + 1) will give a number where all the trailing ones of X will be changed to zeros.
Example:
X = 1011011, X + 1 = 1011100
X & (X + 1) = 1011000
X & (X + 1) will give a number where all the trailing ones of X will be changed to zeros.
Example:
X = 1011011, X + 1 = 1011100
X & (X + 1) = 1011000
8️⃣Multiple and divide a number (X) by 2^k
(X << k) gives X multiplied by (2^k)
(X >> k) gives X divided by (2^k)
(X << k) gives X multiplied by (2^k)
(X >> k) gives X divided by (2^k)
9️⃣Swap two numbers (X) and (Y) without a temporary variable
X = X xor Y
Y = X xor Y
X = X xor Y
X = X xor Y
Y = X xor Y
X = X xor Y
🔟 Have you come across something like:
If (X == A)
X = B
else
X = A
You can do this in one step with this:
X = A xor B xor X
If (X == A)
X = B
else
X = A
You can do this in one step with this:
X = A xor B xor X
In case you found this interesting, don't forget to retweet for your friends.
Also, if you couldn't understand any of them, don't worry, I will be doing a Youtube video on this explaining each of the above in depth. Happy Coding!
Also, if you couldn't understand any of them, don't worry, I will be doing a Youtube video on this explaining each of the above in depth. Happy Coding!
Loading suggestions...