Alternatives to multiplication/division/modulo for encoding choices? The obvious way to encode, with minimum entropy, choosing s out of n (equiprobable) choices when x is already encoded is to identify s with a number [0, n) and set x = n * x + s, decoded with s = x % n, x = x / n.

Is this optimal if the only constraint is that the encoded result must be a bitstring? Would *+/% still be the choice if they were not available as instructions?

I know arithmetic coding (and ANS) exists, but it also can't avoid big integer arithmetic without giving up some entropy.
You can implement ANS using only additions, masks and shifts. Take a look at Finite State Entropy (FSE), it's a performance-focused version of ANS with accurate compression.