Get started

Bit Manipulation Coding Problems: 83 Questions with Solutions

83 bit manipulation coding problems — 34 easy · 40 medium · 9 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.

  • Problems: 83
  • By difficulty: 34 easy · 40 medium · 9 hard
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

Integers are strings of bits, and AND, OR, XOR and shifts read and write them directly. Counting set bits, finding the one number that appears once (XOR cancels pairs), testing a power of two, building subsets from a bitmask and reversing bits are the standard moves; the problems here practise them and the operator precedence and sign rules that make them go wrong.

How bit manipulation works, step by step

32168421n000000= 0count344 → 40 → 32 → 0
Counting set bits, with n & (n − 1) clearing the lowest one. Example: n = 44 (101100 in binary)
  1. Count the 1 bits of 44 = 101100. Checking every position takes a step per bit; instead, n & (n − 1) deletes the lowest 1 bit in a single operation, so the loop runs once per 1 bit until n reaches 0.
  2. 44 − 1 = 43: subtracting 1 borrows from the lowest 1 bit (the 4s place), which becomes 0 while every 0 below it becomes 1. The bits above it are untouched.
  3. AND keeps a bit only where both rows have a 1: the higher bits survive and the flipped region is all 0s. 44 & 43 = 40 = 101000 — exactly one 1 bit is gone, so count = 1.
  4. Now n = 40 = 101000, whose lowest 1 bit is the 8s place, so 40 − 1 = 39 flips the 4 bits from there down. The bits above it are still untouched.
  5. The AND wipes the 4 flipped bits again: 40 & 39 = 32 = 100000, one fewer 1 bit, so count = 2.
  6. Now n = 32 = 100000, whose lowest 1 bit is the 32s place, so 32 − 1 = 31 flips the 6 bits from there down. No 1 bit sits above it any more.
  7. The AND wipes the 6 flipped bits again: 32 & 31 = 0 = 000000, one fewer 1 bit, so count = 3. Nothing is left, so the loop ends.
  8. n reached 0 after 3 rounds, so 44 has 3 set bits. The loop runs once per 1 bit — O(k) for k set bits instead of O(log n) for every bit — and the same trick tests for a power of two: n & (n − 1) == 0.

Bit Manipulation study plan

14 of the 83 Bit Manipulation problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 69 in the full list below are practice at your own pace. Then move on to Bitmask.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 5

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 6

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Day 7

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Day 8

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Next topic: Bitmask

Bit Manipulation: the essentials

When to reach for it

Values that fit a machine word with a question about their binary form; "every element appears twice except one"; a set of at most about 20 items whose subsets must all be tried (2²⁰ is about a million); flags packed into one integer; "add without the + and - operators".

The pattern

A handful of identities do most of the work. x & (x - 1) clears the lowest set bit and x & -x isolates it; x ^ x is 0 and x ^ 0 is x; (x >> i) & 1 reads bit i and x | (1 << i) sets it. XOR over a list cancels every value that appears an even number of times. Masks from 0 to (1 << n) - 1 enumerate every subset of n items, bit i saying whether item i is in.

def count_bits(n):                  # set bits of every value 0..n
    ans = [0] * (n + 1)
    for i in range(1, n + 1):
        ans[i] = ans[i & (i - 1)] + 1
    return ans

Cost

Bitwise operations are O(1) on a machine word; looping over bits is O(word size), and enumerating subsets is O(2ⁿ × n).

Common mistakes

  • Precedence: in C, C++, Java and JavaScript, == binds tighter than &, so x & 1 == 0 does not test the low bit. Parenthesise every bitwise expression.
  • Shifting negatives: >> keeps the sign in Java and JavaScript; >>> shifts in zeros. Python integers are unbounded, so mask with & 0xFFFFFFFF to imitate 32 bits.
  • JavaScript's bitwise operators work on 32-bit signed values, so 1 << 31 is negative.
  • 1 << 40 overflows a 32-bit int in Java or C++; write 1L << 40 or 1LL << 40.

Start with

All bit manipulation problems

Easy (34)

Medium (40)

Hard (9)

Companies that ask bit manipulation problems

  • Amazon 77 problems on bit manipulation
  • Google 55 problems on bit manipulation
  • Adobe 24 problems on bit manipulation
  • Meta 18 problems on bit manipulation
  • Microsoft 13 problems on bit manipulation
  • Apple 7 problems on bit manipulation
  • TCS 6 problems on bit manipulation
  • Uber 5 problems on bit manipulation
  • Zoho 5 problems on bit manipulation
  • Bloomberg 4 problems on bit manipulation
  • Flipkart 3 problems on bit manipulation
  • Cognizant 2 problems on bit manipulation

Next topic: Bitmask