3

我有一个 64 位数（但只使用了 42 个低位），并且需要计算 4 位的总和, 和（注意n：n+m任何可以产生总和 >4 的东西都是无效的）对于一些固定的 m 和将所有位放入数字中的 n 的每个值n+m*2n+m*3

作为一个例子，使用m=3并给出 16 位数字

0010 1011 0110 0001

我需要计算

2, 3, 1, 2, 3, 0, 3

有没有人有任何（很酷）的想法来做到这一点？我没问题。

我目前的想法是制作输入的位移副本以对齐要求和的值，然后构建一个逻辑树来执行 4x 1bit 加法器。

v1 = In;
v2 = In<<3;
v3 = In<<6;
v4 = In<<9;

a1 = v1 ^ v2;
a2 = v1 & v2;
b1 = v3 ^ v4;
b2 = v3 & v4;
c2 = a1 & b1;
d2 = a2 ^ b2;

o1 = a1 ^ b1;
o2 = c2 ^ d2;
o4 = a2 & b2;

这最终会导致结果的位分布在 3 个不同的整数中，但是很好。

编辑：碰巧我需要总和的直方图，所以对 , 进行位计数，并o4给我想要的。o2&o1o2o1

第二种解决方案使用完美的散列函数

arr = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4];

for(int i = 0; i < N; i++)
{
   out[i] = arr[(In & 0b1001001001) % 30]; 
   In >>= 1;
}

这通过注意到 4 个选定位只能采用 16 种模式并且（通过猜测和检查）可以使用 mod 30 将它们散列为 0-15。从那里，一个计算值表给出了所需的总和。碰巧只有 4 步中的 3 步我需要以这种方式工作。

ps

正确胜过快速。快胜于清。我预计会运行数百万次。

4

2 回答 2

2

也许我疯了，但我很开心 :D 这个解决方案是基于数据并行性的使用和伪造矢量 cpu 而没有实际使用 SSE 内在函数或任何类似的东西。

unsigned short out[64];
const unsigned long long mask      = 0x0249024902490249ul;
const unsigned long long shiftmask = 0x0001000100010001ul;

unsigned long long t = (unsigned short)(in >> 38) | (unsigned long long)(unsigned short)(in >> 39) > 40) > 41) << 48;
t &= mask;
*((unsigned long long*)(out + 38)) = (t & shiftmask) + (t >> 3 & shiftmask) + (t >> 6 & shiftmask) + (t >> 9 & shiftmask);

[... snipsnap ...]

t = (unsigned short)(in >> 2) | (unsigned long long)(unsigned short)(in >> 3) > 4) > 5) << 48;
t &= mask;
*((unsigned long long*)(out + 2)) = (t & shiftmask) + (t >> 3 & shiftmask) + (t >> 6 & shiftmask) + (t >> 9 & shiftmask);

t = (unsigned short)in | (unsigned long long)(unsigned short)(in >> 1) << 16;
t &= mask;
*((unsigned int*)out) = (unsigned int)((t & shiftmask) + (t >> 3 & shiftmask) + (t >> 6 & shiftmask) + (t >> 9 & shiftmask));

通过重新排序计算，我们可以进一步显着减少执行时间，因为它大大减少了将某些内容加载到 QWORD 中的次数。其他一些优化非常明显且相当次要，但总结起来是另一个有趣的加速。

unsigned short out[64];
const unsigned long long Xmask = 0x249024902490249ull;
const unsigned long long Ymask = 0x7000700070007u;

unsigned long long x = (in >> 14 & 0xFFFFu) | (in >> 20 & 0xFFFFu) > 26 & 0xFFFFu) > 32) << 48;
unsigned long long y;
y = x & Xmask;
y += y >> 6;
y += y >> 3;
y &= Ymask;
out[32] = (unsigned short)(y >> 48);
out[26] = (unsigned short)(y >> 32);
out[20] = (unsigned short)(y >> 16);
out[14] = (unsigned short)(y      );

x >>= 1;
y = x & Xmask;
y += y >> 6;
y += y >> 3;
y &= Ymask;
out[33] = (unsigned short)(y >> 48);
out[27] = (unsigned short)(y >> 32);
out[21] = (unsigned short)(y >> 16);
out[15] = (unsigned short)(y      );

[snisnap]

x >>= 1;
y = x & Xmask;
y += y >> 6;
y += y >> 3;
y &= Ymask;
out[37] = (unsigned short)(y >> 48);
out[31] = (unsigned short)(y >> 32);
out[25] = (unsigned short)(y >> 16);
out[19] = (unsigned short)(y      );

x >>= 1;
x &= 0xFFFF000000000000ul;
x |= (in & 0xFFFFu) | (in >> 5 & 0xFFFFu) > 10 & 0xFFFFu) << 32;
y = x & Xmask;
y += y >> 6;
y += y >> 3;
y &= Ymask;
out[38] = (unsigned short)(y >> 48);
out[10] = (unsigned short)(y >> 32);
out[ 5] = (unsigned short)(y >> 16);
out[ 0] = (unsigned short)(y      );

[snipsnap]

x >>= 1;
y = x & Xmask;
y += y >> 6;
y += y >> 3;
y &= Ymask;
out[ 9] = (unsigned short)(y >> 16);
out[ 4] = (unsigned short)(y      );

在我的电脑上编译为 64 位二进制的原生 c++ 中 5000 万次执行的运行时间（所有输出验证匹配 ^^）：
基于数组的解决方案：~5700 ms
天真的硬编码解决方案：~4200 ms 第
一个解决方案：~2400 ms
第二种解决方案：~1600 ms

于 2009-02-28T19:38:36.570 回答
1

我现在不想编码的一个建议是使用循环、一个数组来保存部分结果和常量来一次获取位 m。

loop 
   s[3*i] += x & (1 << 0);
   s[3*i+1] += x & (1 << 1);
   s[3*i+2] += x & (1 << 2);
   x >> 3;

这将在每个总和中选择太多位。但是您也可以跟踪中间结果并在进行时从总和中减去，以说明可能不再存在的位。

loop 
   s[3*i] += p[3*i]   = x & (1 << 0);
   s[3*i+1] += p[3*i+1] = x & (1 << 1);
   s[3*i+2] += p[3*i+2] = x & (1 << 2);

   s[3*i] -= p[3*i-10];
   s[3*i+1] -= p[3*i-9];
   s[3*i+2] -= p[3*i-8];
   x >> 3;

当然，通过适当的边界检查。

最快的方法是对总和本身进行硬编码。

s[0] = (x & (1<<0)) + (x & (1<<3)) + (x & (1<<6)) + (x & (1<<9));

等等（这些变化发生在编译时。）

于 2009-02-28T20:03:30.893 回答