Common Bit Tricks: Count Bits, Power of Two & XOR

Once you know the bit-manipulation basics, a handful of tricks turn loops into one-liners: counting the set bits (popcount), checking for a power of two, isolating the lowest set bit, and using XOR to cancel duplicates. These are interview staples — each runs in O(1) or O(number of set bits), and recognizing them instantly is what separates a fast solve from a slow one.

Count set bits (popcount)

The number of 1-bits in an integer is its population count. The classic trick n & (n - 1) removes the lowest set bit, so the loop runs once per set bit — O(k) where k is the number of 1s, not the bit width.

int popcount(unsigned int n) {
    int count = 0;
    while (n) { n &= (n - 1); count++; } // clears lowest set bit each step
    return count;
}
// Or simply: __builtin_popcount(n)

int popcount(int n) {
    int count = 0;
    while (n != 0) { n &= (n - 1); count++; } // clears lowest set bit
    return count;
}
// Or simply: Integer.bitCount(n)

function popcount(n) {
  n = n >>> 0; // treat as unsigned 32-bit
  let count = 0;
  while (n !== 0) { n &= (n - 1); count++; } // clears lowest set bit
  return count;
}

def popcount(n):
    count = 0
    while n:
        n &= n - 1          # clears lowest set bit each step
        count += 1
    return count
# Or simply: bin(n).count("1")  /  n.bit_count() in 3.10+

Going deeper: Why does n & (n - 1) clear the lowest set bit? Subtracting 1 flips the lowest 1 to 0 and turns every 0 below it into 1; ANDing with the original keeps everything above untouched and wipes that bottom run.

Check for a power of two

A power of two has exactly one set bit, so n & (n - 1) == 0 — but you must also exclude 0 (and negatives), which would pass the test spuriously.

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

boolean isPowerOfTwo(long n) {
    return n > 0 && (n & (n - 1)) == 0;
}

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

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

Pitfall: Forgetting the n > 0 guard. 0 & (0 - 1) is 0, so 0 would be wrongly reported as a power of two. Negatives also slip through the AND test without the guard.

Isolate the lowest set bit

n & (-n) returns a value with only the lowest set bit of n kept (everything else zeroed). It works because of two’s complement: -n is ~n + 1, which flips all bits above the lowest 1 and matches there. This is the engine behind a Fenwick tree.

int lowestSetBit(int n) {
    return n & (-n); // e.g. 12 (1100) -> 4 (0100)
}

int lowestSetBit(int n) {
    return n & (-n); // e.g. 12 (1100) -> 4 (0100)
}

function lowestSetBit(n) {
  return n & (-n); // e.g. 12 (1100) -> 4 (0100)
}

def lowest_set_bit(n):
    return n & (-n)  # e.g. 12 (1100) -> 4 (0100)

The XOR cancellation trick

XOR’s “a value cancels itself” property solves a whole family of problems. If every element appears twice except one, XOR the whole array — the pairs cancel to 0 and the lone value survives. O(n) time, O(1) space.

int singleNumber(const std::vector<int>& a) {
    int x = 0;
    for (int v : a) x ^= v; // duplicates cancel, the unique one remains
    return x;
}

int singleNumber(int[] a) {
    int x = 0;
    for (int v : a) x ^= v; // duplicates cancel, the unique one remains
    return x;
}

function singleNumber(a) {
  let x = 0;
  for (const v of a) x ^= v; // duplicates cancel, the unique one remains
  return x;
}

def single_number(a):
    x = 0
    for v in a:
        x ^= v   # duplicates cancel, the unique one remains
    return x

Swap without a temporary

A party trick that demonstrates XOR’s reversibility — XOR each variable with the other three times. (In practice prefer a normal swap; this is mostly an interview curiosity.)

void xorSwap(int& a, int& b) {
    if (&a == &b) return; // aliasing would zero the value
    a ^= b; b ^= a; a ^= b;
}

// Java passes primitives by value; swap two array slots instead
void xorSwap(int[] arr, int i, int j) {
    if (i == j) return;
    arr[i] ^= arr[j]; arr[j] ^= arr[i]; arr[i] ^= arr[j];
}

function xorSwap(arr, i, j) {
  if (i === j) return;
  arr[i] ^= arr[j]; arr[j] ^= arr[i]; arr[i] ^= arr[j];
}

def xor_swap(arr, i, j):
    if i == j:
        return
    arr[i] ^= arr[j]
    arr[j] ^= arr[i]
    arr[i] ^= arr[j]

Pitfall: XOR-swapping a variable with itself (same memory/index) zeroes it out. Always guard against aliasing — which is exactly why ordinary swaps are safer.

Quick reference

Trick	Expression	Result
Clear lowest set bit	`n & (n - 1)`	n with its lowest 1 removed
Isolate lowest set bit	`n & (-n)`	only the lowest 1 kept
Is power of two	`n > 0 && (n & (n - 1)) == 0`	true / false
Count set bits	loop `n &= n - 1`	popcount, O(set bits)
Find the unique value	XOR all elements	the unpaired one

When to use it

Counting, parity, and de-duplication problems; subset enumeration; and as primitives inside larger structures like the Fenwick tree. Now put it together with the math & bit-manipulation exercises.