一个具有不同参数的函数，用于将输入整数的某些位推送到

Question

这个问题与this有关。你知道吗

设x为8位整数。我将从左到右对位进行编号，因为我们就是这样读的。如果我想得到第三位和第五位，把它们放在第一位和第二位，其他的都是零，我可以有f(x) = (5*x) & 0b11000000。更简洁地说：

00a0b000 -> ab000000 | f_0b00101000(x) = (5*x) & 0b11000000

但是，如果我希望第五位、第六位和第八位位于前三位，f(x)是不同的：

000ab0cd -> abcd0000 | f_0b00011011(x) = ((x << 3) & 0b11000000) | (x << 4)

注意，f_n(x)中的n表示我关心哪些位。n可以有任何8位的值。有没有一些x的公共函数（和一些参数）可以将所有需要的位推到左边？而且，这应该是快速的，所以我宁愿只使用位运算。你知道吗

---

假设我处理的是3位整数。你知道吗

000 -> 000 | f_0(x) = (1*x) & 0
00a -> a00 | f_1(x) = (4*x) & 4
0a0 -> a00 | f_2(x) = (2*x) & 4
0ab -> ab0 | f_3(x) = (2*x) & 6
a00 -> a00 | f_4(x) = (1*x) & 4
a0b -> ab0 | f_5(x) = (3*x) & 6
ab0 -> ab0 | f_6(x) = (1*x) & 6
abc -> abc | f_7(x) = (1*x) & 7

这些函数都可以组合到f(x, m, a) = (m*x) & a中，我可以创建一个查找表，我可以通过索引从n中获取m和a的值：

t = [(1, 0), (4, 4), (2, 4), (2, 6), (1, 4), (3, 6), (1, 6), (1, 7)]

所以f_n(x)变成f(x, *t[n])。我认为f(x, m, a) = (m*x) & a是3位的最佳选择。3位的原始版本是：

f(x, a, b, c, d, e, f) = ((x & a) << b) |
                         ((x & c) << d) |
                         ((x & e) << f)

朴素函数的运算数为8，最优（？）的运算数为2一个。现在8位的朴素函数是：

f(x, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p) = ((x & a) << b) |
                                                       ((x & c) << d) |
                                                       ((x & e) << f) |
                                                       ((x & g) << h) |
                                                       ((x & i) << j) |
                                                       ((x & k) << l) |
                                                       ((x & m) << n) |
                                                       ((x & o) << p)

此指令中有25个操作。有没有可能降到7或8左右，甚至更低？你知道吗

Answer 1

def f(t, x):  # template, number to convert
    t = bin(t).replace("0b", "").rjust(8, "0")
    x = bin(x).replace("0b", "").rjust(8, "0")
    return int("".join([x[i] for i, b in enumerate(t) if int(b)]).ljust(8, "0"), 2)

Answer 2

您可以在查找表中存储函数：

table = [
    lambda x:x,
    lambda x:x,
    lambda x:x | ((x & 0b0001) << 1),
    ...
    ]

我想问一下，为什么要在Python中通过位移位整数来实现这一点。如果是为了性能，我认为通过一系列的位移位操作来实现这一点是个坏主意。解释器的开销将完全淹没位移位可以实现的任何速度优势。如果是为了内存使用，因为需要在内存中容纳数百万个这样的数组，那么最好看看numpy，它可以创建内存高效的数组，并在整个数组中同时应用操作。你知道吗

我能想到的一个很好的理由是，在用C这样的低级语言实现算法之前，你需要先对算法进行实验，我怀疑，只有在使用非常有限的硬件或进行非常密集的计算时，性能优势才会明显——也许你在模拟成千上万的《宝石迷航》游戏。如果你这样做只是为了计算一个人实时玩的游戏的一个实例的逻辑，我怀疑位转移优化是否有意义。你知道吗

如果你想用移位的方法来做这件事，你能这样做吗？与其一步一个脚印地完成，不如循环直到没有更多的位元可以“掉落”。您最多只需要循环整数中位的次数。你知道吗

假设你有这样的模式：

        PATTERN : ab c d
          HOLES : 00110110

找到最高的设定位：最左边的孔。（您可以执行类似的操作：https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2）

  LEFTMOST HOLE : 00100000

现在把那个洞去掉。左边的一切都不会改变。右边的东西都会左移一个。为这些区域创建遮罩。你知道吗

       CAN FALL : 00011111  ( == LEFTMOST HOLE - 1)
   WON'T CHANGE : 11000000  ( == invert CAN FALL and shift left )

使用这些掩码来切碎、移动和重新组合所有其他位字段。你知道吗

      KEEP THIS : ab
     SHIFT THIS :    -c d
         RESULT : ab-c d-

最后，重复此过程，直到“CAN FALL”遮罩仅选择孔。它不会以严格的最小操作数执行您的操作，但是它应该相对容易理解，并且不需要大型查找表的复杂性。你知道吗