What is the maximum total number of instructions?

user_16403864 0
Viewed 284

I was given three types of instruction, Type A, B, C which has 4, 7, 8-bit opcode respectively. What is the maximum total number of instructions if all three types of instructions exist? The answer for this question is 240 total instructions.

However, I only managed to get a max instructions of 233 by giving Type A the opcode of 0000 and giving the first four bits of Type B 0001, while the remaining combinations of 4 bits to Type C. The total would be 1 (Type A) + 2^3 (Type B) + (2^4 - 2)(2^4) (Type C) = 233 instructions.

Just to clarify, 2^3 is derived from the remaining 3 bits of Type B. And 2^4 is the remaining 4 bits of Type C.

combinatorics computer-science
1 Answers

You may see it this way. I will assume we will be working with 8 bits. If there were only type C instructions, the maximum number of instructions would be 256 (2^8).

Now suppose you also have just one type B instruction. It needs 7 bits to be encoded and the remaining bit is used as some sort of parameter field. So we have one more instruction but we have to subtract 2 type C instructions (the two that have the same 7 bits as the sole B instruction). So now we have 255 instructions (254 type C and 1 type B)

We repeat the process now adding just one type A instruction. It needs 4 bits to be encoded and the remaining 4 bits are used as some sort of parameter field. To add this instruction we had to "sacrifice" 16 type C instructions (all the combinations with the remaining 4 bits). So now we have 240 instructions (238 type C, 1 type B and 1 type A).

user_4632430
Related