AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started

Topic

Bit Manipulation coding problems

Integers are strings of bits, and AND, OR, XOR and shifts read and write them directly.

New to bit manipulation? Read the Bit Manipulation tutorial first.

146 problems · 38 easy · 67 medium · 41 hard · judged by hidden tests in 13 languages

146problems

38 easy

67 medium

41 hard

Sign in to tick off what you solve.

Study plan: 14 problems · about 8 h 10 min

Start the study plan

Next up: Number of 1 Bits

How it works

Bit Manipulation, step by step

Counting set bits, with n & (n − 1) clearing the lowest one

n = 44 (101100 in binary)

32168421n101100= 44count044

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.

0:01 / 0:28Step 1 of 8
Transcript · 8 steps

Study plan

Learn bit manipulation in 8 days

14 of the 146 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 132 in the full list below are practice at your own pace. Then move on to Bitmask.

  1. Day 1

    about 1 h 15 min

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

  2. Day 2

    about 55 min

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

  3. Day 3

    about 1 h 10 min

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

  4. Day 4

    about 1 h 10 min

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

  5. Day 5

    about 1 h 10 min

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

  6. Day 6

    about 50 min

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

  7. Day 7

    about 50 min

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

  8. Day 8

    about 50 min

    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 Coding Problems: 146 Questions with Solutions

146 bit manipulation coding problems — 38 easy · 67 medium · 41 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.

  • Problems: 146
  • By difficulty: 38 easy · 67 medium · 41 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.

New to bit manipulation? Read the Bit Manipulation tutorial first.

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 146 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 132 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 (38)

Medium (67)

Hard (41)

Companies that ask bit manipulation problems

  • Amazon 128 problems on bit manipulation
  • Google 109 problems on bit manipulation
  • Adobe 24 problems on bit manipulation
  • Meta 20 problems on bit manipulation
  • Microsoft 20 problems on bit manipulation
  • Apple 8 problems on bit manipulation
  • TCS 6 problems on bit manipulation
  • Bloomberg 5 problems on bit manipulation
  • Uber 5 problems on bit manipulation
  • Zoho 5 problems on bit manipulation
  • Flipkart 4 problems on bit manipulation
  • Airbnb 3 problems on bit manipulation

Next topic: Bitmask