Bit Manipulation
7 questions. The shortest solutions in the set, and the ones where a Java-specific detail decides correctness more often than the algorithm does.
The three Java facts that decide four of these problems
| Fact | Bites in |
|---|---|
>> is arithmetic — -1 >> 1 is still -1 | Q2: while (n != 0) { n >>= 1; } never terminates for negative input |
int overflow wraps silently, no exception | Q5 (Gauss sum), Q7 (the accumulator) |
% keeps the sign of the dividend — -123 % 10 is -3 | Q7: removes all sign handling, for free |
A fourth, less often stated: Math.abs(Integer.MIN_VALUE) is negative. Two's complement has one more negative value than positive, so MIN_VALUE has no representable magnitude. That single fact breaks the natural "strip the sign, work with the absolute value, reapply" structure in Q7.
The >> versus >>> question, answered precisely
The usual advice is "always use >>>". That's a fine habit and a bad explanation — and testing it produced the one result in this section that contradicted what I was about to write.
| Loop shape | Does the shift matter? |
|---|---|
while (n != 0) | Yes — fatally. >> stalls at -1 and never terminates |
for (int i = 0; i < 32; i++) | No. Bit 0 of n >> k is the original bit k for every k <= 31 |
a standalone expression, e.g. (n & 0xFFFF0000) >> 16 | Yes. Sign extension corrupts the result; no loop bound protects you |
Measured: with a fixed 32-iteration loop, >> and >>> gave identical results on all 21,777,223 values tested. With while (n != 0), >> failed to terminate on 100,305 of 200,000 random ints — exactly the negative half.
The trap lives in the loop condition, not in the shift.
XOR, used three different ways
XOR over 32-bit integers is an abelian group in which every element is its own inverse. Three properties, and each buys something specific:
| Law | Buys |
|---|---|
x ^ x = 0 | duplicates erase themselves |
x ^ 0 = x | 0 is the correct accumulator seed |
| associative + commutative | the input needn't be sorted |
- Single Number — the duplicates are in the array.
- Missing Number — the duplicates are supplied by the range
0..n. - Both follow-ups partition on
x & -x, the lowest set bit, to separate two survivors.
Per bit, XOR is parity. That's why "every element appears three times" needs a different tool entirely — mod 2 can't count to 3.
One identity, reused three times
n & (n − 1) clears the lowest set bit
n & -n isolates the lowest set bitSubtracting 1 flips the lowest 1 to 0 and turns the zeros below it into ones; the AND keeps only what's above.
| Used as | Where |
|---|---|
| a loop step | Number of 1 Bits — runs once per set bit, not per bit position |
| a DP recurrence | Counting Bits — dp[i] = dp[i & (i-1)] + 1, which is the loop memoised |
| a predicate | n > 0 && (n & (n-1)) == 0 tests for a power of two |
| a partition key | Single Number's two-singleton follow-up |
Verified: the Kernighan loop runs exactly Integer.bitCount(n) iterations on 200,000 random values.
Every Counting Bits recurrence is "strip a bit, reuse the answer"
| Strip | Recurrence |
|---|---|
| the last bit | dp[i] = dp[i >> 1] + (i & 1) |
| the lowest set bit | dp[i] = dp[i & (i-1)] + 1 |
| the highest set bit | dp[i] = dp[i - offset] + 1 |
All three are O(n) and all three were verified against Integer.bitCount for every value up to 100,000. The first needs nothing but the definition of binary, which is why it's the one to write.
Addition is XOR plus a relocated carry
a + b = (a ^ b) + ((a & b) << 1)Apply it to itself until the carry is 0. It terminates because the carry marches strictly left and falls off the end of the int after at most 32 shifts — measured worst case: exactly 32 iterations, attained by 1 + (-1).
Negatives need no handling. Two's complement was designed so one adder serves signed and unsigned alike, and the identity is defined on bit patterns. The function also reproduces Java's overflow rather than avoiding it, which is the correct behaviour for a + replacement.
Overflow you have to predict, not detect
int arithmetic wraps silently, so once res * 10 has overflowed the original value is gone. With 64-bit integers forbidden, the check must run before the multiply:
if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && digit > 7)) return 0;MAX_VALUE / 10 is 214748364 and MAX_VALUE % 10 is 7; the negative mirror is −214748364 and −8, and the asymmetry is real. Without the guard the function is wrong on about 42% of random ints — returning a plausible wrapped value, never an error.
An honest footnote that came out of testing: for 32-bit input the digit > 7 and digit < -8 clauses never actually fire — the coarse comparison catches every real overflow first. Verified on 6 million values. They stay in because the code should state the correct condition, not one that happens to be sufficient at this width.
Complexity
| Question | Time | Space |
|---|---|---|
| Single Number | O(n) | O(1) |
| Number of 1 Bits | Θ(popcount), ≤ 32 | O(1) |
| Counting Bits | O(n) | O(1) auxiliary |
| Reverse Bits | Θ(32), or O(1) with the swap version | O(1) |
| Missing Number | O(n) | O(1) |
| Sum of Two Integers | O(32), usually far less | O(1) |
| Reverse Integer | O(d), d ≤ 10 | O(1) |
Everything here is O(1) space and single-pass. The interest is entirely in constants and in correctness at the boundaries.
The traps
| Trap | Symptom |
|---|---|
while (n != 0) { n >>= 1; } (Q2) | Never terminates for negative input — 100,305/200,000 random ints |
(n & mask) >> k in a standalone expression (Q4) | Sign extension corrupts the high bits |
while (n != 0) to reverse bits (Q4) | reverse(1) returns 1, not 0x80000000 — and {0} doesn't catch it |
Integer.toBinaryString without padding (Q4) | Leading zeros dropped; the reversal is wrong |
Integer.parseInt(s, 2) on 32 bits (Q4) | Throws when the top bit is set — needs parseUnsignedInt |
dp[i] = dp[i >> 1] + 1 (Q3) | 99,984 of 100,001 entries wrong |
dp[i >> 1] + i & 1 without parentheses (Q3) | Parses as (dp[i>>1] + i) & 1; gives 1 instead of 3 at i = 13 |
n * (n+1) / 2 in int (Q5) | Overflows at n = 65,536, silently yielding 32,768 |
Loop to < n instead of <= n (Q5) | Misses the case where the answer is n itself — [0,1] |
Computing the carry after reassigning a (Q6) | Reads the new value; result is garbage |
| No overflow guard (Q7) | Wrong on 42% of random ints — a wrapped value, not an error |
Math.abs(x) to strip the sign (Q7) | Math.abs(MIN_VALUE) is still negative |
v % 2 on an unmasked negative long (Q2) | Returns −1 for odd negatives; wrong on 249,203/500,000 |
Verification
Every snippet compiled and cross-checked against Integer.bitCount, Integer.reverse, +, −, and a long-based reference — over 30 million evaluations:
- Q2 across the fixed 32-scan, Kernighan, SWAR and masked division — all of
[0, 2^22), 2M random 32-bit values, and the boundary set - Q4 across the loop, the divide-and-conquer swap, a string round-trip and a 64 KB lookup table — all of
[0, 2^22)plus millions of random values, with involution (reverse(reverse(n)) == n) and popcount preservation asserted on every one - Q6 across the loop, the recursion, an explicit full adder and subtraction — 3.5M pairs including every boundary pair
- Q7 against a
longreference andMath.multiplyExact— all of[−2×10^6, 2×10^6]plus 3M random ints
A second harness recomputes every numeric claim in the prose and all five diagrams, and differentially tests every alternate implementation shown in the files. Three results from it are worth naming because they corrected or sharpened what I would otherwise have written:
>>and>>>are identical in a fixed 32-iteration loop. I was about to present the shift choice as the trap in Reverse Bits. It isn't — the trap is the loop condition, and it belongs to Number of 1 Bits.- Q7's fine-grained boundary clauses never fire for any 32-bit input. Verified across 6 million values; they're kept for correctness of expression, not necessity.
reverse(0)is 0 under both the correct and the broken version, so a test suite containing only{0}passes the bug.n = 1is the input that separates them.