Bit Tricks
Swap two numbers without a temp, check a power of two, count set bits — the classic sleight-of-hand of bit manipulation.
The problem
You are optimizing a hot loop that runs millions of times a second. Profiling points at three tiny operations: swapping two values, checking whether a size is a power of two before resizing a buffer, and counting how many features a user has enabled. Each looks harmless, but multiplied by millions, the temp variables and loops start to show up on the flame graph.
These three chores share a secret. Once you see numbers as rows of bits, each one has a branch-free, allocation-free form that a single CPU can chew through in a handful of cycles. They feel like magic tricks the first time you see them — and then like old friends.
A first attempt
The straightforward versions all lean on extra work. Swapping needs a temp:
def swap(a, b):
tmp = a
a = b
b = tmp
return a, b
def is_power_of_two(n):
if n <= 0:
return False
while n % 2 == 0:
n //= 2
return n == 1
def count_bits(n):
count = 0
while n > 0:
count += n & 1
n >>= 1
return countThe temp variable is cheap but noisy. is_power_of_two loops up to O(log n) times.
count_bits also loops O(number of bits) times — 32 iterations even for a value with a single
bit set. None of these is slow in isolation, but each has a tighter form.
The insight
Powers of two have exactly one bit set: 1000, 0100, 0010. Subtracting one flips that bit
off and turns every lower bit on: 1000 - 1 = 0111. So n and n - 1 share no bits, which
means n & (n - 1) == 0 for powers of two. That same n & (n - 1) expression clears the
lowest set bit — repeat it and you count set bits in as many steps as there are ones, not as
many as there are bits.
And XOR is its own inverse: a ^ b ^ b == a. Apply it three times and two variables trade
places with no temp at all.
How it works
Swap with three XORs
a ^= b folds b into a. b ^= a now sets b = b ^ (a ^ b) = a. Finally a ^= b sets
a = (a ^ b) ^ a = b. The values are swapped, no temp used.
a=0011 b=0101
a ^= b -> a=0110
b ^= a -> b=0011 (original a)
a ^= b -> a=0101 (original b)Detect a power of two with one AND
A positive power of two has a single set bit. n & (n - 1) clears that bit, giving 0. So
n > 0 && (n & (n - 1)) == 0 is the whole test — no loop, no division.
Count set bits by clearing the lowest one
n & (n - 1) erases the lowest set bit each time. Loop until n is 0, counting iterations.
A number with 3 set bits takes exactly 3 iterations, regardless of its magnitude. This is
Kernighan's algorithm.
n = 1101 -> clear lowest -> 1100 (count 1)
n = 1100 -> clear lowest -> 1000 (count 2)
n = 1000 -> clear lowest -> 0000 (count 3)The code
def swap_xor(a, b):
a ^= b
b ^= a
a ^= b
return a, b
def is_power_of_two(n):
return n > 0 and (n & (n - 1)) == 0
def count_bits(n):
count = 0
while n:
n &= n - 1 # clear lowest set bit
count += 1
return count
print(swap_xor(3, 5)) # (5, 3)
print(is_power_of_two(16)) # True
print(count_bits(13)) # 3 (1101)function swapXor(a: number, b: number): [number, number] {
a ^= b;
b ^= a;
a ^= b;
return [a, b];
}
const isPowerOfTwo = (n: number): boolean => n > 0 && (n & (n - 1)) === 0;
function countBits(n: number): number {
let count = 0;
while (n) {
n &= n - 1; // clear lowest set bit
count++;
}
return count;
}
console.log(swapXor(3, 5)); // [5, 3]
console.log(isPowerOfTwo(16)); // true
console.log(countBits(13)); // 3 (1101)class Tricks {
static int[] swapXor(int a, int b) {
a ^= b;
b ^= a;
a ^= b;
return new int[]{a, b};
}
static boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
static int countBits(int n) {
int count = 0;
while (n != 0) {
n &= n - 1; // clear lowest set bit
count++;
}
return count;
}
public static void main(String[] args) {
int[] s = swapXor(3, 5);
System.out.println(s[0] + "," + s[1]); // 5,3
System.out.println(isPowerOfTwo(16)); // true
System.out.println(countBits(13)); // 3
}
}#include <stdio.h>
#include <stdbool.h>
void swap_xor(int *a, int *b) {
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
bool is_power_of_two(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
int count_bits(int n) {
int count = 0;
while (n) {
n &= n - 1; /* clear lowest set bit */
count++;
}
return count;
}
int main(void) {
int a = 3, b = 5;
swap_xor(&a, &b);
printf("%d,%d\n", a, b); /* 5,3 */
printf("%d\n", is_power_of_two(16)); /* 1 */
printf("%d\n", count_bits(13)); /* 3 */
return 0;
}#include <iostream>
void swapXor(int &a, int &b) {
a ^= b;
b ^= a;
a ^= b;
}
bool isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
int countBits(int n) {
int count = 0;
while (n) {
n &= n - 1; // clear lowest set bit
count++;
}
return count;
}
int main() {
int a = 3, b = 5;
swapXor(a, b);
std::cout << a << "," << b << "\n"; // 5,3
std::cout << isPowerOfTwo(16) << "\n"; // 1
std::cout << countBits(13) << "\n"; // 3
return 0;
}Complexity
| Trick | Time | Space |
|---|---|---|
| XOR swap | O(1) | O(1) |
| Power-of-two test | O(1) | O(1) |
| Count set bits (Kernighan) | O(set bits) | O(1) |
Kernighan's loop runs once per set bit — at most the word width, often far fewer.
When to use it
Prefer clarity unless the trick earns its place
The power-of-two check and Kernighan's count are genuinely useful and readable once known.
The XOR swap, though, has a fatal edge case: if a and b are the same memory location,
it zeroes the value out. In real code, prefer std::swap, tuple unpacking, or the language
built-in (popcount, Integer.bitCount, Number intrinsics). Keep these tricks for
interviews and truly hot paths where you have measured a win.
Practice
Recap
n & (n - 1)clears the lowest set bit — the basis for both the power-of-two test and Kernighan's bit count.- XOR is self-inverse (
a ^ b ^ b == a), which powers the temp-free swap. - These are O(1) or O(set bits); reach for language built-ins in production, keep the tricks for hot paths.
How is this guide?
Last updated on