Bit Manipulation Tricks You Should Know

Bitwise operations are usually used in competitive programming but can also help you in high-performance computing. They are significantly faster than arithmetic operations and can help optimize your code for efficiency.

Here are some bit manipulation tricks that you should know:

1. Checking if a Number is Odd or Even

Instead of using modulus (%), check the least significant bit (LSB):

#include <iostream>
using namespace std;

int main() {
    int x = 7;
    if (x & 1)
        cout << x << " is Odd";
    else
        cout << x << " is Even";
    return 0;
}
        

Internal Working: For x = 7 (Binary: 0111):

0111  (7)
0001  (1)
----
0001  (Result: 1, Odd)
        

For x = 8 (Binary: 1000):

1000  (8)
0001  (1)
----
0000  (Result: 0, Even)
        

2. Checking if a Number is a Power of Two

Use:

#include <iostream>
using namespace std;

bool isPowerOfTwo(int x) {
    return (x > 0) && ((x & (x - 1)) == 0);
}

int main() {
    int x = 8;
    cout << (isPowerOfTwo(x) ? "Yes" : "No");
    return 0;
}
        

Internal Working: For x = 16 (Binary: 10000), x - 1 = 15 (Binary: 01111):

10000  (16)
01111  (15)
------
00000  (Result: 0, True - Power of Two)
        

If x is not a power of two, the result will not be 0.

3. Checking if the kth Bit is Set

To check whether the kth bit is set in x:

#include <iostream>
using namespace std;

bool isKthBitSet(int x, int k) {
    return (x & (1 << k)) != 0;
}

int main() {
    int x = 5, k = 2;
    cout << (isKthBitSet(x, k) ? "Set" : "Not Set");
    return 0;
}
        

Internal Working: For x = 5 (Binary: 0101), checking k = 2:

0101  (5)
0100  (1 << 2)
----
0100  (Result > 0, Bit is Set)
        

4. Toggling, Setting, and Unsetting Bits

• Toggle the kth bit: x ^= (1 << k);
• Set the kth bit to 1: x |= (1 << k);
• Unset the kth bit: x &= ~(1 << k);

Example usage:

#include <iostream>
using namespace std;

int main() {
    int x = 5, k = 1;
    x ^= (1 << k); // Toggle k-th bit
    cout << "After toggling: " << x;
    return 0;
}
        

5. Multiplication & Modulus Using Bitwise Operations

• Left shift (x << k) multiplies x by 2^k.
• Right shift (x >> k) divides x by 2^k.
• Instead of x % (2^k), use x & (2^k - 1) for efficiency.

#include <iostream>
using namespace std;

int main() {
    int x = 19, k = 3;
    cout << "x * 2^k: " << (x << k) << endl;
    cout << "x / 2^k: " << (x >> k) << endl;
    cout << "x % 2^k: " << (x & ((1 << k) - 1));
    return 0;
}
        

6. Swapping Two Numbers Without a Temporary Variable

#include <iostream>
using namespace std;

int main() {
    int a = 5, b = 7;
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
    cout << "After swapping: a = " << a << ", b = " << b;
    return 0;
}
        

Internal Working:

a = 5 (0101), b = 7 (0111)
a = a ^ b  →  0101 ^ 0111 = 0010 (2)
b = a ^ b  →  0010 ^ 0111 = 0101 (5)
a = a ^ b  →  0010 ^ 0101 = 0111 (7)
        

7. Efficient Addition Using XOR and AND

#include <iostream>
using namespace std;

int add(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;
        a = a ^ b;
        b = carry;
    }
    return a;
}

int main() {
    cout << "Sum: " << add(5, 7);
    return 0;
}
        

8. Efficiently Counting Set Bits (Population Count)

Most modern processors have a built-in popcount function to count set bits efficiently:

#include <iostream>
using namespace std;

int main() {
    int x = 29;
    cout << "Set bits: " << __builtin_popcount(x);
    return 0;
}
        

For x = 29 (Binary: 11101):

Set bits count = 4 (1s in 11101)
        

These tricks can make your code not only cleaner but also significantly faster. What are your favorite bitwise tricks? Share them in the comments! 🚀