MARIE bit question?

Question

Knowing that MARIE has 9 operations/instructions, how many bits are needed to represent all of them?

Answer 1

A sequence of n bits has 2^n different patterns.  If you need to represent K different things with n bits, that means you need:

    K <= 2^n

    log K <= n * log 2

    (log K)/(log 2) <= n

When K == 9, that's n >= (log 9)/(log 2) = 3.169925+.

The smallest integer n that works is n==4.

For small problems like this, it's helpful to memorize the small powers of 2, at least up to 2^10 = 1,024.  Knowing that 2^3 == 8 and 2^4 == 16 would instantly get you to the answer that at least 4 bits are needed.