Exercises — Binary number system and bit - byte concepts

Columns from right (position $0$) to left (position $5$): $2^0,2^1,2^2,2^3,2^4,2^5=1,2,4,8,16,32$ Why start at $2^0=1$? Position $i$ is worth $2^i$, and the rightmost position is $i=0$, and $2^0=1$.

Line the weights under the bits: $\underset{32}{1}\underset{16}{0}\underset{8}{1}\underset{4}{1}\underset{2}{0}\underset{1}{1}$ The leftmost bit is a $1$ sitting in the $32$ column, so it contributes $32$ — the largest single amount here. Why the leftmost, not just any $1$? The left column always has the highest weight ($2^5$); a $1$ there beats every column to its right combined ($16+8+4+2+1=31<32$).

True — every bit off is still a legal pattern. It equals $0\cdot 32+0\cdot 16+\cdots +0\cdot 1=0_{10}.$ Why it counts: the parent note stresses that $n$ bits give $2^n$ patterns and they start at $0$. The all-zero pattern is the number zero.

Weights under the bits: $\underset{32}{1}\underset{16}{1}\underset{8}{0}\underset{4}{1}\underset{2}{1}\underset{1}{0}$ Add only the columns with a $1$ (a $0$ contributes nothing): $32+16+4+2=54_{10}$

Read remainders bottom-up: $101101_2$. Verify with Tool A: $32+8+4+1=45$. ✓

A nibble is $4$ bits, so $2^4=16$ patterns. They run $0,1,\dots ,15$, so the largest unsigned value is $15$. Why $15$ not $16$? $16$ patterns, but the count includes $0$; the top of the range is $2^4-1$.

Compare from the most significant (leftmost) bit — that column outweighs everything to its right.

• $11000_2$: leftmost bit ($2^4=16$) is $1$.
• $10111_2$: leftmost bit ($2^4=16$) is also $1$ — tie, move right.
• Next column ($2^3=8$): $11000_2$ has $1$; $10111_2$ has $0$. So $11000_2$ wins here.

Since a single higher column ($8$) beats all lower columns combined ($4+2+1=7<8$), $11000_2>10111_2$. Check: $24>23$. ✓

Take $n=3$. Patterns: $000,001,\dots ,111$ — that is $2^3=8$ patterns, but the values are $0$ through $7$. The claimed max $2^3=8$ is never reachable ($8=1000_2$ needs a 4th bit). Correct maximum: $2^n-1=7$. Root cause: patterns start at $0$, so the count $2^n$ is one more than the top value.

Appending a $0$ on the right shifts every existing bit one column to the left, and each column is worth $2\times$ the one to its right. So every bit's contribution doubles, and the new rightmost column ($2^0$) holds a $0$ (adds nothing). $101_2=4+1=5,1010_2=8+2=10=2\times 5$ Algebra view: if $V=\sum d_i{2}^i$, shifting gives $\sum d_i{2}^{i+1}=2\sum d_i{2}^i=2V$. This is binary's version of "add a zero to multiply decimal by 10."

We need the smallest $n$ with $2^n-1\ge 500$, i.e. $2^n\ge 501$. $2^8=256<501,2^9=512\ge 501$ So $n=9$ bits. (With $8$ bits the max is $255<500$; with $9$ bits the range is $0$–$511$, which comfortably holds $500$.) Why $\ge 501$ and not $\ge 500$? Because the top representable value is $2^n-1$; we need $2^n-1\ge 500\Rightarrow 2^n\ge 501$.

Split the byte down the middle: $\underset{\text{high nibble}}{\underbrace{1101}}\underset{\text{low nibble}}{\underbrace{0110}}$

• High nibble $1101_2=8+4+1=13$.
• Low nibble $0110_2=4+2=6$.
• Whole byte $11010110_2=128+64+16+4+2=214$.

The relationship: the high nibble sits in the top four columns ($2^4$ upward), so it is worth $16\times$ its own value: $13\times 16+6=208+6=214.✓$ This is exactly why one nibble maps to one hex digit — see Hexadecimal number system.

• $1\text{ KiB}=2^{10}=1024$ bytes (binary prefix, used for RAM/Memory addressing).
• $1\text{ kB}=10^3=1000$ bytes (decimal SI prefix, used by disk makers).
• Difference: $1024-1000=24$ bytes.
• Extra fraction: $24/1000=0.024=2.4\%$ more.

Why they differ at all: $1024$ is a power of two (natural to binary addressing); $1000$ is a power of ten (natural to human counting). They just happen to be close.

(a) $2^{16}=2^6\cdot 2^{10}=64\cdot 1024$ bytes $=65536$ bytes $=64\text{ KiB}$. (b) To give each of $2^{16}$ bytes a unique address we need $n$ bits with $2^n\ge 2^{16}$, so $n=16$ bits. Exactly $16$ address lines address exactly $2^{16}$ bytes — a perfect fit, no waste. (See Memory addressing.)

• 2 bytes $=16$ bits $\Rightarrow$ range $0$ to $2^{16}-1=65535$.
• Since $60000\le 65535$, 2 bytes suffice — no overflow.
• (1 byte would only reach $255$, hopelessly small; 3 bytes would be wasteful here.) Why check against $65535$, not $65536$? Top value is $2^{16}-1$; $65536$ itself is unreachable in $16$ bits.

Locations addressable by $n$ bits $=2^n$. Go from $n$ to $2n$ bits: $2^{2n}=(2^n{)}^2=2^n\cdot 2^n.$ So the count is multiplied by $2^n$, not by $2$. Concretely, $8$ bits address $256$ locations; $16$ bits address $65536=256\times 256$ — a factor of $256$, i.e. $2^8$, not $2$. Why: each extra bit doubles the count, and you added $n$ extra bits, so you doubled $n$ times $=\times 2^n$.

Which byte is larger, $10110001_2$ or $10101111_2$? ::: $10110001_2$ — first difference is at $2^4$ (bit $1$ vs $0$); it equals $177$ vs $175$. Smallest bit-count for $1000_{10}$? ::: $2^{10}=1024\ge 1001$, so $10$ bits. $128\text{ KiB}$ in bytes? ::: $128\times 1024=131072$ bytes.