使用一次乘法提取位数
使用一次乘法提取位数
我在一个答案中看到了一个有趣的技巧,用于另一个问题,我想更好地理解它。\n我们有一个无符号的 64 位整数,我们对以下位感兴趣:\n
1.......2.......3.......4.......5.......6.......7.......8.......
\n具体来说,我们希望将它们移动到前八个位置,如下所示:\n
12345678........................................................
\n我们不关心由.
表示的位的值,它们也不需要被保留。\n解决方案是屏蔽掉不需要的位,并将结果乘以0x2040810204081
。这个方法可以实现我们的目的。\n这个方法有多通用?这个技术可以用来提取任何位的子集吗?如果不能,如何确定该方法是否适用于特定的位集?\n最后,如何找到(一个)正确的乘数来提取给定的位?
问题的出现原因:为了将特定的位提取到正确的位置,需要通过乘法来实现。每个乘数中的1位用于将相应的位复制到其正确的位置上。
解决方法:通过乘以特定的乘数来实现位的提取。根据位的位置,选择相应的乘数进行乘法操作。例如,对于位2,需要将其左移7位,因此乘以0x0000000000000080。对于位3,需要将其左移14位,因此乘以0x0000000000000400。依此类推,直到位8,需要将其左移49位,因此乘以0x0002000000000000。乘数是各个位的乘数的总和。
需要注意的是,原始数字中的其他位必须为0。这可以通过与操作来掩码处理。
这种方法之所以有效,是因为要收集的位之间的距离不能太近,这样在我们的方案中不属于同一组的位的乘法结果要么超出了64位,要么位于较低的不关心部分。
值得注意的是,这个解决方法的解释非常好,使得我们能够快速找到“魔术数”的值。
这确实是最好的答案,但如果没有先阅读(前半部分)的答案,就不会那么有帮助。
“用单个乘法提取位”这个问题的出现的原因是:如果可以将问题表述为关于位向量理论的一阶逻辑,那么定理证明器可以为你提供非常快速的答案。解决方法是使用定理证明器SMT-LIB 2来验证该问题是否为定理。下面的代码是将问题转化为SMT-LIB 2输入的示例代码。代码中的变量'mask'和'multiplicand'是常数,通过验证可以确定它们的值。最后,通过调用定理证明器Z3来验证该问题是否为定理,并获取解的模型。
文章还提到,从更一般的角度来看,这个问题可以视为一阶程序合成问题的一个实例。一阶程序合成是一个新兴的研究领域,关于它的论文很少。通过搜索“program synthesis filetype:pdf”可以找到相关的研究论文。
最后,文章中还提到Stack Overflow(SO)作为一个游戏,对很多人来说也是一种娱乐。同时,SO上的回答也是鼓励和支持他人的努力的方式。
文章中给出了解决问题的示例代码和相关讨论,以及提到了一些相关的领域和研究方向。
从上面的内容可以整理出以下问题的出现的原因:
- 问题是如何通过一次乘法来提取位数。
- 原因是要将不感兴趣的位数置为零,并将所需的位数放置在正确的位置上。
- 答案是通过一个位掩码和乘法来实现。位掩码是一个简单的AND操作,将不感兴趣的位数置为零。乘法是一系列的移位和加法操作,通过允许溢出来移动我们不需要的位数,并将我们想要的位数放置在正确的位置上。
- 可以通过多次掩码和乘法来提取任意位数的位。但是,需要满足一定的条件,即位之间需要有足够的空间,或者需要进行额外的掩码和乘法步骤。
以下是问题的解决方法:
- 首先,使用位掩码将不感兴趣的位数置为零。
- 然后,通过乘法来移动位数,将所需的位数放置在正确的位置上。
这个方法可以扩展到更大的数字和更多的位数。
但是,对于所有位数的数字来说,这种方法不一定适用。需要满足一定的条件,即位之间需要有足够的空间,或者需要进行额外的掩码和乘法步骤。
除了以上的规则,如果要提取的两个位是相邻的,并且希望保持它们的顺序不变,那么仍然可以使用这种方法。
另一个洞察力是,对于每个感兴趣的位,它只需要左边有足够的零位来存放需要放置在左边的结果位数,右边需要有足够的位数来存放右边的结果位数。因此,如果一个位在位置m,需要m-1个左边的零位和n-m个右边的零位。这对于位在原始数字中的顺序与重新排序后的顺序不同的情况下尤为重要。
但是,即使满足上述规则,仍然有可能出现进位问题。如果在目标区域的右侧刚好有进位位(当我们正在寻找的位都是1时),则会发生进位。因此,需要根据实际情况对规则进行修改,以避免进位问题。
以上是解决提取位数的问题的原因和方法。