Bit reductions in program instructions are achieved by determining the set of bit patterns in bit locations of the instructions. If only a subset of bit patterns is present in the instructions, they may be represented by an index value having a smaller number of bits. The index value may be substituted into the instruction and later used in decoding by referencing a corresponding bit pattern in a lookup table. The bit-reduction in the instruction makes way for supplemental data bits which may then be embedded.