algorithm - How do I map the position of a hamming-encoded bit to the position of the decoded bit using a closed function or map? -

this in reference simple sec hamming code of arbitrary length. have working decoder, requires 2 loops, , seems there should more efficient way of calculating position of changed bit in destination (decoded) bit-array.

here current algorithm:

decode(input_str)     each symbol in input string         if symbol == 1             xor position of symbol accumulator //binary addition         if position not power of 2             append symbol output array          //accumulator holds position of flipped bit in input string         //need map position in output_string 

after reducing input bit array shorter, decoded bit array, need correct error has resulted flipped bit. position or index of flipped bit stored in accumulator. however, position of bit in input array. need way map position in output array efficient , doesn't loop.

the issue more general this. i'm looking closed formula maps dst_bit src_bit in following tables show relationships between position of destination (encoded) bit corresponding source (decoded) position.

src_bit     dest_bit    powers      diff 1           3           2^0 + 1     2 2           5           2^1 + 1     3 3           6           2^1 + 1     3 4           7           2^1 + 1     3 5           9           2^2         4 6           10          2^2         4 7           11          2^2         4 8           12          2^2         4 9           13          2^2         4 10          14          2^2         4 11          15          2^2         4 12          17          2^2 + 1     5 13          18          2^2 + 1     5 14          19          2^2 + 1     5 ... 26          31          2^2 + 1     5 27          33          2^2 + 2     6 28          34          2^2 + 2     6 ... 57          63          2^2 + 2     6 58          65          2^3 - 1     7 59          66          2^3 - 1     7 ... 64          72          2^3 - 1     7 

i've found 1 relationship seems key, shown transforming first table this:

dest_bit    src_bit     n 3           -2          1  = 2^1 - 1 5 7      -3          3  = 2^2 - 1 9 15     -4          7  = 2^3 - 1 17 31    -5          15 = 2^4 - 1 33 63    -6          31 = 2^5 - 1 

i'm beating head against wall trying come closed function turn dest_bit src_bit.

---

partial solution

figuing out n such 2^n largest twos power less destination bit provides offset, still involes loop, seems inefficient.

def convert_bit_position(dest_bit):     offset = 1     while true:         if 2 ** offset > dest_bit:             break         else:             offset += 1     return offset * -1