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.