3

我发现的所有位洗牌算法都处理 16 位或 32 位，这意味着即使我只使用 int 的前 25 位，洗牌也会将位留在外面。此函数位于 CPU 密集型进程的内部循环中，因此我希望它尽可能快。我试过修改 Hacker's Delight 32-bit shuffle 算法的代码

x = (x & 0x0000FF00) << 8 | (x >> 8) & 0x0000FF00 | x & 0xFF0000FF;
x = (x & 0x00F000F0) << 4 | (x >> 4) & 0x00F000F0 | x & 0xF00FF00F;
x = (x & 0x0C0C0C0C) << 2 | (x >> 2) & 0x0C0C0C0C | x & 0xC3C3C3C3;
x = (x & 0x22222222) << 1 | (x >> 1) & 0x22222222 | x & 0x99999999;

但我做一些困难，部分原因是我不确定面具是从哪里来的。我尝试改变数字并重新洗牌，但到目前为止结果都是徒劳的。任何帮助将不胜感激！

（我正在使用 C 但我可以从另一种语言转换算法）

4

1 回答 1

0

首先，为了均匀起见，我们可以通过记住第 25 位将出现在交错列表的末尾，将问题扩展到 26 位 shuffle，因此我们可以在交错操作之后将其修剪掉而不影响其他位。

现在我们要交错第一组和第二组 13 位；但是我们只有一个算法来交织第一组和第二组 16 位。

一种直接的方法可能是在应用标准算法之前将高低部分移动x到更可行的位置：

x = (x & 0x1ffe000) << 3 | x & 0x00001fff;

x = (x & 0x0000FF00) << 8 | (x >> 8) & 0x0000FF00 | x & 0xFF0000FF;
x = (x & 0x00F000F0) << 4 | (x >> 4) & 0x00F000F0 | x & 0xF00FF00F;
x = (x & 0x0C0C0C0C) << 2 | (x >> 2) & 0x0C0C0C0C | x & 0xC3C3C3C3;
x = (x & 0x22222222) << 1 | (x >> 1) & 0x22222222 | x & 0x99999999;

每半部分顶部的零将被交错并出现在结果的顶部。

于 2013-08-20T22:32:57.637 回答