5

1

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

**2**for some integer m.^{m}- m - 1`110100101 becomes 11010010100`

Insert spaces at every position with an index of

**2**(note that all indexing is 1-based for the purposes of this algorithm). This will insert^{i}**m**spaces for parity bits, resulting in**2**bits total.^{m}- 1`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 `0`

and `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 `0`

s.)

The input will always have a length of at least 1.

Test cases (of the form `input output`

):

```
0 000
1 111
01 1001100
1011 0110011
10101 001101011000000
110100101 111110100010100
00101111011 110001001111011
10100001001010001101 0011010100010010010001101000000
```

What significance does the padding have? – Neil – 2017-05-28T20:22:15.103