빠른 방법은 비트 벡터의 계산 패리티를 알아야합니다

저는 비트 벡터를 사용하여 C에서 작업하고 있습니다. 내 비트 벡터는 unsigned long long입니다. 많은 수의 벡터에 대해, 패리티가 1인지, 즉 비트 수가 1인지 또는 홀수인지를 알아야합니다.빠른 방법은 비트 벡터의 계산 패리티를 알아야합니다

정확한 값은 중요하지 않으며 단지 패리티입니다. 나는 사람의 수를 계산하고 점검하는 것보다 더 빠른 것이 있는지 궁금해하고있었습니다. 나는 무언가를 생각하려고했지만 아무 것도 찾을 수 없었다.

나는이 작동하는 방법의 간단한 예 :

void checkIntersection(unsigned long long int setA, unsigned long long int setB){ 
    if(isEven(setA & setB)){ 
     //do something 
    } 
}

출처

2014-02-27 nvcleemp

"비트 트위 들링 해킹"을 검색하십시오 .... –

uint64_t a = value; 
a ^= (a >> 32);   // Fold the 32 MSB over the 32 LSB 
a ^= (a >> 16);   // reducing the problem by 50% 
a ^= (a >> 8);    // <-- this can be a good break even point 
.. 
return lookup_table[a & 0xff]; // 16 or 256 entries are typically good 
..

접는 과정이 끝날 때까지 적용 할 수

a ^= (a >> 1); 
return a & 1;

는 IA에서 패리티 플래그 직접 8 비트로 감소 후에 검색 될 수있다.

a ^= (a >> 4);은 일부 프로세서 아키텍처가 XXM (또는 NEON) 레지스터에 포함 된 병렬 Look Up 테이블 uint8_t LUT[16]을 제공 할 수 있기 때문에 분할을 중지하는 또 다른 좋은 점을 만듭니다. 또는 단순히 256- 입력 LUT의 잠재적 캐시 누락은 한 번의 추가 라운드 계산 작업을 단순히 과중할 수 있습니다. 주어진 아키텍처에서 어느 LUT 크기가 최적인지를 측정하는 것이 자연히 가장 좋습니다.

이 마지막 표는 실제로는 16 비트로 구성되고 시퀀스 에뮬레이트 될 수

마법 전율

return ((TRUTH_TABLE_FOR_PARITY) >> (a & 15)) & 1;

비트 N 상기 패리티 (N) 대한 부울 값을 부호화한다.

출처

2014-02-27 08:26:39

매우 쉽다. 예 :

unsigned population(unsigned long long x) { 
    x = ((x >> 1) & 0x5555555555555555) + (x & 0x5555555555555555); 
    x = ((x >> 2) & 0x3333333333333333) + (x & 0x3333333333333333); 
    x = ((x >> 4) & 0x0f0f0f0f0f0f0f0f) + (x & 0x0f0f0f0f0f0f0f0f); 
    x = (x >> 8) + x; // Don't need to mask, because 64 < 0xff 
    x = (x >> 16) + x; 
    x = (x >> 32) + x; 
    return x & 0xff; 
}

과 같은 것이 좋습니다. 또한 일부 CPU에는 인구수 지침이 있습니다 (x86은 생각하지 않습니다). 당신이 이런 종류의 일을 좋아하는 경우에, 당신은 헨리 S. 워렌 책 해커의 기쁨을 확인해야

, 주니어

출처

2014-02-27 08:20:17 alastair

OP는 특별히 비트 수를 계산하는 것보다 더 빠른 것을 원합니다. –

공정한 포인트. 나는 그 질문을 약간 잘못 읽었다 고 생각한다. – alastair

당신은 배열에서의 비트의 모든 가능한 조합에 대한 패리티를 미리 계산할 수 바이트 :

bool pre[256] = { 0, 1, 1, 0, 1, ....}

더 큰 배열의 패리티를 찾을 필요가 당신은 수행

bool parity (long long unsigned x) 
{ 
    bool parity = 0; 
    while(x) 
    { 
     parity ^= pre[x&0xff]; 
     x>>=8; 
    } 
    return parity; 
}

면책 조항 : 코드를 테스트하지는 않았지만 단지 아이디어 일뿐입니다. 분할 컨커 기법

출처

2014-02-27 08:25:41 titus

빠른 방법은 비트 벡터의 계산 패리티를 알아야합니다

답변

관련 문제