c++ - 用于非常特殊情况的快速点积

Question

给定一个大小为 L 的 vector X，其中 X 的每个标量元素都来自二进制集合 {0,1}，如果大小为 L 的 vector Y 由的整数值元素。我建议，必须有一种非常快速的方法来做到这一点。

假设我们有 L=4; X[L]={1, 0, 0, 1}; Y[L]={-4, 2, 1, 0} 我们必须找到 z=X[0]*Y[0] + X[1]*Y[1] + X [2]*Y[2] + X[3]*Y[3](在这种情况下将给我们 -4)。

很明显，X 可以用二进制数字表示，例如L=32 的整数类型 int32。然后，我们要做的就是找到这个整数与 32 个整数数组的点积。您对如何快速完成有任何想法或建议？

Answer 1

这确实需要分析，但您可能需要考虑另一种方法:

int result=0;
int mask=1;
for ( int i = 0; i < L; i++ ){
    if ( X & mask ){
        result+=Y[i];
    }
    mask <<= 1;
}

通常位移和按位运算比乘法快，但是，if 语句可能比乘法慢，尽管使用分支预测和大 L 我猜它可能会更快。但是，您确实必须对其进行分析，以确定它是否会导致任何加速。

正如在下面的评论中所指出的，手动或通过编译器标志(例如 GCC 上的“-funroll-loops”)展开循环也可以加快速度(省略循环条件)。

编辑
在下面的评论中，提出了以下好的调整:

int result=0;
for ( int i = 0; i < L; i++ ){
    if ( X & 1 ){
        result+=Y[i];
    }
    X >>= 1;
}