How could I calculate the inverse of this bitwise formula?

Question

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.

Answer 1

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²ⁿ⁺¹-1 the periode is p=2ⁿ⁺¹ , 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);
}

EDIT 2

A further property of fn₁ is, that iterations can be contracted.

Let be more general fn_k(a) := a ^(a>>k), then (fn_k ∘ fn_k)(a) = fn_2k(a), by simple recalculation.

With the binary representation of e=p-1 = ∑ α_i 2 ⁱ the common iteration becomes

fn₁^e(a) = ( ∏_αi≠0 fn₁^{{2 i}} ) (a) = ( ∏_αi≠0 fn_{{2 ⁱ}}) (a)

The asymptotic complexity is O(n log n) in contrast to first attempt with digit-wise evaluation of the inverse.

N fn1_invC(N b)
{
    if (b < 2) return b;
    N p = (N)1 << (floor_ld(floor_ld(b)) + 1);
    N e = p - 1;
    N y = b;
    N k = 1;
    while (e != 0)
    {
        if ((e & 1) != 0)
        {
            y = y ^ (y >> k);
        }
        k <<= 1;
        e >>= 1;
    }
    return y;
}