Skip to main content

DSAPath18 minintermediate

Bit Manipulation

Bit manipulation treats integers as binary sets or flags. It is useful for parity, masks, subset enumeration, compact state, and low-level performance-aware code.

DifficultyIntermediate
TierTier 2
ModuleImplementation Patterns
LanguagesPython

Why This Matters

Bit manipulation compresses state. It appears in single-number tricks, subset masks, parity, permissions, board states, bloom-filter-style ideas, and DP over subsets.

The invariant is that each bit position means something specific. Without that mapping, bit tricks are just unreadable arithmetic.

Prerequisite Check

Review Arrays and Iteration. You should know loops, integers, and basic binary place value.

Learning Objectives

By the end, you should be able to:

  • Explain AND, OR, XOR, shift, and complement at the bit level.
  • Use masks to test, set, clear, and toggle bits.
  • Apply XOR cancellation to single-number problems.
  • Enumerate subsets with masks.
  • Avoid signed-integer and language-width traps.

Core Idea

Represent each yes/no feature as one bit. Operations update or query many boolean flags at once.

PatternInvariantTypical problem
XOR cancellationx ^ x = 0 and x ^ 0 = xone unpaired value
Set membership maskbit i means item i is includedsubset enumeration
Lowbitx & -x isolates lowest set bitFenwick trees, bit iteration
Bit countcount set bits in a maskHamming weight, DP over masks

Visual Model

mask = 0b10110
bit 1 set? yes
bit 3 set? no
set bit 3 -> 0b11110

The binary representation is a compact vector of flags.

Non-Example or Failure Mode

Bit tricks are not portable by default across languages with different signed integer widths. Python integers are arbitrary precision; C++ fixed-width signed overflow has different rules. State the language model.

Worked Example

Find the value that appears once when every other value appears twice:

values = [4, 1, 2, 1, 2]
4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)
= 4

LeetCode-Style Problem Patterns

PatternRecognition signalMove
Single numberevery value duplicated except oneXOR all values
Power of twoexactly one set bitx > 0 and x & (x - 1) == 0
Subsets by maskgenerate all choicesloop masks from 0 to 2^n - 1
DP over subsetsstate is a set of chosen itemsmask as DP key

Common Mistakes

MistakeCorrection
Using tricks without naming bit meaning.Document what each bit position represents.
Forgetting parentheses around bit tests.Write explicit comparisons.
Assuming Python signed behavior matches C++.Check fixed-width and overflow semantics.
Using bitmasks when a set is clearer.Prefer readability unless compact state matters.

Diagnostic Questions

Question typeQuestionAnswer signal
DefinitionWhat is a bitmask?An integer whose bit positions encode flags or membership.
Example / non-exampleIs hashing a value the same as bit manipulation?No; bit manipulation directly operates on binary representation or flags.
ComputationWhat is x & (x - 1) used for?It clears the lowest set bit.
ProofWhy does XOR find a single unpaired value?Duplicate values cancel because XOR is associative and a ^ a = 0.
TransferWhy do subset DP states use masks?A set of chosen items becomes a compact integer key.

Exercises

Beginner:

  • Test whether a bit is set at position i.
  • Count set bits in a small integer by hand.
  • Explain why x ^ x = 0 helps with duplicates.

Intermediate:

  • Generate all subsets of a list using masks.
  • Implement power-of-two detection.

Challenge:

  • Use bitmasks for DP over all subsets of n <= 20 items and estimate memory cost.

Diagram Recommendation

Type: bit-position map.

Caption: "Each bit position is a named flag in a compact state vector."

Purpose: Turn opaque bit tricks into explicit state representation.

Implementation Task

Implement masks for subset generation and classic bit predicates. Test edge cases such as zero.

Run bit manipulation patterns

This cell checks XOR cancellation, power-of-two detection, and subset masks.

Output will appear here.

Next Topics

References