Bit Manipulation

An integer is a row of 32 or 64 on/off flags, and the machine works on all of them at once. AND, OR, XOR and shifts each cost one instruction, so questions about which bits are set run in constant time per number.

Trick	Expression	What it does
XOR cancels	a ^ a == 0, a ^ 0 == a	Pairs vanish, the odd one out survives
Lowest set bit	n & (n - 1)	Clears it, so a loop runs once per set bit
Mask as a set	n & (1 << k), n | (1 << k)	Test or add member $k$

The sign bit is the usual trap. JavaScript truncates bitwise operations to signed 32 bits and Java has no unsigned int, so a set bit shifted into the top position turns the number negative, and a loop that shifts right needs >>> to ever reach zero. Also remember that a number's binary digits already write it as the fewest powers of two that sum to it, and any single power $2^k$ can be split into two $2^{k-1}$ pieces when you need more terms.

Approach	Time	Extra space
Check all 32 positions	$O(32)$ per number	$O(1)$
Clear the lowest bit until zero	$O(\text{set bits})$ per number	$O(1)$
Reuse bits[n >> 1]	$O(1)$ per number	$O(n)$ table

Use XOR when equal values pair off and cancel, and bitmasks when the rule depends on which bits are set or how a number decomposes into powers of two.

The problems below start with XOR cancellation and the lowest-set-bit loop, move through decomposing into powers of two, reusing earlier bit counts, and reducing a number by adding or subtracting powers of two, and end with matching bit prefixes against an upper bound.