二进制矩阵向量乘法

我想将8×8 二进制矩阵乘以由无符号字符表示的8位向量表示为无符号64位整数。 但是，由于一些其他问题，矩阵必须按列排序，因此不容易匹配字节以便于乘法。

知道如何加快这样的计算吗？ 每项操作都很重要，我需要进行数十亿次这样的计算。

乘法是在2元素场（F-2）上进行的。

Answer 1

使用此矩阵和向量表示，有助于以这种方式进行矩阵乘法：

（col ₁ … col ₈ ）*（v ₁ … v ₈ ） ^T = col ₁ * v ₁ + … + col ₈ * v ₈

矩阵A =（col ₁ … col ₈ ）

和列向量v =（v ₁ … v ₈ ） ^T

进一步考虑这一点，如果通过重复每一位8次然后计算P = A & v_inflated将8位向量扩展为64位向量，则可以立即进行所有乘法运算。 唯一剩下的就是产品的添加（即异或）。

对产品进行异或的简单方法是。

 uint64_t P = calculated products from text above; uint64_t sum = 0; for( int i = 8; i; --i ) { sum ^= P & 0xFF; P >> 8; } 

Answer 2

你只有256个载体！ 使用查找表生成正确的位掩码，然后您的逻辑就像

 output_bit_n = bool (matrix [n] & lookup [vector]) 

换句话说，您的查找表可以将8位值转换为64位世界。

如果编译器不够智能(value<<=1)|=result可以使用rotate-with-carry指令将其有效地打包到(value<<=1)|=result 。