---
title: "Bit manipulation"
url: https://algopath.pro/patterns/bit-manipulation
language: en
summary: "Treat a whole number as a row of switches. Masks, shifts and XOR let you read or flip any one of those switches directly."
updated: 2026-08-24
---

# Bit manipulation

Treat a whole number as a row of switches. Masks, shifts and XOR let you read or flip any one of those switches directly.

## How does Bit manipulation work?

A number is a row of bits, each worth twice the one to its right. Bit i is worth 2 to the power i.

Shifting left by one doubles the number. Shifting right by one halves it and drops the last bit.

AND with a mask keeps only the bits the mask holds. That is how you read a single bit.

OR sets a bit and XOR flips it. A bit XORed with itself always becomes zero.

That last fact is the whole trick behind finding a lone value. Every pair cancels out.

n AND n minus one clears the lowest set bit. Repeating that counts the set bits.

- `n = 1100` Twelve written in binary. Two of its bits are set.
- `n & 1 = 0` The last bit is zero, so the number is even.
- `n >> 2 = 11` Shifting right twice leaves three.
- `n & (n - 1) = 1000` Subtracting one gives 1011, and the AND clears the lowest set bit.
- `two rounds reach zero` So twelve has exactly two bits set.

## When should you use Bit manipulation?

- find the single or unique number using XOR
- set, clear, toggle, or test a bit
- pack many yes/no flags into one integer
- count set bits or check a power of two

## What is Bit manipulation confused with?

- **Hash set / map** - A set answers membership for any key at all. A bitmask does it for 32 known items, with no memory.
- **Math and number theory (GCD, sieve, modular)** - Both work on the number itself. That page is about divisors and primes, this one about bits.
- **Backtracking** - Subsets can be listed by counting from zero upward. Backtracking builds the same list recursively.
- **Non-comparison sort (counting / radix)** - Radix sort reads digits, sometimes as bits. Its goal is grouping, never flipping.

## What is the time and space complexity of Bit manipulation?

One operation is O(1) on a 32-bit value. Looping the bits is O(32), which counts as constant.

## A worked example of Bit manipulation

### Count the set bits of every number

For every number from 0 to n, count how many of its bits are set.

Counting each one separately works, but it repeats a lot of work.

Clearing the lowest set bit gives a smaller number, already counted.

So bits[i] is one more than bits[i AND i minus one].

```javascript
function countBits(n) {
    const bits = new Array(n + 1).fill(0);

    for (let i = 1; i <= n; i++) {
        // i & (i - 1) clears the lowest set bit, so it is always smaller
        bits[i] = bits[i & (i - 1)] + 1;
    }

    return bits;
}
```

## Common mistakes with Bit manipulation

- **Shifting past 31 bits** JavaScript bit operators work on 32 bits and wrap around. Use BigInt beyond that.
- **Forgetting the sign bit** The result of a shift can come back negative. Use the unsigned shift for a plain count.
- **Mixing up AND and OR** AND reads or clears, while OR sets. Getting them backwards gives a silently wrong mask.
- **Reaching for bits when clarity matters** A boolean array reads better and runs just as fast. Use a mask when memory is the constraint.

## Which interview problems use Bit manipulation?

- **Single number** Every pair cancels itself out under XOR.
- **Number of 1 bits** Clear the lowest set bit until nothing is left.
- **Counting bits** Each answer reuses a smaller one already computed.
- **Missing number** XOR the indices against the values.
- **Subsets** Count from zero to two to the power n.
- **Power of two** True exactly when n AND n minus one is zero.
- **Sum of two integers** XOR gives the sum, AND shifted gives the carry.

## JavaScript

```javascript
function findUnique(nums) {
    return nums.reduce((acc, n) => acc ^ n, 0);
}
function setBit(mask, i) { return mask | (1 << i); }
function clearBit(mask, i) { return mask & ~(1 << i); }
function hasBit(mask, i) { return (mask & (1 << i)) !== 0; }
```

## Python

```python
def find_unique(nums):
    acc = 0
    for n in nums:
        acc ^= n
    return acc

def set_bit(mask, i): return mask | (1 << i)
def clear_bit(mask, i): return mask & ~(1 << i)
def has_bit(mask, i): return (mask & (1 << i)) != 0
```

## PHP

```php
function findUnique(array $nums): int {
    $acc = 0;
    foreach ($nums as $n) $acc ^= $n;
    return $acc;
}
function setBit(int $mask, int $i): int { return $mask | (1 << $i); }
function clearBit(int $mask, int $i): int { return $mask & ~(1 << $i); }
function hasBit(int $mask, int $i): bool { return ($mask & (1 << $i)) !== 0; }
```