arrays - 确定是否可以在没有分支的情况下生成整数序列的技术？

Question

如果您正在优化分支昂贵的架构(比如 PS3 的单元处理器)，那么能够确定是否可以在不使用分支或至少使用较少分支的情况下表达给定算法可能很重要。我在未优化的代码中经常看到的一种模式是一堆 if 用于将索引调整到某个数组中(如果数组的大小是奇数，则将索引增加 1，在其他情况下，乘以 2，等等。 )。因此，如果有一种方法，给定两个数字列表，能够确定是否可以编写一个将一个列表转换为另一个列表的无分支函数，那就太好了。

例如，我最近想知道是否可以编写一个可以转换的无分支函数:0, 1, 2, 3, 4, 5, 6, 7, 8, 9至:0, 2, 4, 6, 8, 9, 7, 5, 3, 1 (偶数升序，奇数降序)。从技术上讲，我可以编写一个大的 switch/case 函数，但显然我对一个将遵循任意大小模式的函数感兴趣。编写一个函数来完成这个转换对于分支来说很简单，但是如果有一种非分支的方式来做到这一点，它并不是很明显。

那么是否有解决此类问题的通用方法，或任何类型的快速试金石？还是必须逐案提出证据？我可以在这类问题上更加努力地工作，但如果它们实际上是不可能的，那也毫无意义。我似乎记得在某个时候读到过，对于只使用算术而不使用分支的函数，有一个正式的数学词，但我不记得了。

Answer 1

将:0, 1, 2, 3, 4, 5, 6, 7, 8, 9 转换为: 0, 2, 4, 6, 8, 9, 7, 5, 3, 1(升偶后降奇) .

简单:给定 X 的 N 个值从 0 到 N-1 的序列，我们看到序列的前半部分是 2X。序列的后半部分是 (2N-1)-2X。序列在 X=(N+1)/2 处用“整数”数学拆分。在上面的例子中，N == 10。

因此，假设具有算术右移的 32 位有符号整数:

int Transform(int x)
{
    const int seq1=x+x;
    const int mask=(x-((N+1)>>1))>>31;
    const int seq2=(N+N-1)-seq1;
    return (mask&seq1)|((~mask)&seq2);
}

请注意，这里使用的掩码模式很快，因为 PowerPC 有一个 ANDC(并带有补码)，使得 (~mask)免费操作。