Bit Manipulation Tricks

We’ll assume:

int x;       // some non-negative integer
int k;       // 0-based bit index (0 = least significant bit)

and use masks like 1 << k which has only bit k equal 1.

Checking if a Bit is 1

bool isSet = (x >> k) & 1;
  • x >> k → shift right so that the k-th bit comes to the rightmost position.
  • (x >> k) & 1 → keeps only the rightmost bit, zeroes everything else.
  • The result is 0 or 1, which is the same as false or true.

Examples

Check if bit 1 of x is set.

int x = 10;     // 10 = 1010 (in binary)
int k = 1;

bool isSet = (x >> 1) & 1; // 1010 >> 1 = 101;  101 & 1 = 1 (true)

Given n and k, write a function that determines if the k-th bit of n is set.

bool kthBitIsSet(int n, int k) {
    return (n >> k) && 1;
}

Setting the k-th Bit to 1

x |= (1 << k);
  • | sets bits where either side has 1.
  • So we force bit k to 1, leave others unchanged.

Example

int x = 4;      // 0100
x |= (1 << 0);  // 0100 | 0001 = 0101 (5)

Clearing the k-th Bit (Set it to 0)

x &= ~(1 << k);
  • 1 << k → mask with bit k equal 1.
  • ~(1 << k) → mask with bit k equal 0, all others equal 1.
  • & with that mask clears bit k.

Example

int x = 13;         // 1101
x &= ~(1 << 2);     // ~(0100) = ...1011
                    // 1101 & 1011 = 1001 (9)

Now bit 2 is 0.

Toggling (Flipping) the k-th Bit

x ^= (1 << k);

  • ^ (XOR) flips a bit if the mask has 1:

    • 0 ^ 1 = 1
    • 1 ^ 1 = 0

Example

int x = 5;     // 0101
x ^= (1 << 2); // 0101 ^ 0100 = 0001 (1)

Bit 2 was 1 → now 0.

Remove the Lowest Set Bit

This is a very famous trick.

x = x & (x - 1);

This clears the lowest (rightmost) 1-bit in x.

Why This Works

Think about what happens to the bits when you subtract 1:

  • When you do x - 1, you scan from the right until you find the first 1-bit.
  • That lowest 1-bit becomes 0.
  • All the bits to the right of it (which were 0s) become 1s (because of borrowing).

So around the lowest set bit, the pattern looks like this:

x:       .... 1 0 0 0 0
x - 1:   .... 0 1 1 1 1

Now AND them:

x        = .... 1 0 0 0 0
x - 1    = .... 0 1 1 1 1
-------------------------
x&(x-1)  = .... 0 0 0 0 0
  • The lowest 1-bit becomes 0 because it’s 1 & 0.
  • All bits to the right are 0 in x and something in x - 1, so they also become 0.
  • All bits to the left of that position are unchanged, because subtraction didn’t touch them (same bits in both x and x - 1).

So x & (x - 1) is just x with its rightmost 1-bit cleared.

Example

x           = 12 = 1100
x - 1       = 11 = 1011
x & (x - 1) =  8 = 1000

So we removed the lowest 1-bit (bit 2).

Check if x is a Power of Two

We assume x is a positive number, and use the previous trick.

bool isPowerOfTwo = (x & (x - 1)) == 0;

Why this works:

  • A power of two in binary (1, 10, 100, 1000, …) has exactly one bit set.
  • If you do x & (x - 1) it removes the lowest set bit.
  • If there was exactly one set bit, result becomes 0.

So:

  • “x & (x - 1) is 0” ⇔ “x has exactly one set bit”.

Examples

  • x = 8 (1000) → x & (x-1) = 1000 & 0111 = 0000 → power of two.
  • x = 12 (1100) → x & (x-1) = 1100 & 1011 = 1000 → not zero → not a power of two.

Get the Lowest Set Bit Only

int lowest = x & -x;

Here -x is the two’s-complement negative of x.

Pattern:

  • x & -x isolates the rightmost 1-bit and zeroes everything else.

Example

x                = 12 = ...00001100
-x (two's complement) = ...11110100
x & -x                = ...00000100 = 4

So the lowest set bit corresponds to value 4 (bit 2).

Quick Summary

  • Check bit k: isSet = (x >> k) & 1;
  • Set bit k: x |= (1 << k);
  • Clear bit k: x &= ~(1 << k);
  • Toggle bit k: x ^= (1 << k);
  • Remove lowest set bit: x &= (x - 1);
  • Check power of two: x > 0 && (x & (x - 1)) == 0
  • Get lowest set bit: lowest = x & -x;

These are the the most important bit manipulation tricks.