I'm working on practicing my algorithms and getting into some bitwise stuff which I'm not too proficient with yet.

So I have this function:

def fn1(a):
    return (a >> 1) ^ a

But I need to reverse the operation for the algorithm I'm working on. So, for example, if function fn1(11) returns 14, I need to create a function fn2(14) that returns 11. It only needs to work for positive integers.

I thought that maybe the inverse could have more than one answer, but running fn1 thousands of times in a loop did not yield any duplicate values, so there must be only one answer for any value of fn2.

CodePudding user response：

1. Bit sequences 11 and 00 go to *0. Bit sequences 10, 01 go to *1. So an image *1 indicates that same bit and next higher bit in a are flipped.

2. The leading 1-Bit in a is preceded by a 0, so remains 1.

For binary representations of fn₁(a) = b,

fn₁(a_m a_m-1 .... a₀) = b_m b_m-1 .... b₀

it is

b_i = a_{i 1} ^ a_i ⇔

a_i = a_{i 1} ^ b_i ⇔

a_i-1 = a_i ^ b_i-1

with this recursion and a_m = b_m = 1 you get the digits a_m-1, _m-2, ... , a₀ .

EDIT

A different observation (not yet formally proven) is that iterated application of fn₁ to some argument a will lead back to the original argument a.

For a in argument range 2²ⁿ...2^{2n 1}-1 the periode is p=2^{n 1} , resolved p=2^{floor( ld( ld (a) ) 1}

With this fn₁^-1(a) = fn₁^p-1(a) .

As for b=fn₁(a), both a and b belong to the same cycle, the p-Formula equally applies to b.

Finally fn₁^-1(b) = fn₁^p-1(b) with p=2^{floor( ld( ld (b) ) 1}

Here is an implementation in C

typedef unsigned long long N;

N fn1(N a)
{
    return a ^ (a >> 1);
}

N floor_ld(N x);

N fn1_inv(N b)
{
    if (b<=2) return b;
    N p = (N)1 << (floor_ld(floor_ld(b))   1);
    N y = b;
    for (int i = 1; i <= p - 1; i  )
    {
        y = fn1(y);
    }
    return y;
}

N floor_ld(N x)
{
    return x == 1 ? 0 : 1   floor_ld(x >> 1);
}