我如何计算这个按位公式的倒数？

Question

我正在努力练习我的算法并研究一些我还不太精通的按位的东西。

所以我有这个功能：

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

但是我需要为我正在处理的算法反转操作。因此，例如，如果函数 fn1(11) returns 14，我需要创建一个函数 fn2(14) 即 returns 11。它只需要对正整数起作用。

我以为逆可能有不止一个答案，但是运行 fn1 循环了数千次都没有产生任何重复值，所以一定只有一个答案fn2.

的任意值

Answer 1

位序列 11 和 00 转到 *0。位序列 10、01 转到 *1。因此图像 *1 表示 a 中的相同位和下一个更高位被翻转。
a 中的前导 1 位前面是 0，因此仍然是 1。

对于 fn₁(a) = b,

的二进制表示

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

是

b_i = a_i+1 ^ a_i ⇔

a_i = a_i+1 ^ b_i ⇔

a_i-1 = a_i^b_i-1

通过这个递归和 a_m = b_m = 1 你得到了数字a_m-1, _m-2, ..., a₀ .

编辑

一个不同的观察（尚未正式证明）是 fn₁ 对某些参数 a 的迭代应用将导致回到原始参数 a.

For a in argument range 2^2ⁿ...2^2ⁿ⁺¹-1周期为p=2ⁿ⁺¹，已解决 p=2^{floor( ld( ld (a) )+1}

有了这个fn₁^-1(a) = fn₁^p-1(a) .

至于b=fn₁(a)，a和b属于同一个循环，p-公式同样适用于b.

最后fn₁^-1(b) = fn₁^p-1(b) 与 p=2^{floor( ld( ld (b) ) +1}

这是 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);
}

编辑 2

fn₁ 的进一步属性是，可以收缩迭代。

让更一般的fn_k(a) := a ^(a>>k), 然后 (fn_k ∘ fn_k)(a) = fn_2k(a )，通过简单的重新计算。

用二进制表示 e=p-1 = ∑ α_i 2 ⁱ 普通迭代变为

fn₁^e(a) = ( ‖_{α_i≠0} fn₁^{{2 ⁱ}} ) (一) = ( ∠_{α_i≠0} fn_{{2 ⁱ}}) (一)

渐近复杂度为 O(n log n) 与第一次尝试 digit-wise 求逆相反。

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;
}

我如何计算这个按位公式的倒数？

How could I calculate the inverse of this bitwise formula?

python

algorithm

bit-manipulation

编辑

编辑 2