Exercises — Bit manipulation — XOR tricks, LSB, counting set bits

Each $1$ contributes its place value. Reading right to left the switches are at places $2^0,2^1,2^3$: $1011_2=2^3+2^1+2^0=8+2+1=11.$ The LSB is the rightmost bit, here a $1$, worth $2^0=1$. Answer: $x=11$, LSB $=1$.

Line them up ($12=1100_2$, $10=1010_2$):

  1100   (12)
  1010   (10)

• AND keeps a $1$ only where both are $1$: column $2^3$ ($1\&1=1$), column $2^2$ ($1\&0=0$), $2^1$ ($0\&1=0$), $2^0$ ($0\&0=0$) → $1000_2=8$.
• OR keeps a $1$ where either is $1$ → $1110_2=14$.
• XOR keeps a $1$ only where they differ: $2^3$ same $\to 0$, $2^2$ differ $\to 1$, $2^1$ differ $\to 1$, $2^0$ same $\to 0$ → $0110_2=6$. Answers: (a) $8$, (b) $14$, (c) $6$.

Left shift by $k$ multiplies by $2^k$; right shift divides (floor): $5\ll 3=5\cdot 2^3=5\cdot 8=40,200\gg 2=\lfloor \frac{200}{4}\rfloor =50.$ Answers: $40$ and $50$.

XOR the whole list; pairs cancel (self-inverse law $a\oplus a=0$): $7\oplus 3\oplus 5\oplus 3\oplus 7=(7\oplus 7)\oplus (3\oplus 3)\oplus 5=0\oplus 0\oplus 5=5.$ Running left to right if you prefer: $7\oplus 3=4$, $4\oplus 5=1$, $1\oplus 3=2$, $2\oplus 7=5$. Answer: 5.

$20=10100_2$. Its lowest set bit sits at place $2^2$. The identity from the parent note is $x\&-x=2^k$ where $k$ is the lowest set position, so the answer is $2^2=4$. Check via two's complement ($5$-bit picture, $-20$ = flip $10100$ → $01011$, add $1$ → $01100$):

  10100   ( 20)
  01100   (-20)
& -----
  00100   =  4

Answer: 4.

$30=11110_2$. Each step kills one $1$:

• $30\&29=11110\&11101=11100=28$ → count $1$
• $28\&27=11100\&11011=11000=24$ → count $2$
• $24\&23=11000\&10111=10000=16$ → count $3$
• $16\&15=10000\&01111=00000=0$ → count $4$, loop ends. Answer: 4 set bits (indeed $11110$ has four $1$s).

A power of two has exactly one switch on: $2^k=1\underset{k}{\underbrace{0\cdots 0}}$.

• ($\Rightarrow$) If $x=2^k$ then $x-1=\underbrace{0\cdots 0}0\underset{k}{\underbrace{1\cdots 1}}$, i.e. the single $1$ became $0$ and everything below became $1$. ANDing $x$ (only bit $k$ set) with $x-1$ (bit $k$ clear) gives $0$.
• ($\Leftarrow$) If $x$ has two or more set bits, let the lowest be at place $k$ and some higher bit at place $j>k$. Subtracting $1$ flips bit $k$ and the zeros below it, but leaves the high bit $j$ untouched. So $x\&(x-1)$ still has bit $j$ set → not $0$. Hence the AND is $0$ exactly for one-bit numbers, i.e. powers of two. (See Logarithms and Powers of Two.) Note: the condition $x>0$ matters — for $x=0$, $x\&(x-1)=0\&(-1)=0$ too, yet $0$ is not a power of two, which is why the full test is x != 0 && (x & (x-1)) == 0.

Write $x$ splitting off its lowest set bit at place $k=2$: $x=\underset{\text{high}}{\underbrace{11}}\underset{k=2\text{ trailing zeros}}{\underbrace{00}}.$ Two's complement $-x=(\neg x)+1$. Flipping $1100\to 0011$, then $+1\to 0100$. The "$+1$" ripples through the trailing $1$s of $\neg x$ and stops at place $k$, planting a $1$ there while re-clearing everything below and inverting every high bit. AND the two:

  1100   ( x)
  0100   (-x)
& ----
  0100   = 4 = 2^2

High bits cancel (a bit AND its inverse $=0$), the lowest bit aligns ($1\&1=1$), trailing stay $0$. The construction forces the match at the lowest set position — never the highest.

XOR only cancels in pairs (even counts → $0$). Here $6$ appears an odd number (three) times, so it does not vanish: $6\oplus 6\oplus 6\oplus 9=(6\oplus 6)\oplus 6\oplus 9=0\oplus 6\oplus 9=6\oplus 9=15.$ The result $15$ is neither the lone value nor $6$ — the trick is invalid when repeats aren't even. Fix for "all appear thrice except one": count each bit position modulo $3$ (see L4·Q2). Answer: no — plain XOR gives $15$, not $9$.

Let the two loners be $p$ and $q$. Step 1 — collapse to their XOR. XOR everything; the pairs die, leaving $s=p\oplus q.$ Here $1\oplus 2\oplus 1\oplus 3\oplus 2\oplus 5=3\oplus 5=6=110_2$. So $p\oplus q=6$. Step 2 — find a bit where they differ. Since $p\ne q$, $s$ has at least one $1$ bit. Isolate the lowest one with $s\&-s$: $s\&-s=6\&(-6)=110_2\&\dots 010_2=010_2=2.$ This $2^1$ bit is $1$ in exactly one of $p,q$ and $0$ in the other — a perfect splitter. Step 3 — split the array by that bit and XOR each group. Elements whose $2^1$ bit is set: [2, 3, 2] → $2\oplus 3\oplus 2=3$. Elements whose $2^1$ bit is clear: [1, 1, 5] → $5$. Within each group the paired numbers still cancel, so each group's XOR is one loner. Answer: $p=3$, $q=5$ (either order). Check: $3\oplus 5=6=s$ ✓.

XOR fails (L3·Q3), so count bits modulo 3. For each bit position $i$, add up how many of the numbers have that bit set; if the total is not a multiple of $3$, the lone number has that bit. $5=101_2$, $8=1000_2$.

• place $2^0$: set in the three $5$s → total $3$, $3\mathrm{mod}3=0$ → loner's bit $0$.
• place $2^2$: set in the three $5$s → total $3\mathrm{mod}3=0$ → loner's bit $0$.
• place $2^3$: set only in $8$ → total $1$, $1\mathrm{mod}3=1$ → loner's bit 1. Rebuild: only $2^3$ is on → $1000_2=8$. Answer: 8. (This generalises the parity idea from "mod 2" to "mod 3.")

XOR all indices/values of the full range $\mathrm{0..}n$ with all array elements; every present number cancels with its twin in the range, leaving the absent one: $\text{ans}=(0\oplus 1\oplus 2\oplus 3)\oplus (3\oplus 0\oplus 1).$ Range part: $0\oplus 1\oplus 2\oplus 3=0$. Array part: $3\oplus 0\oplus 1=2$. $\text{ans}=0\oplus 2=2.$ Answer: 2 (indeed $2$ is missing from $[3,0,1]$).

$-0$ in two's complement is still $0$ (flip all bits of $0$ → all $1$s $=-1$; add $1$ → $0$). So $0\&0=0$. There is no set bit to isolate, and the trick correctly returns $0$. Practical rule: always guard "lowest set bit" logic with a check for $x=0$, since $0$ is the one input with no lowest set bit. Answer: 0.

In 8-bit, $12=00001100$, so $-12=11110100$ (flip → $11110011$, add $1$ → $11110100$). Then $-(-12)=12=00001100$. AND:

  11110100   (-12)
  00001100   ( 12)
& --------
  00000100   = 4 = 2^2

The identity $x\&-x=2^k$ holds for negatives too: it still returns the lowest set bit's place value, here $2^2=4$. Answer: 4 — the sign doesn't matter, only the trailing-zero count does.

$-1$ in two's complement is all ones: $\underset{32}{\underbrace{11\cdots 1}}$. So it has 32 set bits. Brian Kernighan's loop x &= x-1; count++ clears one $1$ per iteration, so it runs exactly $32$ times before hitting $0$. (This is why popcount of $-1$ equals the word width — a classic sanity check for signed inputs.) Answer: 32.

$-8=11111000$. An arithmetic right shift copies the sign bit in from the left: $11111000\gg 1=11111100=-4$. Here $-8/2=-4$ too, so they agree. But the general warning stands: arithmetic shift rounds toward $-\infty$. E.g. $-7=11111001$, $\gg 1=11111100=-4$, whereas language division $-7/2=-3$ (rounds toward $0$). They differ. Answer: $-8\gg 1=-4$, which happens to equal $-8/2$; the mismatch shows up for odd negatives.

XOR keeps only what shows up an odd number of times (flip a switch twice and it's untouched). When two things are odd, first XOR everything to get their difference, then use x & -x to find one bit where they disagree and sort the room into two piles — each pile now has a single odd one out. For "appears three times," switch from counting parity (mod 2) to counting mod 3. And whenever a minus sign or a zero shows up, stop and picture the fixed-width switch row.