3

我正在寻找在 64 位整数中置换位的最快方法。

给定一个名为“array”的表，对应于一个排列数组，这意味着它的大小为 64，并填充了从 0 到 63 的唯一数字（即不重复），对应于 64 位整数中的位位置，我可以置换位这边走

bit = GetBitAtPos(integer_, array[i]);
SetBitAtPos(integer_, array[i], GetBitAtPos(integer_, i));
SetBitAtPos(integer_, i, bit);

(by looping i from 0 to 63)

GetBitAtPos being
GetBitAtPos(integer_, pos) { return (integer >>) pos & 1 }

Setbitatpos 也基于相同的原理（即使用 C 运算符），形式为 SetBitAtPos(integer, position, bool_bit_value)

如果可能的话，我正在寻找一种更快的方法来执行此任务。我愿意接受任何解决方案，包括必要时的内联汇编。我很难找到比这更好的方法，所以我想我会问。

我想执行这样的任务以隐藏 64 位生成的整数中的数据（其中第 4 位可以显示信息）。这比说一个 XOR 掩码 imo 好一点（除非我错过了什么），主要是如果有人试图找到相关性。它还允许进行逆运算以不丢失宝贵的位...

但是我觉得这个手术有点贵...

谢谢

4

3 回答 3

1

由于排列是恒定的，因此您应该能够想出一种比逐个移动位更好的方法（如果您可以发布您的秘密排列，我可以尝试一下）。最简单的改进是在输入和输出中同时移动它们之间具有相同距离（可以是模块化距离，因为您可以使用旋转）的位。如果这样的组很少，这是一个非常好的方法。

如果效果不如您希望的那样好，请查看是否可以使用bit_permute_step来移动所有或大部分位。有关更多想法，请参阅该站点的其余部分。

如果您可以使用 PDEP 和 PEXT，您可以在位之间的距离可以任意改变（但它们的顺序不能）的组中移动位。这是，afaik，虽然不知道它们会多快（而且它们还不可用）。

最好的方法可能是结合其他答案中提到的这些技巧和其他技巧。

有太多的可能性去探索它们，真的，所以你可能不会找到进行排列的最佳方法，但是使用这些想法（以及发布的其他想法）你无疑可以找到比你更好的东西'目前正在使用。

PDEP 和 PEXT 已经有一段时间了，所以它们的性能是已知的，在 3 个周期的延迟和 1 个周期的吞吐量下，它们比大多数其他有用的置换原语（除了琐碎的置换原语）要快。

于 2013-02-20T10:34:50.207 回答
0

将您的位拆分为此方法适用的子集：

用单次乘法提取位

然后使用按位或组合结果。

于 2013-02-20T06:39:46.223 回答
0

对于 64 位数字，我相信（寻找最佳算法）的问题可能由于大量的可能性而无法解决。最具可扩展性和最容易自动化的方法之一是查找表： 

result = LUT0[ value & 0xff] +  
         LUT1[(value >> 8) & 0xff] +  
         LUT2[(value >> 16) & 0xff] + ...  
     +   LUT7[(value >> 56) & 0xff];
  • 每个 LUT 条目必须是 64 位宽，并且它只是将子组中的每个 8 位扩展到 64 个可能的 bin 的全部范围。此配置使用 16k 内存。

可伸缩性来自这样一个事实，即可以使用任意数量的查找表（实际范围从 3 到 32？）。此方法容易受到缓存未命中的影响，并且无法并行化（至少对于大表大小）。

如果存在某些对称性，则可以使用一些巧妙的技巧——例如在 Intel 中交换两个位：

 test eax, (1<<BIT0 | 1<<BIT1)
 jpe skip:
 xor  eax, (1<<BIT0 | 1<<BIT1)
 skip:

此 OTOH 极易受到分支错误预测的影响。

于 2013-02-20T07:11:35.910 回答