Exercises — Binary number system — conversions from - to decimal, counting in binary

Write the weights over the bits (rightmost bit is position $0$, weight $2^0=1$):

What we did: kept only the columns where the bit is $1$. Why: a $0$ contributes nothing; a $1$ contributes its weight. $4+0+1=5$ So $101_2=5_{10}$.

Positions count from the right starting at 0: the rightmost bit is position $0$, next is $1$, next is $2$. "Third from the right" is position $2$, whose weight is $2^2=4.$ (The bit there happens to be $0$, so it contributes nothing — but the weight of that slot is still $4$.)

$1000_2$ has its single $1$ in the highest column, weight $2^3=8$. $0111_2$ has $1$s only in the three lower columns, so its biggest possible sum is $4+2+1=7$. Since $8>7$, $1000_2$ is larger. Key recognition: a single high bit always beats any combination of the lower bits — because each weight is more than the sum of all smaller weights combined ($8>4+2+1$). This is the doubling ruler at work.

Weights over the bits $10110$:

Keep the $1$-columns (positions $4,2,1$): $16+4+2=22$ So $10110_2=22_{10}$.

Why divide by 2? The remainder of $N÷2$ is $1$ when $N$ is odd and $0$ when even — and $2^0=1$ is the only odd-weighted column, so that remainder is exactly the last bit. The quotient drops the units column and holds the higher bits.

Read remainders bottom → top: $100101$. Check: $32+4+1=37$ ✓ So $37_{10}=100101_2$.

$64=2^6$, so it should be a single $1$ followed by six $0$s.

Bottom → top: $1000000$. Check: one $1$ in the $2^6$ column $=64$ ✓ Every exact power of two is a lone $1$ with zeros trailing.

Forecast: $2^7=128$ and $2^8=256$. Since $128\le 200<256$, the highest weight that "fits" is $2^7$, so we need 8 bits (positions $0$ through $7$).

Verify by division:

Bottom → top: $11001000$ — that's 8 digits ✓ Check: $128+64+8=200$ ✓

Each of the $6$ bits is independently $0$ or $1$, so the number of combinations is $2\times 2\times 2\times 2\times 2\times 2=2^6=64\text{ values.}$ Because counting starts at 0, the values run from $0$ up to $2^6-1=63$. The largest pattern is $111111_2=32+16+8+4+2+1=63$ ✓ So: 64 distinct values, range $0$ to $63$.

Look at the counting figure:

Each column flips half as often as the column to its right, because its weight is double.

• The rightmost bit (weight $1$) flips every step: from $0$ to $15$ there are $15$ steps, so it flips $15$ times. Equivalently it changes at every increment.
• The leftmost bit (weight $8$) flips only when the lower three bits roll over (every $8$ steps): it goes $0\to 1$ at step $8$. Across $0\to 15$ it flips once.

Structural read: bit at position $i$ changes state every $2^i$ counts, so higher bits are "lazier." That laziness is exactly why the leftmost bit tells you the biggest chunk of the value.

Incrementing is the odometer move: flip the rightmost bit; if it was $1$ it becomes $0$ and carries a $1$ leftward (see Binary addition and overflow).

• Position 0: $1+1=10_2$ → write $0$, carry $1$.
• Position 1: $0+\text{carry }1=1$ → write $1$, no carry.
• Positions 2,3 unchanged: $1$ and $1$. Result: $1110_2$. Confirm: $1101_2=8+4+1=13$; $1110_2=8+4+2=14$. Indeed $13+1=14$ ✓

Step 1 — decimal to binary by division:

Bottom → top: $110101_2$. Check: $32+16+4+1=53$ ✓

Step 2 — group into 4s from the right. Pad the left with zeros to fill the top group: $00110101_2$ Why grouping-by-4 works: four bits carry weights $8,4,2,1$, spanning values $0$–$15$ — exactly one hex digit. Each block of four converts independently.

• $0011_2=2+1=3\to$ hex digit 3
• $0101_2=4+1=5\to$ hex digit 5 So $53_{10}=110101_2={35}_{16}$. Confirm: $3\times 16+5=48+5=53$ ✓

Value: weights on $10011100$ are $128,64,32,16,8,4,2,1$. Keep the $1$-columns (positions $7,4,3,2$): $128+16+8+4=156.$ Room above: a byte's largest value is $2^8-1=255$. Patterns strictly larger than $156$ number $255-156=99.$ So $10011100_2=156_{10}$, with 99 larger patterns before you hit the ceiling $11111111_2=255$.

Run the algorithm on $N=0$: we divide, get quotient $0$ and remainder $0$, and $N$ is already $0$, so we stop.

The single remainder is $0$, so $0_{10}=0_2$. Why not empty? The value zero is a real, writable number — the convention is a single digit $0$, just as decimal writes "0" rather than nothing. In a fixed field of $n$ bits it appears as $n$ zeros (e.g. $00000000$ in a byte). All zero columns means "no weight is switched on," which correctly sums to $0$.

Claim: $\underset{n}{\underbrace{11\dots 1}}{}_2=2^n-1$.

The string of $n$ ones sums all the weights from $2^0$ up to $2^{n-1}$: $S=2^0+2^1+2^2+\cdots +2^{n-1}.$ The doubling trick: add $1$ to $S$. The lone $2^0=1$ plus that extra $1$ makes $2^1$; that combines with the existing $2^1$ to make $2^2$; which combines to make $2^3$; the carry cascades all the way up until you reach a single $2^n$: $S+1=2^n⟹S=2^n-1.$ Picture it as an odometer of all-nines rolling over: $\underset{n}{\underbrace{11\dots 1}}+1$ overflows into $1\underset{n}{\underbrace{00\dots 0}}$, which is $2^n$.

Apply ($n=5$): the largest 5-bit value is $11111_2=2^5-1=31$. Check: $16+8+4+2+1=31$ ✓

Test on $1011_2=11_{10}$:

• Append $0$: $10110_2=16+4+2=22=2\times 11$ ✓
• Append $1$: $10111_2=16+4+2+1=23=2\times 11+1$ ✓

Why it must hold: appending a digit on the right shifts every existing bit one column left, and each column's weight is exactly double the column to its right. So every bit's contribution doubles → the whole value doubles. The new rightmost bit occupies the $2^0=1$ column, adding $0$ or $1$ on top. Hence "append 0 = double" and "append 1 = double plus one." (This is the binary version of "append a 0 in decimal = multiply by 10.")

Binary→decimal: sum the weights where the bit is 1. Decimal→binary: divide by 2 repeatedly, read remainders bottom-to-top.

$n$-bit value? $2^n-1$ (all ones), because all-ones plus one overflows to $2^n$.