Bit Manipulation & Math

Two's complement gives the top bit a weight of -128, so the 256 patterns split into 128 negatives (-128 to -1) and 128 non-negatives. Zero uses one non-negative pattern, leaving only 127 positives — so -128 has no positive counterpart.

Use n = n & ~(1 << k). The shifted mask holds a single 1 at position k; inverting it gives all ones except there, so the AND forces that bit to 0 and leaves the rest unchanged.

The shift moves the field down to bit 0 so it reads as a number; the mask clears the neighbouring fields still sitting above it. Shift alone leaves garbage on top, mask alone leaves the value scaled.

Permutations count arrangements where order matters; combinations count selections where it does not. A ranked top-3 podium from 30 entrants gives 30 x 29 x 28 = 24,360 outcomes; an unordered shortlist of three gives only 4,060.

Binary floating-point cannot hold most decimal fractions exactly, so every operation rounds. Two totals summed in different orders accumulate different rounding error and end up a few bits apart even when the algebra says they match. Compare with a tolerance.

Fixed-width integer arithmetic wraps: once a running total passes the largest representable value it continues from the most negative one. Nothing checks for this by default, so the sum is simply wrong from that point on.

Every common divisor of a and b also divides a mod b, and every common divisor of b and a mod b also divides a. The two pairs therefore have exactly the same common divisors, and so the same greatest one.

In truncated-division languages the remainder carries the sign of the dividend, so a day offset that lands left of zero yields a negative result. Normalize with ((x % 7) + 7) % 7 to map any integer into 0..6.

Divisors come in pairs whose product is n, so any divisor larger than the square root of n is paired with one smaller than it. Testing up to the square root therefore finds a factor whenever one exists.

XOR is self-inverse (x xor x = 0), has identity 0, and is commutative and associative. So the fold can be reordered to put duplicates side by side; every pair collapses to 0 and only the unpaired value survives.

Every n-bit integer is a distinct in-or-out choice for each of the n elements, and counting from 0 to 2^n - 1 visits every n-bit pattern exactly once. The number itself is the subset; no list is built.

Each pass clears the lowest set bit of n and leaves every other bit alone, so the loop runs exactly once per set bit — the population count — not once per bit of the word width.

An arithmetic right shift rounds toward negative infinity; truncating integer division rounds toward zero. They agree on non-negative values and when the division is exact, but for -7 the shift gives -4 and the division gives -3.

A fixed absolute epsilon only works in a narrow magnitude band: near 1e12 adjacent 64-bit floats are further apart than 1e-9, while near zero the same epsilon calls wildly different values equal. Use a relative tolerance with an absolute floor.

Operand width, not destination width, decides where arithmetic happens. A product of two 32-bit values is formed in 32 bits and wraps there; widening afterwards faithfully copies the already-wrong result. Widen at least one operand before multiplying.

Reducing every step and reducing once at the end give the same answer but not the same intermediates. With both factors below the modulus every product fits a fixed-width accumulator; deferring reduction lets the running value overflow silently.

Every multiple of p below pp has a prime factor smaller than p, so it was already crossed out when that smaller prime was processed. Starting at pp skips guaranteed-redundant work without ever missing a composite.

Fold the expected numbers 1..n and the received ones into a single XOR accumulator. Every delivered number then appears exactly twice and cancels, so the accumulator ends holding the one sequence number that never arrived.

The bits never change — the interpretation does. Unsigned reading weights the top bit +128, so 11001000 is 200. Two's complement weights the same bit -128, giving -128 + 64 + 8 = -56. Signedness is a property of the reading, not the byte.

Sign extension copies the sign bit into every new high-order bit when widening, which preserves the two's-complement value. Zero-filling instead reinterprets a negative as a large positive: the 16-bit value -200 arrives in 32 bits as 65336.

Zero slips through, and on a signed word so does the most-negative value. The expression only asserts "at most one bit is set", so the real power-of-two test needs the guard n > 0 in front of it.

It tests the lowest bit of flags, not the ACK bit. The comparison binds tighter, runs first and yields 1, so the line reduces to flags AND 1 — a silent bug that still compiles.

The factorials overflow long before the answer does. Choosing 6 winners from 30 entrants is only 593,775, yet 21! already exceeds a 64-bit signed integer. The multiplicative form interleaves multiplying and dividing, keeping every intermediate value near the answer's size.

Every comparison involving NaN is false, so a NaN seed pins the running maximum at NaN forever, while a NaN arriving later is silently skipped. Infinity compares as an ordinary value and wins every comparison. Neither is reported as an error.

Signed fixed-width ranges are asymmetric — there is one more negative value than positive. Negating the most negative value has no representable result, so it wraps back to itself, and absolute value hands you that same negative number.

One remainder step collapses a whole run of subtractions. After the first swap each remainder is strictly less than half the dividend it came from, so the values shrink geometrically and the step count is logarithmic, not proportional to a/b.

Both forms are mathematically equal, but the product a * b can overflow a fixed-width integer before the division ever runs. Dividing first is exact, because the gcd divides a, and keeps every intermediate no larger than the answer.

Congruence survives addition, subtraction and multiplication, so reducing after each of those is exact. Division is not an operation on residues: it needs a modular inverse, which exists only when the divisor shares no factor with the modulus.

Factor the number into primes, then multiply every exponent plus one. A value equal to 2^3 * 3^1 has (3+1)(1+1) = 8 divisors, because a divisor picks each prime's exponent independently, anywhere from zero up to the one available.