如何獲得校驗爲跨入模式

Question

我有一個64位的數字（但僅使用42個低位），需要計算機的位的總和在n，n+m，n+m*2和n+m*3（注：任何可以產生一個和值> 4是無效的），用於一些固定的米和放置在數

如使用m=3一個例子的所有位和給出的16位數字

0010 1011 0110 0001 

n個的每一個值

我需要計算

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

有沒有人有任何（酷）想法的方式來做到這一點？我很好，有點混蛋。

---

我現在的想法是：把位移位輸入的副本對準總和的值，然後建立一個邏輯樹做4倍1位加法器。

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個不同的整數，但很好。

編輯：因爲它發生了，我需要資金的直方圖這樣做的，o2&o1，o2和o1bit-count給我我想要的。

---

的第二解決方案使用一個完美的哈希函數

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個我需要這樣工作。

---

p.s.

正確的勝負很快。快速勝過清楚。我希望能夠運行數百萬次。

Answer 1

也許我很瘋狂，但我很開心：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  ); 

運行時間在本地C++ 5000萬處決（所有。OUPUTS驗證匹配^^）編譯爲我的電腦上一個64位二進制：
基於 陣列的解決方案：〜5700毫秒
天真硬編碼的解決方案： 〜4200毫秒
第一個解決方案：〜2400毫秒
第二溶液：〜1600毫秒

Answer 2

，我不希望立即代碼的建議是使用一個循環，一個數組來保存部分結果，以及一次拾取位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)); 

等。（轉變發生在編譯時。）