DSA · Lesson 17 of 17

Bit Manipulation

⏱ 15 min🎬 Interactive chart💻 Python · Java · C++ · JavaScript🧩 4 practice problems

XOR tricks, masks and counting bits. Short, elegant solutions that show you understand how numbers are stored.

The operators

Operator	Meaning	Example (5 = 0101, 3 = 0011)
`a & b`	AND: 1 where both are 1	0001 = 1
`a \| b`	OR: 1 where either is 1	0111 = 7
`a ^ b`	XOR: 1 where they differ	0110 = 6
`~a`	NOT: flip every bit	−6 (two’s complement)
`a << k`	shift left: × 2ᵏ	5 << 1 = 10
`a >> k`	shift right: ÷ 2ᵏ (floor)	5 >> 1 = 2

Tricks worth memorising

x & 1: is x odd?
x & (x − 1): clears the lowest set bit. The loop runs once per 1-bit (Brian Kernighan), and x & (x − 1) == 0 tests for a power of two.
x & −x: isolates the lowest set bit (used by Fenwick trees).
a ^ a = 0 and a ^ 0 = a: XOR cancels pairs. Use it for Single Number and Missing Number, and to swap without a temporary.
(mask >> i) & 1: is bit i set? mask | (1 << i) sets it; mask & ~(1 << i) clears it.
Bitmask subsets: the numbers 0 .. 2ⁿ − 1 enumerate every subset of n items; bit i means “item i is in”.

Code template

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

def popcount(x):
    c = 0
    while x:
        x &= x - 1          # drop the lowest set bit
        c += 1
    return c

def single(nums):
    r = 0
    for v in nums: r ^= v   # pairs cancel
    return r

def all_subsets(items):
    n = len(items)
    return [[items[i] for i in range(n) if mask >> i & 1] for mask in range(1 << n)]

boolean isPowerOfTwo(int x) { return x > 0 && (x & (x - 1)) == 0; }

int popcount(int x) { int c = 0; while (x != 0) { x &= x - 1; c++; } return c; }   // or Integer.bitCount(x)

int single(int[] nums) { int r = 0; for (int v : nums) r ^= v; return r; }

List<List<Integer>> allSubsets(int[] items) {
    List<List<Integer>> res = new ArrayList<>();
    for (int mask = 0; mask < (1 << items.length); mask++) {
        List<Integer> s = new ArrayList<>();
        for (int i = 0; i < items.length; i++) if ((mask >> i & 1) == 1) s.add(items[i]);
        res.add(s);
    }
    return res;
}

bool isPowerOfTwo(int x) { return x > 0 && (x & (x - 1)) == 0; }

int popcount(unsigned x) { int c = 0; while (x) { x &= x - 1; c++; } return c; }   // or __builtin_popcount

int single(const vector<int>& nums) { int r = 0; for (int v : nums) r ^= v; return r; }

vector<vector<int>> allSubsets(const vector<int>& items) {
    int n = items.size(); vector<vector<int>> res;
    for (int mask = 0; mask < (1 << n); mask++) {
        vector<int> s;
        for (int i = 0; i < n; i++) if (mask >> i & 1) s.push_back(items[i]);
        res.push_back(s);
    }
    return res;
}

const isPowerOfTwo = x => x > 0 && (x & (x - 1)) === 0;

function popcount(x) { let c = 0; while (x) { x &= x - 1; c++; } return c; }

const single = nums => nums.reduce((r, v) => r ^ v, 0);

function allSubsets(items) {
  const res = [];
  for (let mask = 0; mask < 1 << items.length; mask++)
    res.push(items.filter((_, i) => (mask >> i) & 1));
  return res;
}

Where it shows up

Single Number, Missing Number, Counting Bits (ans[i] = ans[i >> 1] + (i & 1)), Reverse Bits, Sum of Two Integers without +, subset enumeration, bitmask DP (travelling salesman for n ≤ 20), Gray code.

Language gotchas

Python integers are unbounded: mask with & 0xFFFFFFFF to imitate 32-bit behaviour.
Java has >>> (unsigned shift) as well as >> (sign-extending).
JavaScript bit operators work on 32-bit signed integers: >>> 0 converts to unsigned.

Check yourself: what is 12 & 11, and what does it tell you?

1100 & 1011 = 1000 = 8. The lowest set bit of 12 was cleared, so 12 is not a power of two (the result is not 0).

Practise this pattern (4 problems)

Each problem has a statement, hints, approaches, solutions in 4 languages and a code runner. Solve them in order: easy first.

#	Problem	Difficulty
87	Single Number	Easy
88	Number of 1 Bits	Easy
89	Counting Bits	Easy
90	Missing Number	Easy

🧩 All DSA problems 🎬 Algorithm visualizer 🎓 Certificates

Created by Ajeetkumar