// Bit Manipulation

core idea

Operate on a number’s binary representation directly instead of the number’s value. A handful of identities let &, |, ^, <<, and >> do in one step what a loop, a hash set, or a whole extra array would otherwise cost you — usually collapsing an O(n)-space solution down to O(1):

when to reach for it

• The problem demands no extra space, and a HashSet/Dictionary would otherwise be the obvious answer — XOR cancellation deletes it entirely.
• You’re counting or testing individual bits: “how many 1 bits”, “is this a power of two”, “reverse the bits”.
• The statement forbids the normal arithmetic operators and wants the result built from &, |, ^, <<, >> instead (e.g. “add two integers without +”).
• You need an answer for every integer in a range 0..n, and each answer is one bit-shift away from a smaller integer’s answer you’ve already computed.

universal templates

XOR cancellation — pairs vanish, the loner (or the gap) survives:

public int XorCancellation(int[] nums)
{
    int result = 0;
    foreach (int x in nums)
        result ^= x;            // x^x=0 for every pair; XOR is commutative/associative,
    return result;               // so pairing order never matters
}

Clear the lowest set bit — count or process bits one at a time, not 32 times:

public int ClearLowestSetBit(uint n)
{
    int count = 0;
    while (n != 0)
    {
        n &= n - 1;              // n-1 flips every trailing 0 to 1 and the lowest 1 to 0;
        count++;                 // ANDing with the original n zeroes out just that one bit
    }
    return count;
}

Bit-DP recurrence — every value’s answer is a smaller value’s answer plus one bit’s worth:

public int[] BitDp(int n)
{
    var dp = new int[n + 1];
    for (int i = 1; i <= n; i++)
        dp[i] = dp[i >> 1] + (i & 1);   // i>>1 is smaller than i, so it's already filled in
    return dp;
}

problems

Four short problems, each one instance of a skeleton above:

1. 01Single NumbereasyLC #136

   XOR everything — pairs cancel, the loner survives.

2. 02Missing NumbereasyLC #268

   XOR indices against values — everything cancels except the gap.

3. 03Number of 1 BitseasyLC #191

   n & (n−1) clears the lowest set bit; count the clears.

4. 04Counting BitseasyLC #338

   DP on bits: bits[i] = bits[i >> 1] + (i & 1).