Bitwise Operations: Techniques and Applications in Algorithmic Problems

Bitwise operations are rarely seen in everyday production code or algorithmic problem solving, but when used correctly they can dramatically improve performance and code elegance, giving a "wow" factor in interviews.

What is a bitwise operation? All data in a modern computer is stored as binary. Bitwise operations manipulate the binary representation of integers directly, avoiding conversion to decimal and thus executing very quickly.

Basic bitwise operators include AND (&), OR (|), XOR (^), NOT (~), left shift (<<), and right shift (>>). The following examples illustrate each:

0110
&   0100
-----------
    0100

AND: result is 1 only when both bits are 1.

0110
|   0110
-----------
    0110

OR: result is 1 when at least one bit is 1.

0110
^   0100
-----------
    0010

XOR: result is 1 when the bits differ.

~   0110
-----------
    1001

NOT: flips each bit.

int a = 8;
a << 3;
// before: 0000 0000 0000 0000 0000 0000 0000 1000
// after : 0000 0000 0000 0000 0000 0000 0100 0000

Right shift behaves differently for signed and unsigned integers.

unsigned int a = 8;
a >> 3;
// before: 0000 0000 0000 0000 0000 0000 0000 1000
// after : 0000 0000 0000 0000 0000 0000 0000 0001

int a = -8;
a >> 3;
// before: 1111 1111 1111 1111 1111 1111 1111 1000
// after : 1111 1111 1111 1111 1111 1111 1111 1111

Common bit‑manipulation tricks

1. Check if an integer is even or odd :

if ((x & 1) == 0) {
    // even
} else {
    // odd
}

2. Test whether the n‑th bit is set :

if (x & (1 << n)) {
    // n‑th bit is 1
} else {
    // n‑th bit is 0
}

3. Set the n‑th bit to 1 :

y = x | (1 << n);

4. Clear the n‑th bit (set to 0) :

y = x & ~(1 << n);

5. Toggle the n‑th bit :

y = x ^ (1 << n);

6. Clear the rightmost set bit (useful for counting bits):

y = x & (x - 1);

Example of counting the number of 1‑bits:

count = 0;
while (x) {
    x = x & (x - 1);
    count++;
}

Applying bitwise tricks to algorithmic problems

1. Poison bottle puzzle (8 bottles, 3 mice) – encode bottle indices in binary and feed each mouse the mixture of bottles whose corresponding bit is 1. The pattern of dead/alive mice reveals the poisonous bottle.

2. Check if a number is a power of two – a power‑of‑two has exactly one bit set, so x & (x - 1) == 0 indicates true.

if (x & (x - 1)) {
    printf("%d is NOT a power of two!\n", num);
} else {
    printf("%d is 2^%d!\n", num, log2(num));
}

3. Count bits for all numbers from 0 to n (LeetCode 338) – use the relation bits[i] = bits[i & (i - 1)] + 1 to fill an array in O(n) time.

vector
countBits(int num) {
    vector
bits(num + 1, 0);
    for (int i = 1; i <= num; i++) {
        bits[i] = bits[i & (i - 1)] + 1;
    }
    return bits;
}

4. Solving the 8‑Queens problem with bitmask backtracking – represent columns, left diagonals (pie) and right diagonals (na) as bit masks. At each row compute available positions with ~(col | pie | na) & ((1 << 8) - 1) , pick the rightmost 1‑bit, place a queen, and recurse with updated masks.

void queenSettle(int row, int col, int pie, int na) {
    const int N = 8;
    if (row >= N) { count++; return; }
    int bits = ~(col | pie | na) & ((1 << N) - 1);
    while (bits) {
        int p = bits & -bits; // rightmost 1-bit
        queenSettle(row + 1, col | p, (pie | p) << 1, (na | p) >> 1);
        bits &= bits - 1; // clear the used bit
    }
}

These examples show how bitwise operations can simplify logic, reduce time complexity, and produce highly efficient solutions for common interview and competitive‑programming problems.

Conclusion

Mastering bitwise manipulation not only boosts code performance but also enhances readability when applied appropriately. For further reading, see the links at the end of the original article.