LESSON 26 · PATTERN GUIDE

Bit Manipulation

Use binary representations and bitwise operations to solve compact state and parity problems.

FIRST, LEARN THE PATTERNAND, OR, XOR, shifts, and masks operate on individual bits. XOR cancels equal values because x XOR x is zero.

The task mentions bits, parity, powers of two, compact subsets, or one unique value among duplicates.

How to approach it

Write down the bit pattern, apply one operation at a time, and use masks to isolate or toggle selected bits.

Watch out for

Signed integers and shift behavior vary across languages; know the integer width and sign rules.

A CLOSER EXPLANATION

Bitwise operations work on the binary digits of integer values. A mask selects bits with AND, turns bits on with OR, and XOR toggles or cancels bits. These operations are useful for compact flags and parity, but should be written with the language's integer width in mind.

NOW YOU TRY

Practice question

Every number appears twice except one. What remains after XORing [4, 1, 2, 1, 2]?

EXAMPLEvalues = [4, 1, 2, 1, 2]Give your answer before revealing the explanation.

Show a hint

XOR is associative and commutative, and x XOR x = 0.

Show an answer

4, because duplicate pairs cancel under XOR.

CONNECT IT TO REAL LIFE

Bit Manipulation at work

A device stores four on/off settings in one integer. If the third setting uses mask 0100, how can it check whether that setting is enabled?

Show one possible approach

Compute flags AND 0100 and check whether the result is nonzero. The mask isolates only the third bit.

Practice next

Use these problem IDs to find additional practice for this pattern:

136137191338268190