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. JavaScript questions and answers, JavaScript questions pdf, JavaScript question bank, JavaScript questions and answers pdf, mcq on JavaScript pdf, JavaScript questions and solutions, JavaScript mcq Test , Interview JavaScript questions, JavaScript Questions for Interview, JavaScript MCQ (Multiple Choice Questions)

Answer 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. The leading 1-Bit in a is preceded by a 0, so remains 1. For binary representations of fn1(a) = b, fn1(am am-1 .... a0) = bm bm-1 .... b0 it is bi = ai+1 ^ ai ⇔ ai = ai+1 ^ bi ⇔ ai-1 = ai ^ bi-1 with this recursion and am = bm = 1 you get the digits am-1, m-2, ... , a0 . EDIT A different observation (not yet formally proven) is that iterated application of fn1 to some argument a will lead back to the original argument a. For a in argument range 22n...22n+1-1 the periode is p=2n+1 , resolved p=2floor( ld( ld (a) )+1 With this fn1-1(a) = fn1p-1(a) . As for b=fn1(a), both a and b belong to the same cycle, the p-Formula equally applies to b. Finally fn1-1(b) = fn1p-1(b) with p=2floor( 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 fn1 is, that iterations can be contracted. Let be more general fnk(a) := a ^(a>>k), then (fnk ∘ fnk)(a) = fn2k(a), by simple recalculation. With the binary representation of e=p-1 = ∑ αi 2 i the common iteration becomes fn1e(a) = ( ∏αi≠0 fn1{2 i} ) (a) = ( ∏αi≠0 fn{2 i}) (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; }