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

Question

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

所以我有这个功能:

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

但我需要为我正在处理的算法反转操作。因此，例如，如果函数 fn1(11) 返回 14，我需要创建一个返回 11 的函数 fn2(14)。它只需要为正整数工作.

我认为也许逆运算可能有多个答案，但是在循环中运行 fn1 数千次并没有产生任何重复值，因此对于任何值都必须只有一个答案fn2。

Answer 1

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

2. 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。

对于参数范围 2²ⁿ...2^{2n+1 中的 a} -1 periode是p=2ⁿ⁺¹ , resolved 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}} ) (a) =( ∞_αi≠0 fn_{{2 ⁱ}}) (a)

<我>

渐近复杂度为 O(n log n)，这与第一次尝试对逆函数进行数字评估形成对比。

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