gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-05 05:43:58 26 4
gpt4 key购买 nike

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

所以我有这个功能:

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

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

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

最佳答案

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

  2. a 中的前导 1 位前面是 0,因此仍然是 1。

对于 fn1(a) = b 的二进制表示,

fn1(am am-1 .... a0) = bm bm-1 .... b0

bi = ai+1 ^ ai

ai = ai+1 ^ bi

ai-1 = ai ^ bi-1

通过这个递归和 am = bm = 1 你得到数字 am-1 , m-2, ..., a0 .

编辑

一个不同的观察(尚未正式证明)是将 fn 1 迭代应用到某些参数 a 将导致返回原始参数 a

对于参数范围 22n...22n+1 中的 a -1 periode是p=2n+1 , resolved p=2floor( ld( ld (a) )+ 1

有了这个 fn1-1(a) = fn1p-1(a) .

对于b=fn1(a)ab属于同一个循环,p-公式同样适用于b

最后 fn1-1(b) = fn1p-1(b) p=2floor( 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

fn1 的另一个属性是迭代可以收缩。

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

使用 e=p-1 = ∑ αi 2 i 的二进制表示,普通迭代变为

fn1e(a) = ( ∞αi≠0 fn1{2 i} ) (a) =( ∞αi≠0 fn{2 i}) (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;
}

关于python - 我如何计算这个按位公式的倒数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/71698768/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com