Bit tricks worth knowing

Bits and maths Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
x = 0b10110
print(x & -x, x & (x - 1), x | 1, x ^ (1 << 4), bin(x >> 2))

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 2 20 23 6 0b101

Right: lowest bit 2, clearing it gives 20, setting bit 0 gives 23, flipping bit 4 gives 6, and shifting gives 101.

Each of these is one machine operation, which is why bit tricks replace loops in tight code.

Why not the others?
  • B 2 21 23 6 0b101. x & (x - 1) clears bit 1: 10110 becomes 10100, which is 20.
  • C 1 20 23 38 0b101. The lowest 1 bit of 10110 is worth 2, and flipping bit 4 turns it off.

30-second answer

A handful cover most questions: x & 1 tests odd; x >> k and x << k divide or multiply by 2ᵏ; x & (x - 1) clears the lowest 1 bit; x & -x keeps only the lowest 1 bit; x | (1 << k) sets bit k, x & ~(1 << k) clears it and x ^ (1 << k) flips it; a mask of n bits represents a subset of n items.

Practise saying it · 45 s. No recording, just a timer

Explain common bit tricks.

Say your answer out loud, then check which of these points you covered:

  • Test, set, clear, flip
  • Lowest bit tricks
  • Masks as subsets

Deep dive

Subset masks (0 to 2ⁿ - 1) are how bitmask DP stores 'which items are used'.

Powers of two: x > 0 and x & (x - 1) == 0.

Retry delays that double after each failure are 1 << attempt times a base delay.

Common mistakes

  • Porting x & 1 == 0 between languages without brackets: C and Java group it as x & (1 == 0), while Python binds & tighter than == and groups it as (x & 1) == 0.
  • Assuming 32-bit wrap-around in Python, which has unbounded ints.

Senior take & follow-ups

Write (x & 1) == 0 with brackets. Python already groups it that way, but C and Java do not, so the brackets save a reader from stopping to check.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you iterate over all subsets of a mask?

    Show hint

    sub = mask; while sub: ...; sub = (sub - 1) & mask.

  2. How do you get the lowest set bit's position?

    Show hint

    (x & -x).bit_length() - 1.

What each operation costs: Hash Functions

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.