c++ - 快速获取 "down-scale"三维张量索引的方法

Question

对于 C 或 C++，这是一个有点棘手的问题。我在 Ubuntu 12.04.2 下运行 GCC 4.6.3。

我有一个内存访问索引 p对于具有以下形式的三维张量:

p = (i<<(2*N)) + (j<<N) + k

在这里0 <= i,j,k < (1<<N)和 N一些正整数。

现在我想为 i>>S, j>>S, k>>S 计算一个“按比例缩小”的内存访问索引与 0 < S < N ，这将是:

q = ((i>>S)<<(2*(N-S))) + ((j>>S)<<(N-S)) + (k>>S)

计算q 最快的方法是什么？来自 p (事先不知道 i,j,k)？我们可以假设 0 < N <= 10 (即 p 是一个 32 位整数)。我会对 N=8 的快速方法特别感兴趣(即 i,j,k 是 8 位整数)。 N和 S都是编译时常量。

N=8 的示例和 S=4 :

unsigned int p = 240407; // this is (3<<16) + (171<<8) + 23;
unsigned int q = 161; // this is (0<<8) + (10<<4) + 1

Answer 1

直接的方式，8个操作(其他是对常量的操作):

M = (1<<(N-S)) - 1;                     // A mask with S lowest bits.
q = (  ((p & (M<<(2*N+S))) >> (3*S))    // Mask 'i', shift to new position.
     + ((p & (M<<(  N+S))) >> (2*S))    // Likewise for 'j'.
     + ((p & (M<<     S))  >>    S));   // Likewise for 'k'.

看起来很复杂，但实际上并非如此，只是不容易(至少对我而言)让所有常量都正确。

为了创建具有较少操作的公式，我们观察到将数字移动 U左边的位等于乘以 1<<U .因此，由于乘法分配性，乘以 ((1<<U1) + (1<<U2) + ...)与向左移动 U1 相同, U2 , ... 并将所有内容相加。

因此，我们可以尝试屏蔽 i 的需要部分, j和 k ，通过一次乘法将它们全部“移动”到彼此相对的正确位置，然后将结果向右移动到最终目的地。这给了我们三个操作来计算 q来自 p .

不幸的是，存在局限性，特别是对于我们试图同时获取所有三个的情况。当我们将数字加在一起时(间接地，通过将​​多个乘数加在一起)，我们必须确保只能在一个数字中设置位，否则我们会得到错误的结果。如果我们尝试一次(间接地)添加三个正确移位的数字，我们会得到:

iiiii...........jjjjj...........kkkkk.......
 N-S      S      N-S      S      N-S
.....jjjjj...........kkkkk................
 N-S  N-S      S      N-S
..........kkkkk...............
 N-S  N-S  N-S

请注意，第二个和第三个数字的左侧是 i 的位。和 j ，但我们忽略它们。为此，我们假设乘法像在 x86 上一样工作:将两种类型相乘 T给出了一些类型 T , 只有实际结果的最低位(如果没有溢出则等于结果)。

因此，要确保 k第三个数字的位不与 j 重叠从头开始，我们需要 3*(N-S) <= N ，即 S >= 2*N/3 N = 8将我们限制为 S >= 6 (移位后每个分量只有一位或两位；不知道您是否曾经使用过这么低的精度)。

但是，如果S >= 2*N/3 ，我们可以只使用 3 个操作:

// Constant multiplier to perform three shifts at once.
F = (1<<(32-3*N)) + (1<<(32-3*N+S)) + (1<<(32-3*N+2*S));
// Mask, shift/combine with multipler, right shift to destination.
q = (((p & ((M<<(2*N+S)) + (M<<(N+S)) + (M<<S))) * F)
     >> (32-3*(N-S)));

如果 S 的约束太严格了(可能确实如此)，我们可以结合第一个和第二个公式:计算 i和 k使用第二种方法，然后添加 j从第一个公式。这里我们需要位不在以下数字中重叠:

iiiii...............kkkkk.......
 N-S   S   N-S   S   N-S
..........kkkkk...............
 N-S  N-S  N-S

即3*(N-S) <= 2*N , 这给出了 S >= N / 3 ，或者，对于 N = 8不那么严格S >= 3 .公式如下:

// Constant multiplier to perform two shifts at once.
F = (1<<(32-3*N)) + (1<<(32-3*N+2*S));
// Mask, shift/combine with multipler, right shift to destination
// and then add 'j' from the straightforward formula.
q = ((((p & ((M<<(2*N+S)) + (M<<S))) * F) >> (32-3*(N-S)))
     + ((p & (M<<(N+S))) >> (2*S)));

此公式也适用于您的示例，其中 S = 4 .

这是否比直接方法更快取决于架构。另外，我不知道 C++ 是否保证假定的乘法溢出行为。最后，您需要确保值是无符号的并且恰好是 32 位，这样公式才能工作。