Bit Manipulation

Concept

Bitwise operators work on individual bits: & AND, | OR, ^ XOR, ~ NOT, << left shift, >> right shift.

Set bit k: x | (1 << k). Clear: x & ~(1 << k). Toggle: x ^ (1 << k). Check: (x >> k) & 1.

x & (x − 1) clears the lowest set bit — used to count set bits and test powers of two. Right-shifting negative signed numbers is implementation-defined; use unsigned.

Cheat sheet

Code (C17)

#include <stdio.h>

int count_bits(unsigned x) {
    int c = 0;
    while (x) { x &= x - 1; c++; }
    return c;
}

int single_number(const int *a, int n) {   // all others appear twice
    int r = 0;
    for (int i = 0; i < n; i++) r ^= a[i];
    return r;
}

int main(void) {
    printf("%d\n", count_bits(29));        // 11101 -> 4
    int a[] = {4, 1, 2, 1, 2};
    printf("%d\n", single_number(a, 5));   // 4
    return 0;
}

Remember

• x ^ x = 0, x ^ 0 = x.
• Use unsigned for bit work.
• x << k multiplies by 2^k.

Interview questions