Overview

Every integer is a row of bits, and processors operate on all of them at once. Bitwise operators — AND, OR, XOR, NOT and shifts — let you test, set and clear individual bits in O(1), pack a set of up to 64 flags into one number, and spot patterns that are invisible in decimal.

A few identities do most of the work. x ^ x = 0 and x ^ 0 = x, so XOR-ing a list cancels every pair and leaves the odd one out. x & (x − 1) removes the lowest set bit, so a loop of it counts set bits. And the integers from 0 to 2ⁿ − 1, read as bitmasks, enumerate every subset of n items.

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
Any single bitwise operationO(1)
Count set bits (Kernighan)O(number of set bits)
Enumerate all subsets of nO(2ⁿ)

Patterns to recognise

XOR to cancel pairs

Use it for: Single number, missing number, find the difference.

XOR everything together; duplicates disappear.

Bit-by-bit construction

Use it for: Reverse bits, single number II, sum of two integers.

Process bit positions 0..31 independently and rebuild the answer.

Mask enumeration

Use it for: Subsets, maximum product of word lengths.

Encode each item's properties as a mask; compare with a single AND.

Code template

Single Number and Counting Bits
def single_number(nums):
    result = 0
    for x in nums:
        result ^= x              # pairs cancel out
    return result


def count_bits(n):
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        bits[i] = bits[i >> 1] + (i & 1)
    return bits

Common mistakes

  • Operator precedence: in C++/Java, x & 1 == 0 means x & (1 == 0) — always parenthesise.
  • Python integers are unbounded, so negative numbers never "wrap"; mask with 0xFFFFFFFF to emulate 32-bit behaviour.
  • Shifting a 32-bit int by 32 or more is undefined in C++; use 1LL << i for large i.

Quick check

Three questions on Bits. Get all three right to earn +15 XP.

  1. What does x & (x - 1) do?

  2. XOR-ing every number in an array where each value appears twice except one gives:

  3. Which expression tests whether x is a power of two?

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on Bits?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor