패턴에 대한 체크섬을 얻는 방법

StackOverflow https://stackoverflow.com/questions/598458

문제

64 비트 번호가 있지만 (42 개의 저 순수 비트 만 사용) 4 비트 n, n+m, n+m*2 그리고 n+m*3 (참고 : 합계> 4를 생성 할 수있는 것은 모두 고정 된 M에 대해 유효하지 않습니다).

예를 사용하여 사용합니다 m=3 16 비트 번호가 주어졌습니다

0010 1011 0110 0001

계산해야합니다

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

이 작업을 수행하는 방법에 대한 (멋진) 아이디어가 있습니까? 나는 약간의 twiddling으로 괜찮습니다.

현재의 생각은 입력의 비트 이동 사본을 만들기 위해 합산 할 값을 정렬 한 다음 4x 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 가지 다른 INT에 걸쳐 확산되었지만 오, 잘합니다.

편집 : 발생하기 때문에 합의 히스토그램이 필요하므로 비트 카운트 의 o4, o2&o1, o2 그리고 o1 내가 원하는 것을 제공합니다.

두 번째 솔루션은 완벽한 해시 기능을 사용합니다

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 개만 발생하므로 이런 식으로 작업하면됩니다.

추신

올바른 트럼프가 빨리 트럼프됩니다. 빠른 트럼프는 분명합니다. 나는이 수백만 시간을 달리기를 기대한다.

도움이 되었습니까?

해결책

어쩌면 나는 미쳤을 지 모르지만 재미있다 : D이 솔루션은 데이터 병렬 처리의 사용을 기반으로하고 실제로 SSE INTRINSICS 또는 유사한 것을 사용하지 않고 벡터 CPU를 위조하는 데 기반을두고있다.

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 ++에서 5 천만 실행에 대한 실행 시간 (모든 OUPUT가 일치하도록 확인) 내 PC에서 64 비트 바이너리로 컴파일되었습니다.
배열 기반 솔루션 : ~ 5700ms
순진한 하드 코드 솔루션 : ~ 4200ms
첫 번째 해결책 : ~ 2400ms
두 번째 해결책 : ~ 1600ms

다른 팁

내가 지금 코딩하고 싶지 않다는 제안은 루프, 부분 결과를 보유하기위한 배열, 상수를 사용하여 한 번에 비트를 선택하는 것입니다.

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));

등 (교대는 컴파일 시간에 발생합니다.)

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top