Show understanding of and perform binary shifts

4.3 Bit Manipulation – Binary Shifts

Learning Objective

Students will be able to:

• Explain the purpose of binary shift operations.
• Perform and predict the result of:

  • Logical left‑shift (<<)
  • Logical right‑shift (>>> in Java, >> on unsigned values in C)
  • Arithmetic right‑shift (>> on signed two’s‑complement values)

• Apply shifts in typical algorithmic, data‑representation and low‑level programming contexts.

Why Shifts Matter

• Multiplication / division by powers of two – a single CPU instruction.
• Core of many algorithms (cryptography, graphics, compression, fast exponentiation).
• Essential for extracting, inserting or packing bit‑fields in data structures.
• Direct mapping to assembly instructions: LSL (logical shift left), LSR (logical shift right), ASR (arithmetic shift right).

Basic Definition

A binary shift moves every bit of a binary representation a fixed number of positions left or right. Vacated positions are filled with a defined value (0 or the sign‑bit) and bits that move beyond the word size are discarded.

Types of Shifts

Mathematical Interpretation

For an n‑bit unsigned integer x and shift amount k (0 ≤ k < n):

\[

x \ll k = (x \times 2^{k}) \bmod 2^{n}

\qquad\qquad

x \ggg k = \big\lfloor \tfrac{x}{2^{k}} \big\rfloor

\]

For a signed two’s‑complement integer y:

\[

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

\]

Behaviour Illustrated

Overflow & Under‑flow

Left‑shifting discards the most‑significant bits that move beyond the word size.

unsigned 8‑bit: 1110 1101 << 2  →  0110 1100
Explanation: the two left‑most bits “11” are lost; the result is 108 decimal,
not 573 (which would be 1110 1101 00₂).

Masking & Field Extraction Using Shifts

Shifts are almost always paired with & (AND) or | (OR) to isolate or reposition sub‑fields.

• Extract a 5‑bit colour component (bits 16‑20 of a 24‑bit RGB value):

  mask   = 0b11111 << 16;          // 0x001F_0000
  red    = (rgb & mask) >> 16;     // now in bits 0‑4
  

• Insert a 3‑bit flag into bits 5‑7 of an unsigned integer n:

  flag   = 0b101;                  // value to insert
  n      = (n & ~ (0b111 << 5)) | (flag << 5);
  

Algorithmic Use of Shifts

Because a shift corresponds to multiplication or division by a power of two, they appear in many fast‑arithmetic algorithms.

// Compute 2^k using a left‑shift (k ≥ 0)
int powerOfTwo(int k) {
return 1 << k;          // 1 × 2^k
}
// Binary exponentiation (modular power)
int powMod(int base, int exp, int mod) {
int result = 1;
while (exp > 0) {
if (exp & 1) result = (result * base) % mod;
base = (base << 1) % mod;   // base = base × 2
exp  = exp >> 1;            // exp = exp ÷ 2
}
return result;
}

Cambridge Syllabus Links (AS 4.3 AO‑1 & AO‑2)

• Multiplying an unsigned integer by 2^k → x << k.
• Dividing an unsigned integer by 2^k → x >>> k.
• Dividing a signed integer by 2^k with rounding toward –∞ → y >> k.
• Masking and field extraction → x & ((1 << k) - 1).
• Understanding logical vs. arithmetic shift underpins the “CPU Architecture” (4.1) and “Assembly Language” (4.4) topics.

Common Pitfalls

1. Shifting by an amount ≥ the word size (n) is undefined in C and Java.
2. Confusing logical and arithmetic right shifts for signed values – the sign may change unexpectedly.
3. Ignoring overflow on left‑shifts; high‑order bits are discarded, possibly changing the sign of a signed value.
4. Assuming identical behaviour across languages: Java’s >>> is logical, while C’s >> on signed types is implementation‑defined.

Cross‑Topic Links

In assembly language the same operations appear as LSL (logical shift left), LSR (logical shift right) and ASR (arithmetic shift right). Mastery of binary shifts therefore supports the “CPU Architecture” (4.1) and “Assembly Language” (4.4) sections of the syllabus, and provides a foundation for later A‑level topics such as:

• Boolean algebra and Karnaugh maps (optimising combinational logic).
• RISC vs. CISC processor design (pipeline and parallelism).
• Data compression techniques that rely on bit‑level packing.
• Cryptographic primitives that use circular shifts (e.g., ROT‑13, SHA‑1).

Practice Questions

1. Given the 16‑bit unsigned value 0x0F3A, compute 0x0F3A << 4 and give the result in hexadecimal.
2. For the signed 8‑bit two’s‑complement number 1001 0110₂, perform an arithmetic right shift by 1. State the resulting binary and decimal values.
3. Explain why 1100 0001₂ >>> 2 yields a different result from 1100 0001₂ >> 2 when the operand is interpreted as signed.
4. Write pseudocode that extracts bits 5‑7 (LSB = bit 0) from an unsigned integer n using shift and mask operations.
5. Show how a left‑shift can be used to multiply the unsigned 8‑bit value 0010 1101₂ (45) by 8, and indicate whether any overflow occurs.
6. (A‑level extension) A 32‑bit signed integer -12345678 is stored in two’s‑complement form. What is the result of an arithmetic right shift by 3? Show the intermediate binary representation.

Answer Key (Teacher Use)

1. 0x0F3A << 4 = 0xF3A0

   Binary: 1111 0011 1010 0000. The high‑order nibble “0” is discarded.

2. Arithmetic right shift: 1001 0110 → 1100 1011

   Decimal: -53 (since 1100 1011₂ = –53 in two’s‑complement).

3. Logical right shift inserts 0s: 1100 0001₂ >>> 2 = 0011 0000₂ (48).

   Arithmetic right shift replicates the sign bit (1): 1100 0001₂ >> 2 = 1111 0000₂ (‑16). The sign‑extension changes the value.

4. mask      = 0b111 << 5;          // 0b11100000
   extracted = (n & mask) >> 5;    // bits 5‑7 now in positions 0‑2
   

5. Left‑shift by 3 (multiply by 2³ = 8):

   0010 1101 << 3 → 0101 1010 (binary 0101 1010₂ = 90).

   No overflow occurs because the original MSBs are 0; the result fits in 8 bits.

6. Signed 32‑bit -12345678 = 1111 0010 1111 0010 1110 0010 0010 0010₂.

   Arithmetic right shift by 3 → 1111 1001 0111 1001 0111 0001 0001 0001₂ = -1543209.

Context Within the Cambridge Computer Science Syllabus (2026)

AS‑Level Topics (Sections 1‑12)

The following blocks are required for the full AS course. Only the binary‑shift block is expanded here; teachers should ensure the other blocks are taught alongside.

• 1. Information Representation – binary, hexadecimal, BCD, ASCII/Unicode.
• 2. Hardware – CPU, RAM/ROM, registers, ALU, fetch‑execute cycle, interrupts.
• 3. Processor Architecture – Von Neumann model, instruction sets, CPU registers.
• 4. System Software – OS functions, utilities, language translators, IDEs.
• 5. Programming Fundamentals – variables, data types, operators, control structures, procedures/functions.
• 6. Algorithm Design – abstraction, decomposition, pseudocode, flowcharts.
• 7. Data Structures – arrays, records, files, ADTs.
• 8. Databases – relational model, ER diagrams, normalisation, basic SQL (DDL/DML).
• 9. Multimedia – bitmap vs. vector graphics, sound sampling, colour models.
• 10. Compression – lossless (RLE, Huffman) and lossy (JPEG, MP3) techniques.
• 11. Communication – LAN/WAN, topologies, IP addressing, DNS, client‑server vs. peer‑to‑peer.
• 12. Security & Ethics – threats, authentication, encryption basics, copyright, professional bodies.

A‑Level Extensions (Sections 13‑20)

These topics build on the AS foundation and are examined at A‑level.

• 13. Advanced Data Representation – floating‑point format, sign‑magnitude, excess‑bias.
• 14. Advanced Processor Architecture – RISC vs. CISC, pipelining, parallelism, virtual machines.
• 15. Boolean Algebra & Logic Design – Karnaugh maps, minimisation, flip‑flops, counters.
• 16. Operating Systems – process management, scheduling, virtual memory, paging, segmentation.
• 17. Communication Protocols – TCP/IP stack, HTTP/FTP, circuit‑ vs. packet‑switching.
• 18. Advanced Security – symmetric/asymmetric encryption, SSL/TLS, digital signatures, quantum cryptography.
• 19. Software Development – waterfall, iterative, RAD, testing, maintenance.
• 20. Artificial Intelligence – search algorithms, neural networks, data mining.

How Binary Shifts Connect to Other Syllabus Areas

• Information Representation: Shifts illustrate how multiplication/division by powers of two is performed at the bit level.
• Processor Architecture & Assembly: Direct equivalents of <<, >> and >>> are the CPU instructions LSL, LSR and ASR.
• Data Structures & File Organisation: Packing several fields into a single word (e.g., flags, colour components) relies on shifts and masks.
• Compression & Multimedia: Bit‑level packing and unpacking of pixel or audio samples uses shifts extensively.
• Security & Cryptography: Many block ciphers employ circular shifts (rotates) as a primitive; understanding basic shifts is a prerequisite.
• Boolean Algebra: Shifts are a practical way to implement logical functions such as “select the nth bit”.

Further Reading & Resources

• Cambridge International AS & A Level Computer Science (Coursebook, 2025 edition) – sections 4.3, 4.4.
• “Computer Organization and Design” by Patterson & Hennessy – chapters on shift instructions and data‑path design.
• Online visualiser: Bitwise Operations Visualiser.
• Practice worksheets from the Cambridge Teacher Support Hub – “Bit Manipulation” pack.