Skip to content
Hello Python
Algorithm1 Practice1 Interview

Bit Manipulation

Use bitwise operations and binary representations for masks, parity, subsets, and compact state. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Bit Manipulation when the prompt's constraints and required operations match this shape: Use bitwise operations and binary representations for masks, parity, subsets, and compact state.

Pybit demonstrates Bit Manipulation in a professional Python interview workspace.
On this page · Treat Integers as Bit Sets

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Bit Manipulation Code Labs

Treat Integers as Bit Sets

A bit position represents one Boolean flag inside an integer. Build masks with one shifted by the zero-based index and name which position each mask owns.

Test Set and Clear One Bit

Test with AND, set with OR, clear with AND against the inverted mask, and toggle with XOR. Parenthesize shifts and combinations so precedence is visible.

Trace Bit Operations

Reference
def bit_operations(value,index):
    mask=1<<index
    return [bool(value&mask),value|mask,value&~mask,value^mask]
Practice

Implement bit_operations(value,index). Return [tested,set_value,cleared_value,toggled_value] for the selected zero-based bit.

Public tests

  • Apply one explicit mask

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Use XOR for Parity and Cancellation

XOR is associative, commutative, and self-canceling: x XOR x is zero. It can isolate one unpaired value when every other value appears exactly twice, but the frequency premise is essential.

Find the Unpaired Value

Reference
def single_unpaired(values):
    result=0
    for value in values:result^=value
    return result
Practice

Implement single_unpaired(values). Every integer appears twice except one; return the singleton using XOR.

Public tests

  • Cancel equal pairs with XOR

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Handle Python Signed Integers Deliberately

Python integers have arbitrary precision and negative values behave like infinite two’s-complement for bit operations. Apply an explicit width mask when the problem assumes 32 or 64 bits; avoid loops that expect a negative number to shift to zero.

Explain It in an Interview

Say: “This mask owns bit i. AND tests it, OR sets it, AND-not clears it, and XOR toggles it.” For cancellation, state the exact multiplicity contract and derive O(n) time and O(1) space.

Python Version Note

Python 3.11+

The code uses standard Python syntax and containers supported by the browser Judge. The Bit Manipulation proof does not depend on a minor Python release.

Verify in Python docs(opens in a new tab)

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Bit Manipulation complete workflowO(s)O(s)Repeatedly clear the least significant set bit and count transitions.

Space

O(1) for the focused Count Set Bits implementation.

Assumptions

  • For positive value, value & (value - 1) removes exactly one set bit. Repeating reaches zero after exactly the original number of set bits.
  • The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

  1. State the precise Bit Manipulation invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. Each set bit has one documented semantic meaning.
  3. Mask updates do not affect unrelated bit positions.
  4. Use value & (value - 1) to clear one set bit. Preserve this claim after every transition.
  5. Tie loop iterations to the number of set bits. Preserve this claim after every transition.

When To Use Or Avoid Bit Manipulation

Use It When

  • Use Bit Manipulation when this precondition is stated or can be proved: The integer width, sign behavior, and meaning of each bit position are explicit.
  • Use it when this maintained state removes repeated work: Each set bit has one documented semantic meaning.

Choose Another Tool When

  • Avoid Bit Manipulation when this precondition is absent: The integer width, sign behavior, and meaning of each bit position are explicit.
  • Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: The integer width, sign behavior, and meaning of each bit position are explicit.

Avoid

def count_set_bits(value):
    pass

Use instead

def count_set_bits(value):
    count = 0
    while value:
        value &= value - 1
        count += 1
    return count

Where you will hit this: Count Set Bits(opens in a new tab)

Breaking the state transition

Returns whether any bit exists instead of counting all set bits.

Prevent it: Preserve this proof obligation: Each bitwise identity is justified independently for every bit position.

Avoid

def count_set_bits(value):
    return 1 if value else 0

Use instead

def count_set_bits(value):
    count = 0
    while value:
        value &= value - 1
        count += 1
    return count

Where you will hit this: Count Set Bits(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(s).

Avoid

def count_set_bits(value):
    return 1 if value else 0

Use instead

def count_set_bits(value):
    count = 0
    while value:
        value &= value - 1
        count += 1
    return count

Where you will hit this: Shortest Subarray With OR at Least K(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.