Generate Hamming codes 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 &amp; j ≠ 0 (where &amp; 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 0s.)

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
JavaScript (ES6), 116 bytes

f=(a,p=i=0)=&gt;1/a[p]?f(a,p+p+1,a.splice(p,0,0)):[...Array(p)].map(_=&gt;i&amp;++i?~~a[i-1]:a.reduce((p,e,j)=&gt;p^=++j&amp;i&amp;&amp;e,0))


If the padding is unnecessary, then for 97 bytes:

f=(a,p=i=0)=&gt;1/a[p]?f(a,p+p+1,a.splice(p,0,0)):a.map(e=&gt;i&amp;++i?e:a.reduce((p,e,j)=&gt;p^=++j&amp;i&amp;&amp;e,0))