IAE Academy

GATE 2026 CS2 Q.44: solution and answer

GATE 2026 · CS2Q.44 · 2 marks · MCQ

Consider a processor that has 16 general purpose registers and it uses 2-byte instruction format for all its instructions. Variable-sized opcodes are permitted. There are three different types of instructions; M-type, R-type, and C-type. Each M-type instruction has 2 register operands and a 6-bit immediate operand. Each R-type instruction has 3 register operands. Each C-type instruction has a register operand and a 6-bit offset value. If there are 2 unique M-type opcodes and 7 unique R-type opcodes, which one of the following options gives the maximum number of unique opcodes possible for C-type instructions?

  1. (A)

    8

  2. (B)

    4

  3. (C)

    64

  4. (D)

    16

See the question in the paper
GATE 2026 CS2 question 44Tap to open full size

Answer and solution

ANSWER

The maximum number of unique C-type opcodes is 4 — option (B).

Official answer: BSource: Official answer key, GATE 2026 CS2 (IIT Guwahati)

  1. Registers: 16 GPRs ⇒ each register operand needs bits.

  2. Instruction length is fixed at 2 bytes = 16 bits for every type.

  3. M-type: operand bits ⇒ opcode length bits.

  4. R-type: operand bits ⇒ opcode length bits.

  5. C-type: operand bits ⇒ opcode length bits.

  6. Because the decoder must identify the instruction type from the opcode bits alone (before knowing how many operand bits follow), the opcodes of all three types together must form a prefix-free set — no opcode may be a prefix of another.

  7. Model this with a binary tree of depth 6 (the longest opcode length), giving leaves in total.

  8. Each 2-bit M-type opcode, extended to depth 6, blocks leaves; 2 such opcodes block leaves.

  9. Each 4-bit R-type opcode blocks leaves; 7 such opcodes block leaves.

  10. Leaves consumed by M-type and R-type together: .

  11. Leaves remaining at depth 6: .

  12. Each C-type opcode is already 6 bits (full depth), so it occupies exactly 1 leaf ⇒ maximum unique C-type opcodes , matching option (B).

KEY IDEA

Variable-length opcodes that must be uniquely decodable from a fixed 16-bit instruction behave exactly like a prefix-free (Huffman) code: the set of opcodes, extended to a common comparison depth, must occupy disjoint blocks of a binary code tree (Kraft's inequality). Count how many leaves of that tree the already-fixed M-type and R-type opcodes use up, and the remainder bounds the C-type opcode count.

WATCH OUT FOR

Treating each instruction type's leftover opcode bits independently (e.g., concluding C-type has possible opcodes) without imposing the prefix-free condition that lets a single opcode-decoder distinguish M-, R-, and C-type instructions from the same 16-bit word; this ignores that shorter opcodes (M-type, R-type) consume large blocks of the shared code space that longer C-type opcodes cannot then use.

From the GATE 2026 CS2 paper. Every question of this paper · Download the full paper · All 11 Instructions & addressing questions, with notes

More Instructions & addressing questions