Bit manipulation interview tricks, explained from zero

In this article

1. Before you start
2. Why interviewers ask this
3. Bit manipulation from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page is one step of the coding interview questions learning path. The code is Python; the ideas carry over to Java and C.

Why interviewers ask this

A single missed edge case, such as zero or a negative number, turns a correct-looking one-liner into a wrong answer. Bit questions are short, so they expose that habit quickly. No public statistics say how often they appear in coding rounds, so treat them as a compact pattern worth learning, not a quota.

A weak answer recites a memorised trick and cannot say why it works. A strong answer explains the trick from what subtraction does to the binary digits, states the edge cases (zero, negative inputs, fixed width) and says when plain arithmetic is clearer. A Staff-level answer also knows where languages differ, for example that Python integers never overflow while Java's do, and prefers the readable version unless a bit trick removes real memory or time.

Bit manipulation from first principles

Bitmask

A bitmask is an integer whose set bits mark the positions of interest, so that combining it with another integer using &, | or ^ tests, sets, clears or flips exactly those positions and leaves every other position unchanged.

Set bit

A set bit is a binary digit with the value one. The lowest set bit is the set bit closest to the right-hand end of the number, the one worth the least. A number's set bits are the ones that remain after you ignore every zero digit.

Popcount

Popcount, short for population count, is the number of set bits in an integer, such as the three set bits in the number written 101100 in binary. It is the standard measure of how many ones a bit pattern holds, and several interview problems reduce to computing it.

In plain words

Picture a row of light switches, each either off (0) or on (1). An integer is that row, read as a binary number. Bitwise operators flip, test or combine the switches one position at a time. The analogy breaks in one place that matters later. Real switches are independent. Subtracting one from a number can change many switches at once, because borrowing ripples leftward.

In one precise sentence, a bitwise operator applies a logical rule to each pair of matching binary digits of its operands and ignores neighbouring positions. Shifts are the exception, because they move every digit sideways. Keep the switch picture in mind through the steps below, and watch for the moments where one operation touches several positions at once.

Step 1: Four operators act per digit; two shifts move the digits

Four operators (&, |, ^, ~) each apply one rule to every binary digit of an integer, position by position, and two shifts (<<, >>) move the digits sideways. & keeps a one only where both inputs have a one. | keeps a one where either input has one. ^ is exclusive-or, and xor is the operation that outputs one only where its two input bits differ. ~ flips every digit; the Java Tutorials describe it as making every 0 a 1 and every 1 a 0.

Take 12 (1100) and 10 (1010). Their & is 8 (1000), their | is 14 (1110) and their ^ is 6 (0110).¹ The two shifts move digits: the Python documentation says a left shift by n bits equals multiplication by 2 to the power n and a right shift equals floor division by the same power. So 1 << 4 is 16 and 7 >> 1 is 3.¹ You now know the vocabulary; the next step uses it for the most reused idiom.

Step 2: Clear the lowest set bit with x & (x - 1)

The expression x & (x - 1) clears the lowest set bit. Subtracting one turns the lowest set bit into zero and turns every zero below it into one, so the two numbers disagree in all of those positions and share the rest. Anding them keeps only the shared part, which is the original number minus its lowest set bit. Wikipedia shows the same pattern.

For 44 (101100) the steps go 44, 40, 32, 0, one set bit removed each time.¹

A number with exactly one set bit is a power of two, so clearing that bit leaves zero. That gives the well-known test, but Anderson's page notes that 0 is incorrectly considered a power of 2 by it, and the fix adds a check. Over the integers from 0 to 64 the naive test accepts 8 numbers and the fixed test accepts 7.¹

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

The same move counts set bits. Each pass of the loop below clears one set bit, so it runs once per set bit.

def popcount(x):
    count = 0
    while x:
        x &= x - 1
        count += 1
    return count

Step 3: A mask sets, clears, toggles or tests one bit

A bitmask built as 1 << k isolates bit position k, counted from zero at the right. Four idioms follow, and each is one operator. Set the bit with x | mask, clear it with x & ~mask, toggle it with x ^ mask, and test it with (x >> k) & 1.

Start from 10 (1010). With k equal to one the mask is 2: setting leaves 10, clearing gives 8, toggling gives 8, and the test returns 1. With k equal to two the mask is 4: setting gives 14, clearing leaves 10, toggling gives 14, and the test returns 0.¹ Oracle's own demonstration masks 0x2222 with 0x000F and prints 2, the low four bits (Java Tutorials).

A mask can also hold a small set. The set of lowercase letters seen so far fits in one integer, one bit per letter, which some sliding-window solutions, such as longest substring without repeating characters, use in place of a set. One more idiom: x & -x isolates the lowest set bit, so for 44 it returns 4.¹

Step 4: xor cancels pairs, so a lone value survives

xor of a value with itself is zero, xor with zero changes nothing, and the order of the operands does not matter. Equal values cancel under xor, so pairs vanish and the single number remains. That solves "every number appears twice except one" in one pass and constant extra memory.

For the list 4, 1, 2, 1, 2 the running xor goes 4, 5, 7, 6, 4, and the answer is 4.¹

def single_number(nums):
    result = 0
    for n in nums:
        result ^= n
    return result

A hash map of counts, for instance a defaultdict, also works but stores one entry per distinct value. Anderson's contents list includes swapping values with xor, but Python's a, b = b, a is clearer, so use the xor swap only if asked. Prefix sums cancel by subtraction in the way xor cancels by repetition; see subarray sum equals k.

1 · Operators2 · Clear lowest set bit3 · Mask4 · xor cancels pairsReplay

Step-by-step description

1. Each operator works on every digit.
2. x & (x - 1) drops the lowest one.
3. A mask clears one chosen position.
4. Pairs vanish; the lone value stays.

• The expression x & (x - 1) clears the lowest set bit.
• Equal values cancel under xor, so pairs vanish and the single number remains.

Worked example

Count the set bits of several numbers two ways: scanning every bit position, and the loop of step two. The scan takes one iteration per binary digit of the number; the loop takes one per set bit. The loop is known as Brian Kernighan's way of counting set bits, and Anderson's Bit Twiddling Hacks lists it under that name. For 1,048,576 the loop runs one time while a scan of every bit position runs 21 times.¹

All values are computed from the integers shown.¹ The case of 255 shows the limit of the trick: with every bit set, the loop saves nothing.

Text description of the diagram

• Kernighan's loop runs once per set bit.
• For 1,048,576 the loop runs one time while a scan of every bit position runs 21 times.

The table below collects the idioms of this page in one place, with illustrative inputs.

All results in the table are computed from the illustrative inputs shown.¹

Trade-offs and edge cases

Bit tricks trade readability for compactness, so use one only when it earns its place. The mistakes below cluster around negative numbers and fixed width.

Two's complement is the scheme computers use to store negative integers, where the pattern for minus x is the pattern for x with every bit flipped and one added. Python behaves as if negatives carry an endless run of leading ones: the Wikibooks Python page gives ~x == -1 * (x + 1), and shows that -2 anded with 15 is 14. So ~5 is -6, ~-2 is 1 and -2 & 0xF is 14.¹

A right shift floors: the Python language reference defines it as floor division by a power of two, so -5 >> 1 is -3, not -2.¹ Python integers have unlimited precision (built-in types), so nothing overflows, and a negative shift count raises ValueError. To mimic 32 bits, mask: ~2 & 0xFFFFFFFF is 4294967293, the same as 0xFFFFFFFD.¹ Java has a zero-filling right shift written >>>, while >> depends on the sign; Java's integer width is fixed, so applying >>> to -5 held in 32 bits gives 2147483645.¹

Text description of the diagram

• Java has a zero-filling right shift written >>>.
• Python integers have unlimited precision.

Subset enumeration is the most common bitmask use: loop a mask from 0 to (1 << n) - 1 and include item i when bit i of the mask is set, which gives 8 masks for n equal to 3.¹ It suits small n only, because the count doubles with every item. For "every number appears three times except one", count each bit position across all numbers and keep the positions whose count mod 3 is 1; the illustrative list 2, 2, 3, 2 gives 3.¹

Other edge cases: the popcount loop never ends for a negative input, because -1 becomes -2, then -4, then -8 and never reaches zero.¹ The Python docs also say that for booleans and, or and != are preferred over &, | and ^. Precedence differs by language. In Java the operator precedence table ranks equality above &, so == binds tighter and you must write (x & 1) == 0; C orders them the same way. In Python the bitwise operators bind tighter than comparisons, though the parentheses cost nothing.¹ Bit position is not byte order, which little-endian covers, and the Python interview questions page lists neighbouring language traps.

How to answer it in an interview

The spoken structure: name the move, say why it works, state the zero edge case, then state the cost and the input assumption.

Common mistakes

• "x & (x - 1) == 0 means power of two." (wrong) It is also true for zero. (right) "I check x > 0 and x & (x - 1) == 0."
• "A right shift by one rounds toward zero." (wrong) In Python it floors, so -5 >> 1 is -3. (right) "A right shift is floor division by a power of two, so negatives round down."
• "~x just flips the bits and gives a positive number." (wrong) In Python it equals -x - 1. (right) "~x equals -x - 1, so ~5 is -6; I mask with & 0xFFFFFFFF when I need a 32-bit view."
• "I'll use the popcount loop on any integer." (wrong) It loops forever on negatives in Python. (right) "I mask a negative input to a fixed width first, or reject it."
• "The popcount loop is how I would count bits in production." (wrong) The loop is the interview answer, not the production one. (right) "In production I call the built-in int.bit_count() or a hardware popcount, and I use the loop to show I understand the trick."

Follow-up questions

How do you count the set bits in an integer?

Repeat x &= x - 1 until x is zero and count the passes, as in the worked example; it loops once per set bit. Python 3.10 and later also offer the built-in undefined method, which is the readable choice outside an interview that forbids it.

How do you find the single number that appears once?

xor every element together. Equal pairs cancel to zero and zero leaves the remaining value unchanged, so for 4, 1, 2, 1, 2 the result is 4 in one pass and constant extra memory.

How do you find the missing number in a list of 0 to n?

xor every number from 0 to n with every element of the list. Matching values cancel and the missing one remains; for the illustrative list 3, 0, 1 with n equal to 3 the result is 2.¹

How do you get the lowest set bit of a number?

Compute x & -x. For 44 (101100) it returns 4 (100), because negation flips every bit above the lowest set bit and keeps that bit.

Why does -5 >> 1 give -3 in Python?

The language reference defines a right shift as floor division by a power of two. Minus five divided by two is minus two and a half, and the floor of that is minus three.

How do you emulate a 32-bit integer in Python?

Python integers are unlimited, so mask results: x & 0xFFFFFFFF keeps the low 32 bits, as the Wikibooks example ~2 & 0xFFFFFFFF == 0xFFFFFFFD shows. Read the result back as signed only if the problem needs it.

Sources

1. Built-in Types: Bitwise Operations on Integer Types (Python 3 documentation) — Python Software Foundation (undated page, accessed 2026-10-26), 26 Oct 2026
2. Expressions: Shifting and Binary bitwise operations (Python Language Reference) — Python Software Foundation (undated page, accessed 2026-10-26), 26 Oct 2026
3. Bitwise and Bit Shift Operators (The Java Tutorials) — Oracle (written for JDK 8, accessed 2026-10-26), 26 Oct 2026
4. Operators (The Java Tutorials, precedence table) — Oracle (written for JDK 8, accessed 2026-10-26), 26 Oct 2026
5. Bit Twiddling Hacks — Sean Eron Anderson, Stanford Graphics (undated page, accessed 2026-10-26), 26 Oct 2026
6. Bit manipulation — Wikipedia (undated page, accessed 2026-10-26), 26 Oct 2026
7. Python Programming/Operators — Wikibooks (undated page, accessed 2026-10-26), 26 Oct 2026