Bit Manipulation Tricks

Check if a Number is a Power of Two

This is the most famous bit hack and the one I use most often. The expression x & (x - 1) clears the lowest set bit. If x is a power of two, it has exactly one set bit, so clearing it gives zero:

// Check if x is a power of two (C, Java, JavaScript)
bool isPowerOfTwo(int x) {
    return x > 0 && (x & (x - 1)) == 0;
}

// How it works:
// x = 16 (0b10000)
// x - 1 = 15 (0b01111)
// x & (x-1) = 0b00000 = 0   is a power of two ✓

// x = 12 (0b01100)
// x - 1 = 11 (0b01011)
// x & (x-1) = 0b01000 = 8   NOT a power of two ✗

// x = 0 (edge case)
// 0 & (0-1) = 0
// The x > 0 check handles this: 0 is NOT a power of two

// Alternative using x & -x (isolate lowest set bit):
bool isPowerOfTwo_v2(int x) {
    return x > 0 && (x & -x) == x;
}

The second version using x & -x is equally valid and works because x & -x isolates the lowest set bit. For a power of two, the lowest set bit is the only bit, so the result equals x itself. I use this in hash table sizing to round up to the next power of two: given a desired capacity, I find the next power of two with a loop or built-in function, then apply this check defensively.

I use the x & -x trick to isolate the lowest set bit so often that it is muscle memory now. Whether I am parsing a bitmask of feature flags or walking through a BIT's update path, that single expression saves me from writing a loop every time.

Brian Kernighan's Algorithm — Counting Set Bits

Counting the number of 1-bits (popcount) is a staple operation. The naive approach checks each of the 32 or 64 bits individually. Brian Kernighan's algorithm is smarter: it runs in O(number of set bits) by repeatedly clearing the lowest set bit until the value reaches zero.

// Brian Kernighan's popcount
int countSetBits(int n) {
    int count = 0;
    while (n) {
        n &= (n - 1);  // clear the lowest set bit
        count++;
    }
    return count;
}

// Example: n = 40 (0b101000)
// Iteration 1: n = 40 & 39 = 32 (0b100000), count = 1
// Iteration 2: n = 32 & 31 = 0,               count = 2
// Result: 2 set bits ✓

// Example: n = -1 (all 32 bits set)
// Iteration 1-32: zeros out one bit each time
// Result: 32 iterations ✓

// Using built-in popcount (preferred when available):
// C:   __builtin_popcount(n);       // GCC/Clang
// C++: std::popcount(n);            // C++20
// Java: Integer.bitCount(n);
// Python: n.bit_count();            // Python 3.8+
// Go:   bits.OnesCount(uint(n));

Swapping Variables Without a Temporary

The XOR swap is a classic bit hack that swaps two integer values using three XOR operations and no temporary variable. It works because XOR is its own inverse: a ^ b ^ b = a.

// XOR swap
void xorSwap(int *a, int *b) {
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}

// Walkthrough: a = 5 (0101), b = 3 (0011)
// Step 1: a = a ^ b     a = 0101 ^ 0011 = 0110 (6)
// Step 2: b = a ^ b     b = 0110 ^ 0011 = 0101 (5) ✓
// Step 3: a = a ^ b     a = 0110 ^ 0101 = 0011 (3) ✓
// Result: a = 3, b = 5

// WARNING: XOR swap breaks if a and b point to the same location!
void xorSwapBroken(int *a, int *b) {
    if (a == b) return;  // guard required!
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}

I should be honest: I never use XOR swap in production code. On modern CPUs, using a temporary variable is faster because it avoids data dependencies between the three XOR operations (the CPU cannot pipeline them). The XOR swap is best treated as an intellectual curiosity and an interview question that demonstrates understanding of XOR properties. For real code, just write int temp = a; a = b; b = temp; — the compiler will optimize it.

Isolate the Rightmost Set Bit

The expression x & -x isolates the lowest set bit of a number. This is the foundation for several other bit hacks, including Fenwick tree (Binary Indexed Tree) implementations and low-level bit pattern generation.

// Isolate the lowest set bit
int lowestSetBit(int x) {
    return x & -x;
}

// Example: x = 40 (0b101000)
// -x = -40
// In 8-bit two's complement: 40 = 0010 1000
//                          -40 = 1101 1000  (~40 + 1)
// 40 & -40 = 0010 1000 & 1101 1000 = 0000 1000 = 8
// Result: 8 — the value of the lowest set bit (bit 3)

// Practical use: iteration over set bits
void forEachSetBit(int x) {
    while (x) {
        int bit = x & -x;          // isolate lowest set bit
        int index = __builtin_ctz(bit);  // count trailing zeros  bit position
        printf("Bit %d is set\n", index);
        x ^= bit;                  // clear that bit for next iteration
    }
}

// Another use: rounding up to the next power of two
// (for positive integers)
int nextPowerOfTwo(int n) {
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n + 1;
}

The x & -x pattern works because of two's complement negation. Flipping bits and adding 1 causes all the trailing zeros in x to become zeros in -x as well, while the lowest set bit in x becomes the only position where both x and -x have a 1. See our two's complement guide for a deeper explanation of why this works.

Clearing and Changing Runs of Bits

Beyond single-bit operations, you sometimes need to clear or set a contiguous range of bits. These patterns are common in register configuration — for example, setting a multi-bit field in a microcontroller's configuration register:

// Create a mask for bits [start, end) (0-indexed from LSB)
uint32_t rangeMask(int start, int end) {
    int width = end - start;
    return ((1 << width) - 1) << start;
}

// Clear bits in a range, then set a value
uint32_t setBitRange(uint32_t reg, int start, int end, uint32_t value) {
    uint32_t mask = rangeMask(start, end);
    reg &= ~mask;          // clear the range
    reg |= (value << start) & mask;  // set new value
    return reg;
}

// Example: set bits 8-15 of a register to 0xA5
uint32_t reg = 0x00000000;
reg = setBitRange(reg, 8, 16, 0xA5);
// reg = 0x0000A500

// Sign-extend a value from N bits to 32 bits
int signExtend(int x, int bits) {
    int shift = 32 - bits;
    return (x << shift) >> shift;
}

// Example: sign extend a 5-bit value
signExtend(0b01101, 5);  // +13
signExtend(0b10011, 5);  // -13 (! it's two's complement in 5 bits)

// Merge two values into bit-aligned halves
int packNibbles(int low, int high) {
    return (low & 0x0F) | ((high & 0x0F) << 4);
}

The setBitRange pattern — clear then OR — is the same approach I showed in the C bitwise guide for register configuration. It prevents unintended modifications to other bits and is the universal pattern for writing to multi-bit fields in hardware registers.