Bits, Numbers, and Geometric Patterns

Representation is part of the algorithm

A fixed-width unsigned word of w bits represents integers from 0 to $2^w-1$. Arithmetic that wraps keeps the result modulo $2^w$. A signed two's-complement interpretation instead assigns the upper half to negative values.

mask = (1 << width) - 1
unsigned = value & mask
signed = (unsigned - (1 << width)
          if unsigned >= (1 << (width - 1))
          else unsigned)

For width=8, masking −1 gives 255; interpreting that word as signed gives −1 again. Specify width before asking to reverse bits or count the ones of a signed word. Leading zeros matter when reversal uses a fixed width. Repeat exactly w times: append the lowest input bit with reversed=(reversed<<1)|(value&1), then shift the input right.

Python integers have arbitrary precision. Bit operations behave as if negative numbers had indefinitely repeated sign bits; ~n equals −n−1. Right shift corresponds to floor division, so −1 shifted right remains −1. These are not unsigned machine-word rules. Python integer representation and shifts ↗

The labs below use explicit small unsigned words. Their numerical models use BigInt, not JavaScript's signed 32-bit number operators. O(1) word operations assume a fixed width; arbitrary-precision work and storage can grow with operand length.

Bits encode flags, not counts

A bit position is not a value. Setting bit 3 stores the flag with numeric weight 8. Repeating the set operation does not store a second occurrence. Use counters when multiplicity matters.

Parentheses make the intended operation explicit. Python's ^ is XOR, not exponentiation; use ** for powers. A negative shift count is invalid.

A subset of n indexed items can be represented by a mask from 0 through $2^n-1$. Include item i exactly when mask & (1 << i) is nonzero. The empty mask includes no items. Enumerating all masks still has 2ⁿ states; materializing each subset can require $O(n2^n)$ total output work and storage.

def mask_subsets(values):
    result = []
    for mask in range(1 << len(values)):
        subset = []
        for i, value in enumerate(values):
            if mask & (1 << i):
                subset.append(value)
        result.append(subset)
    return result

Equal item values at different indices remain different choices in this encoding. Deduplicating value-based subsets is a separate policy. A visited-item mask can also be part of a dynamic-programming state; its possible states still grow exponentially. See Backtracking and Search → for explicit choice ownership and pruning.

Cancel pairs, not arbitrary multiplicities

If every integer appears twice except one, XOR every occurrence. The paired values cancel and leave the unpaired value. The algorithm needs one accumulator under a fixed-width contract, not a set of all previous values.

def single_number(values):
    result = 0
    for value in values:
        result ^= value
    return result

After each step, result is the XOR of the processed prefix. It is not necessarily an input value until the full cancellation contract has been used. Three occurrences do not cancel to zero; an even number cancels, an odd number contributes one copy.

If exactly two distinct values are unpaired, the total XOR is their XOR. Its lowest set bit identifies a position where they differ. Split all inputs by that bit and XOR each group. Every duplicate pair stays together, while the two distinct values separate. A zero total gives no separating bit and violates this particular contract.

For one missing value from the known universe 0..n, XOR that universe and the n supplied values. This works only if exactly one value is absent and every other value occurs once. It does not validate the input or repair multiple omissions and duplicates.

Separate sum bits from carries

At one bit position, XOR gives the addition result before the carry. AND identifies positions where both operands contain 1. Shift those positions left to put each carry at the next weight.

Repeat until the carry is zero. For finite w-bit words, mask both new operands each time. Pending carries move left and eventually leave the word. The result is addition modulo 2^w, not a promise that overflow cannot happen.

The trace adds 13 and 7: (13,7) → (10,10) → (0,20) → (20,0). Eight-bit 255+1 instead returns 0. Signed interpretation must be applied separately to the final word.

Unmasked negative Python integers do not supply the same finite-width termination argument. This algorithm explains a carry mechanism; ordinary + is usually clearer when bit-level addition is not the requested operation.

Remove one set bit at a time

For a positive integer n, n−1 changes its lowest 1 to 0 and the trailing zeros to ones. AND with the original therefore removes exactly that lowest set bit. The expression n & −n instead isolates its weight.

def count_bits(n):
    if n < 0:
        raise ValueError("use a nonnegative integer")
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

The loop runs once per set bit, with zero returning zero. For a negative Python integer, repeatedly clearing bits can continue indefinitely. Reject negative input or mask to a defined finite word first.

Since Python 3.10, int.bit_count() counts ones in the absolute value, which is different from counting ones in a masked signed word. For example, (−1).bit_count() is 1, but an eight-bit representation of −1 has eight ones. Population-count semantics ↗

For counts of every value 0..n, reuse a smaller value: count[i]=count[i>>1]+(i&1). The shift removes the last bit, and the last term contributes that bit's count. This avoids recounting each whole representation.

Locate the next power of two

A positive power of two has exactly one set bit. Therefore n>0 and n & (n−1)==0 tests that property. The positivity condition excludes zero and avoids treating a signed representation as a positive power.

def next_power_of_two(n):
    if n <= 0:
        raise ValueError("n must be positive")
    return 1 << (n - 1).bit_length()

Subtracting one keeps an exact power unchanged. For n=16, 15 has bit length 4, so the answer stays 16. For n=13, 12 also has bit length 4, so the answer is 16. For n=17, 16 needs five bits, so the answer becomes 32. n=1 gives 1.

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

bit_length excludes the sign and leading zeros. The helper deliberately uses a positive domain instead of extending the result to negative inputs. In a bounded integer type, the next power might not fit; check representability before shifting.

Separate a block number from its offset

For alignment a=2^k, the lowest k bits are the offset inside a block. All values 32..39 share a block when a=8; their offsets run from 000 to 111. At 40, the offset returns to 000 and the block number increases.

a−1 has ones exactly in the offset positions. Its complement preserves the block number and clears the offset. For x=37 and a=8, rounding down gives 32.

Rounding up first adds a−1, then rounds down. For 37, adding 7 gives 44, whose aligned lower boundary is 40. An already aligned 40 becomes 47 before clearing and still returns 40. The addition does not imply that every input moves to the next block.

def align_up(x, a):
    if x < 0 or a <= 0 or a & (a - 1):
        raise ValueError("nonnegative x; power-of-two a")
    return (x + a - 1) & ~(a - 1)

Use the same validation for align_down, then return x & ~(a−1). The helper below gives that operation a name. Python gives ~(a−1)=−a; that identity holds for any integer a, but the alignment interpretation requires a power of two. A mask for a=6 does not implement division into six-element blocks.

def align_down(x, a):
    if x < 0 or a <= 0 or a & (a - 1):
        raise ValueError("nonnegative x; power-of-two a")
    return x & ~(a - 1)

For any positive integer a, use down = (x // a) * a and up = ((x + a - 1) // a) * a. These formulas use floor division. Python also gives coherent floor/ceiling multiples for negative x, but address or tensor-size APIs may reject that domain. Other languages can use different signed division rules.

def align_down_arbitrary(x, a):
    if a <= 0:
        raise ValueError("positive alignment required")
    return (x // a) * a

def align_up_arbitrary(x, a):
    if a <= 0:
        raise ValueError("positive alignment required")
    return ((x + a - 1) // a) * a

Padding a tensor dimension to a multiple of 32 gives (dim+31)&~31. Aligning an address down to 256 gives address&~255. Keep units consistent: a dimension counts elements, while a byte address uses byte boundaries. Fixed-width x+a−1 can overflow; validate or use checked arithmetic. Named helpers explain the intent better than unexplained masks, and the trick is not automatically faster.

Remainders preserve common divisors

Euclid's algorithm replaces (a,b) with (b,a mod b). Writing a=q·b+r shows why: a divisor of both a and b also divides r, and a divisor of b and r also divides a. Continue until the remainder is zero.

def gcd(a, b):
    while b:
        a, b = b, a % b
    return abs(a)

def lcm(a, b):
    return 0 if a == 0 or b == 0 else abs(a // gcd(a, b) * b)

For 48 and 18, the pairs are (48,18), (18,12), (12,6), (6,0), so the greatest common divisor is 6. The least common multiple is $\frac{48}{6}\cdot18=144$. Divide before multiplying to reduce intermediate size; the final product can still overflow in a fixed-width type.

The zero guard makes lcm(0,0) well-defined as 0 instead of dividing by zero. gcd(0,0)=0 is the convention used here and by Python. GCD and LCM zero conventions ↗

Trial division extracts prime factors of n≥2. Test factors f while f²≤n, repeatedly divide each factor out, then record any remaining n>1. Dividing repeatedly preserves multiplicity; testing each factor once does not. A large remaining prime needs no further trial factor. In fixed-width arithmetic, f≤n//f avoids overflowing f*f. Values 0, 1 and negative inputs need an explicit policy rather than entering this positive-factor routine.

Reduce arithmetic, not ordinary division

Reduction keeps integers bounded while preserving addition and multiplication modulo m. It does not preserve ordinary division. Dividing by b modulo m requires an inverse, which exists exactly when gcd(b,m)=1.

Fast exponentiation uses the binary digits of a nonnegative exponent. When the last digit is 1, multiply the result by the current base. Square the base and shift the exponent right to process its next digit.

def mod_power(base, exponent, mod):
    if exponent < 0 or mod <= 0:
        raise ValueError("nonnegative exponent; positive modulus")
    result, base = 1 % mod, base % mod
    while exponent:
        if exponent & 1:
            result = result * base % mod
        base = base * base % mod
        exponent >>= 1
    return result

For 3⁵ mod 7, exponent bits select powers 3 and 3⁴, giving 5. The invariant is result·base^exponent congruent to the original requested power. There are O(log(exponent+1)) iterations, not necessarily constant-cost multiplications.

Initialize result to 1%mod so exponent=0 and mod=1 return 0. Reject negative exponents in this loop: Python's right shift would not make them reach zero. Python's built-in pow(base,exp,mod) additionally supports negative integer exponents when a modular inverse exists. That is a different contract, not this loop's behavior. Built-in modular power and inverse conditions ↗

Digits are repeated quotient/remainder steps

For a nonnegative base-ten integer, n % 10 extracts the last digit and n // 10 removes it. Reversing digits accumulates reversed = 10 * reversed + digit. Adding one to a digit array propagates a carry from the last position, stopping when a digit remains below ten.

Separate a negative sign and operate on abs(n). Repeated floor division of −1 by 10 leaves −1, so a naive while n loop never terminates. Define how zero is represented and whether leading zeros must survive. An integer representation loses leading zeros; a string or digit array can preserve them. Palindrome construction copies the chosen left-side digits in reverse order; an odd-length center digit is not copied twice.

Large decimal-string multiplication follows the same local mechanism: multiply digit pairs, accumulate by place value and propagate carries. Converting the whole string to a floating-point number can lose exactness. Reversing into a bounded signed integer needs an overflow check before returning the result.

Repeated states justify cycle shortcuts

A deterministic transition sends the same state to the same next state. Once a state repeats, every subsequent state follows the same cycle. Store previously seen states, or use fast/slow pointers when only detecting a cycle is needed.

For a state sequence $s_0,s_1,\ldots$ with a prefix of length μ and a cycle of length λ, an index $t\ge\mu$ maps to $\mu+((t-\mu)\operatorname{mod}\lambda)$. Finding μ and λ is part of the work; a large t alone does not reveal them.

A finite state space guarantees eventual repetition. An arbitrary integer transform can instead grow forever. For repeated digit-square transforms, establish a bound after enough steps before using a finite-state argument. A visited set stores actual states, not merely a hash whose collisions are ignored.

Fast composition is another mechanism. Squaring a composable transition can evaluate 2,4,8,… steps and combine the selected powers, just as modular exponentiation does. Composition must remain affordable; doubling a huge explicit function table can defeat the intended shortcut.

Matrix order needs explicit boundaries

A rectangular matrix uses row r downward and column c rightward in the diagrams. With C columns, row-major index r * C + c maps a valid cell to one position; r = index // C and c = index % C invert it. Handle C = 0 before dividing. The same index can name a cell in a visited set or a Union-Find structure; the encoding does not define which neighboring cells are connected.

Flattening does not imply sortedness. Binary search over row-major indices requires the entire flattened sequence to be ordered, not just each row. See Binary and Monotonic Search → for the stronger boundary condition.

A clockwise spiral maintains inclusive top, bottom, left and right boundaries. Visit the top edge, advance top; visit the right edge, decrease right. Then recheck the remaining row before visiting bottom, and the remaining column before visiting left.

The checks prevent visiting a collapsed central row or column twice. Every emission belongs to the current remaining rectangle, and every retired boundary has already been visited. The 3×4 trace emits [0,1,2,3,7,11,10,9,8,4,5,6]. Empty matrices emit nothing. One row or column still needs the same checks.

For setting whole rows and columns to zero, marking while immediately zeroing can create false new markers. First record which rows and columns contained an original zero. A constant-extra-space variant uses the first row/column as markers and separate flags for their original zero status; overwrite those marker boundaries last.

Rotate coordinates, not traversal directions

For an n×n matrix, clockwise rotation sends (r,c) to (c,n−1−r). Transpose first to exchange row and column, then reverse each row to move the original row coordinate to the complementary column.

The transposed intermediate rows are [A,D,G], [B,E,H], [C,F,I]. Reversing them produces the displayed result. Reversing rows before transposing instead rotates counterclockwise. An in-place transpose swaps each off-diagonal pair once, not twice.

A rectangular R×C rotation becomes C×R. The coordinate rule generalizes to (c,R−1−r), but the simple in-place square swap routine does not preserve that shape. Allocate a new rectangle or implement a separately justified storage permutation.

Normalize slopes; test orientation exactly

Floating-point slope keys can disagree for the same rational direction. For integer differences (dy,dx), divide both by gcd(abs(dy),abs(dx)), then choose a common sign convention. Require dx>0 for nonvertical directions; use (1,0) for vertical and (0,1) for horizontal.

from math import gcd
def slope_key(dy, dx):
    if dy == dx == 0:
        return None  # Duplicate point; count separately.
    g = gcd(abs(dy), abs(dx))
    dy, dx = dy // g, dx // g
    if dx < 0 or (dx == 0 and dy < 0):
        dy, dx = -dy, -dx
    return dy, dx

(6,4) and (−6,−4) both reduce to (3,2). These keys represent a line's slope, so opposite directions intentionally merge. A directed ray would need a different policy. Duplicate points have no direction and must be counted separately when finding collinear points.

For A=(0,0), B=(2,0), C=(1,1), the result is 2, so the turn is counterclockwise. A screen coordinate system with y increasing downward reverses the visual turn. Do not reuse the sign description without changing that convention.

Squared distance $(x_1-x_2)^2+(y_1-y_2)^2$ compares distances without a square root. Integer arithmetic makes these tests exact only when products and sums fit, or arbitrary precision is used. Floating inputs do not become exact merely because square roots were removed.

Vectors and Geometry → explains the cross product's sign, normal and area. The integer slope key here is an algorithmic representation, not a replacement for those geometric quantities.

Choose a mechanism and check its domain

Tests should include zero, one, exact powers, just-below/above boundaries, negative input policy, duplicate values, single-row/column matrices and coincident points. Compare small masks with set membership, alignment with division, spiral output with an independent walk, and modular powers with a trusted integer implementation.

Choosing Algorithms → connects these mechanisms to the problem's requested output and constraints. Small input sizes permit enumeration; they do not establish a bit, arithmetic or geometric invariant.

Sources and connected concepts

Python integer and bit operations ↗ · Integer bit length ↗ · Bitwise expression rules ↗ · Integer GCD/LCM ↗ · Modular power ↗

Recursive subset enumeration → · Dynamic-programming state design → · Geometric orientation →

The visual traces are exact synthetic examples, not measurements of hardware cost. The snippets state their representation and input contracts; tests compare them with independent small references.