Show understanding of and perform binary shifts

4.3 Bit Manipulation – Binary Shifts

Learning Objective

Show understanding of binary shift operations and be able to perform left‑shift, logical right‑shift and arithmetic right‑shift on binary numbers.

Why Shifts Matter

• Efficient way to multiply or divide by powers of two.
• Common in low‑level algorithms (e.g., cryptography, graphics, compression).
• Used to extract or insert bit‑fields in packed data structures.

Basic Definitions

A binary shift moves each bit of a binary representation a fixed number of positions left or right. Vacated bit positions are filled with a defined value (0 or sign‑bit).

Types of Shifts

1. Logical left shift (<<) – bits move towards more significant positions; zeros fill the least‑significant bits (LSBs).
2. Logical right shift (>>>) – bits move towards less significant positions; zeros fill the most‑significant bits (MSBs). Used for unsigned values.
3. Arithmetic right shift (>>) – bits move right; the sign bit (most significant bit) is replicated to preserve the sign of a signed two’s‑complement number.

Mathematical Interpretation

For an \$n\$‑bit unsigned integer \$x\$ and shift amount \$k\$:

\$x \ll k = x \times 2^{k} \pmod{2^{n}}\$

\$x \ggg k = \left\lfloor \dfrac{x}{2^{k}} \right\rfloor\$

For a signed two’s‑complement integer \$y\$:

\$y \gg k = \text{sign‑extend}\!\left(\left\lfloor \dfrac{y}{2^{k}} \right\rfloor\right)\$

Step‑by‑Step Example: 8‑bit \cdot alues

Consider the 8‑bit binary number \$0101\;1010_2\$ (decimal 90).

Practical Use Cases

• Multiplying an unsigned integer by \$2^k\$ → use \$x \ll k\$.
• Dividing an unsigned integer by \$2^k\$ → use \$x \ggg k\$.
• Dividing a signed integer by \$2^k\$ (rounding toward \$-\infty\$) → use \$y \gg k\$.
• Masking: \$x \& ( (1 \ll k) - 1 )\$ extracts the lowest \$k\$ bits.

Common Pitfalls

1. Shifting by an amount \$\ge n\$ (the word size) is undefined in many languages.
2. Confusing logical and arithmetic right shifts for signed values – the sign may change unexpectedly.
3. Ignoring overflow: left shift can discard high‑order bits, changing the value.
4. Assuming the same behaviour across languages; e.g., Java’s >>> is logical, while C’s >> is implementation‑defined for signed types.

Practice Questions

1. Given the 16‑bit unsigned value \$0x0F3A\$, compute the result of \$0x0F3A \ll 4\$ and express it in hexadecimal.
2. For the signed 8‑bit two’s‑complement number \$1001\;0110_2\$, perform an arithmetic right shift by 1. What is the resulting binary and decimal value?
3. Explain why \$1100\;00012 \ggg 2\$ yields a different result from \$1100\;00012 \gg 2\$ when the value is interpreted as signed.
4. Write a short pseudocode fragment that extracts bits 5‑7 (counting from 0 as LSB) from an unsigned integer n using shift and mask operations.

Answer Key (for teacher use)

1. \$0x0F3A \ll 4 = 0xF3A0\$ (binary \$1111\;0011\;1010\;0000\$). The high‑order nibble \$0\$ is discarded.
2. Arithmetic right shift: \$1001\;0110 \rightarrow 1100\;1011\$. Decimal: \$-53\$ (since \$1100\;1011_2\$ = \$-53\$ in two’s‑complement).
3. Logical right shift inserts 0s, giving \$0011\;00002\$ (decimal 48). Arithmetic right shift replicates the sign bit (1), giving \$1111\;00002\$ (decimal \$-16\$). The sign extension changes the value.

4. mask = 0b111 << 5      // mask = 0b11100000
   extracted = (n & mask) >> 5
   

   This isolates bits 5‑7 and shifts them to the least‑significant positions.