Given a stream of bits, output the shortest possible Hamming code that encodes it.
The steps to generate the Hamming code are as follows, although your submission does not necessarily have to conform to them as long as it produces identical output. The input
110100101 will be used as an example.
Pad the input with trailing zeroes until its length is 2m - m - 1 for some integer m.
110100101 becomes 11010010100
Insert spaces at every position with an index of 2i (note that all indexing is 1-based for the purposes of this algorithm). This will insert m spaces for parity bits, resulting in 2m - 1 bits total.
11010010100 becomes __1_101_0010100
Fill in the parity bits. A parity bit at index i is calculated by taking the sum modulo 2 of all bits whose index j satisfies i & j ≠ 0 (where & is bitwise AND). Note that this never includes other parity bits.
__1_101_0010100 becomes 111110100010100
Input may be taken as a list (or a string) of any two distinct elements, which do not necessarily have to be
1. Output must be in an identical format. (Input or output as an integer with the corresponding binary representation is disallowed, as this format cannot express leading
The input will always have a length of at least 1.
Test cases (of the form
0 000 1 111 01 1001100 1011 0110011 10101 001101011000000 110100101 111110100010100 00101111011 110001001111011 10100001001010001101 0011010100010010010001101000000