Bits required to address registers

问题:

Say I have 12 registers. How many bits must be reserved in the machine code instruction order to address any of these 12 registers?

回答1:

It takes ceil(log2(12)) bits to encode 1 of 12 possibilities in a normal fixed-width field.

But does having fewer than a power of 2 registers let us save any bits in an instruction with multiple register operands? Yes, in this case.

A 3-register instruction has 12^3 = 1728 possible permutations of registers. But using 3 separate 4-bit fields would give us 2^(4*3) = 4096 possible encodings. So there's 1 redundant bit, because 2^11 = 2048 which is still greater than 1728. However, encoding all 3 register selectors into one 11-bit field would require much more complex decoding.

A 2-register instruction needs 12^2 = 144 unique register encodings. But here, 2^(4*2) = 256, and the next lowest power of 2 (128) isn't big enough.

Probably your best bet is to use 4-bit fields, and use the 13..15 register encodings for something else. e.g. an escape code that means it's actually a different instruction. Or if you don't need that much instruction coding space, simplify the decoders and leave your instruction format redundant.

Or really your best bet is to have a power-of-2 number of registers, so you don't waste coding space. There's a reason that basically every modern register machine has a power-of-2 number of registers.

回答2:

Registers don't store "4 digit base 16 numbers", that's how you can interpret content of such register (seems you mean 16 bit register which when interpreted as hexadecimal integer can store values 0000..FFFF).

But the registers themselves are implemented in HW from bits (0 or 1 value). 16 bit register has 16 bits. Nothing about digits, hexadecimal, etc... those are all features of particular interpretation and interpretation is done either by code using the value in register, or tools used to view content of register.

Anyway, "addressing" register is not relevant in any way to the register content capabilities! The question is to address 12 registers, so for simplicity you can start by giving them names/addresses like 0,1,2,..,11 - how many bits must be reserved to encode that?

How much information can store 1 bit? 0 or 1 = 2 options.

Two bits can store these bit patterns 00, 01, 10, 11 = 4 options.

Three bits can store 000, 001, 010, 100, 011, 101, 110, 111 = 8 options. (notice, that would you interpret those bits as integer value encoded in binary, I did wrote 0, 1, 2, 4, 3, 5, 6, 7 ... in that (dis)order ... but when designing CPU you will hardly bother to interpret the register selection bits as integer, it's more like "pattern matching", if register "example1" has pattern 101 inside CPU, then that's how the assembler has to convert source into machine code)

etc...

It's very common to show content of register as hexadecimal values, because then 1 digit is formed by 4 bits, so the programmer debugging the code can easily "see" single bits, if he needs it, but the "hexadecimal number" is only interpretation of the bit pattern stored in register, it's not part of the information encoded. Encoded are only the bit values.