Use a length-7 Hamming code, numbering positions from 1 on the left. Put the four original bits in positions in order.
Let be the XOR of the position numbers among those four positions whose bits are 1. Write and place at positions , respectively. The XOR of all positions containing 1 is then .
Suppose position is flipped. XORing the positions containing 1 in the received string adds or removes exactly one occurrence of , so the result is exactly . Flip that bit again and read positions . Because exactly one bit is flipped, the received syndrome for this strategy is always between 1 and 7.
The transmitted length is always 7, within the limit. The same procedure handles errors in parity positions 1,2,4 and data positions 3,5,6,7.
A naive decoder may encode all 16 original strings and find the codeword at distance exactly one from the received string. Distinct codewords have distance at least 3: a distance of one contradicts their equal zero syndromes, while a distance of two would require two distinct position numbers to XOR to zero. Thus the candidate is unique. Since the input size is fixed, this naive solution also passes the full task.
The main solution takes time and auxiliary space. The naive decoder makes at most bit comparisons, also . Position XOR values are at most 7, original numeric values at most 15, and an 8-bit mask at most 255. All arithmetic fits signed 64-bit integers.
Solution written by GPT6