Unlock the Power of Bitwise Operations in C: Tips, Tricks, and Real‑World Code

Bitwise operations work directly on the binary representation of integers stored in memory, offering fast, memory‑efficient computation.

Advantages of Bitwise Operations

Much faster than ordinary arithmetic.

Minimal memory usage.

Enable exploitation of binary properties for problem solving.

Low space requirements.

Result in concise, elegant code.

Can represent sets of states.

Operator Symbols in C

Bitwise Operators

a & b

– bitwise AND a | b – bitwise OR a ^ b – bitwise XOR ~a – bitwise NOT a << b – left shift a >> b – right shift (signed)

Operator Precedence

1 – ~ 2 – <<, >> 3 – & 4 – ^ 5 – | 6 – assignment forms ( &=, ^=, |=, <<=, >>=)

Common Bit‑Manipulation Techniques

AND (&)

Test odd/even: if (x & 1) { … } Check a specific bit (e.g., 7th bit): if (n & 0x40) { … } Extract bytes: (x >> 0) & 0xFF, (x >> 8) & 0xFF, …

Power‑of‑two test:

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

Modulo when divisor is 2ⁿ: int remainder = num & ((1 << n) - 1); Masking to isolate a bit: set mask B = 1 << k, then A & B tells whether bit k is 1.

OR (|)

Combine flags or generate a bitmask for state compression.

Count zero bits (example code omitted for brevity).

XOR (^)

Swap two integers without a temporary variable:

void swap(int &a, int &b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

Detect opposite signs: bool diffSign = ((x ^ y) < 0); Simple encryption/decryption: c = a ^ key; Find the unique element in an array where every other element appears twice:

int find(int arr[], int len) {
    int tmp = 0;
    for (int i = 0; i < len; ++i) tmp ^= arr[i];
    return tmp;
}

NOT (~) and Sign‑aware Tricks

Negate a number: int rev = ~a + 1; Branch‑free absolute value:

int abs(int n) {
    return (n ^ (n >> 31)) - (n >> 31);
}

Set a specific bit to 1: n | (1 << (m-1)) Clear a specific bit:

n & ~ (1 << (m-1))

Shift Operations

Compute 2ⁿ: 1 << n Swap high and low bytes: a = (a >> 8) | (a << 8); Bit reversal using masks (sequence of mask‑and‑shift steps).

Get max/min int values:

int maxInt() { return (1 << 31) - 1; }
int minInt() { return 1 << 31; }

Fast integer power using exponentiation by squaring with bit shifts:

int pow(int m, int n) {
    int result = 1;
    while (n) {
        if (n & 1) result *= m;
        m *= m;
        n >>= 1;
    }
    return result;
}

Find the greatest power of two ≤ N by propagating the highest set bit:

int highestPowerOfTwo(int n) {
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return (n + 1) >> 1;
}

Count leading zeros without branches (nlz function).

int nlz(unsigned x) {
    if (x == 0) return 32;
    int n = 1;
    if ((x >> 16) == 0) { n += 16; x <<= 16; }
    if ((x >> 24) == 0) { n += 8;  x <<= 8;  }
    if ((x >> 28) == 0) { n += 4;  x <<= 4;  }
    if ((x >> 30) == 0) { n += 2;  x <<= 2;  }
    n -= x >> 31;
    return n;
}

Bit‑Level Utilities

#define set_bit(x,n) ((x) |= (1 << (n)))

#define clr_bit(x,n) ((x) &= ~(1 << (n)))

#define get_bit(x,n) (((x) >> (n)) & 1)

Further Reading

For an extensive collection of bit‑hacks, see the Stanford Bit Hacks page: http://graphics.stanford.edu/~seander/bithacks.html