이 C++ 비트 버퍼 처리 코드를 향상시키는 데 도움이됩니다.

Question

들어오는 32 비트 버퍼를 처리하는 함수를 작성하여 변경된 데이터를 해당 저장된 32 비트 버퍼와 비교할 때이를 나타냅니다. 변경 비트의 위치는 변경이 0-> 1인지 1-> 0인지 여부와 함께 처리되어야하는 번호 (즉, 8의 값은 비트 3을 의미 함)를 나타냅니다. 여기에 현재의 구현입니다, 제발 그것을 개선하는 데 도움주세요! 이것은 실제 코드가 아니며 컨텍스트에 중립적으로 단순화되었습니다.

uint32_t temp = oldBuffer^newBuffer; 
uint32_t number = 0; 
while (temp != 0) 
{ 
    if (temp & 0x1) 
    { 
     uint32_t bitValue = 0; 
     if ((newBuffer& (1 << number)) != 0) bitValue = 1; 
     processNumber(number, bitValue); 
    } 
    number++; 
    temp = temp >> 1; 
} 
oldBuffer = newBuffer; 

지금은 제대로 작동하지만 비트 1을 확인하고 전체 내용을 확인하여 각 비트를 확인해야한다는 점이 마음에 들지 않습니다. 알아 내기 힘들지 않을 것 같은 1 비트 세트 만 보장된다면, 그렇진 않습니다.

편집 : Neil에게, 나는 버퍼를 통해 모든 방법으로 이동하고 비트를 하나씩 확인하는 대신 일정 시간에 XOR 이후의 비트 위치를 얻는 방법을 찾고 싶습니다.

Answer 1

uint32_t temp = oldBuffer^newBuffer; 
uint32_t number = 0; 
uint32_t bitmask=1; 
while (temp != 0) 
{ 
    if (temp & 0x1) 
    { 
     processNumber(number, ((newBuffer & bitmask) != 0)); 
    } 
    number++; 
    temp = temp >> 1; 
    bitmask <<=1; 
} 
oldBuffer = newBuffer; 

2 슈퍼 작은 변화 ...

코드는 이미 당신은 아마도 하나 또는 '비트 이상을 사용하여 일부 성능을 얻을 수 있습니다

Answer 2

uint32_t temp=oldBuffer^newBuffer, ntemp=newBuffer; 
for(int b=0;temp;++b,temp>>=1,ntemp>>=1) 
    if(temp&1) processNumber(b,ntemp&1); 

Answer 3

매우 효율적이었다 twiddling '해킹을

• http://graphics.stanford.edu/~seander/bithacks.html

특히 '정수 로그 기준 2'(최상위 비트 세트의 위치)를 찾는 알고리즘. 이렇게하면 각 비트를 반복하는 것보다 직접 설정되는 비트를 결정할 수 있습니다. 당신이 상위 낮은에서의 비트를 처리해야하는 경우

, 당신은 카운트 비트 커니 핸의 방법에 약간의 수정을 사용할 수 있습니다

/* note: untested code */ 
while (temp) { 

    uint32_t bit = temp & (~(temp & (temp - 1)); /* isolate lowest bit */ 

    temp &= ~bit; 

    uint32_t bit_number = /* use find log base 2 hack */; 

    /* etc... */ 

} 

이 동일한 시간을 정확하게 수 while 루프의 반복 처리를해야한다 세트 비트 수. 원래 루프는 가장 높은 세트 비트의 비트 위치와 동일한 횟수만큼 반복합니다.

그러나이 코드가 초 임계 비트가 아닌 한 측정 가능한 차이가 있다면 놀랍습니다.

Answer 4

그 종류는 (oldBuffer^newBuffer)의 배포본이 무엇을 기대하는지에 따라 다릅니다. 완전히 무작위이고 전체 범위가 32 비트라면 평균 16 개의 루프가 있습니다.

한가지 가능한 해결책은 루프 (평균 4)로 설정되는 각 비트에 대해 4 배 (1 바이트마다) 한 후 1 시간이 이에 본

int lookup[255][8] = { 
    { -1, -1, -1, -1, -1, -1, -1, -1 }, // 0 has no bits set 
    { 0, -1, -1, -1, -1, -1, -1, -1 }, // 1 has only the 0th bit set 
    { 1, -1, -1, -1, -1, -1, -1, -1 }, // 2 has only the 1st bit set 
    { 0, 1, -1, -1, -1, -1, -1, -1 }, // 3 has the 0th, 1st bit set 
    { 2, -1, -1, -1, -1, -1, -1, -1 }, // 4 has only the 2nd bit set 
    ... 
    { 0, 1, 2, 3, 4, 5, 6, 7 }, // 255 has all bits set 
}  

같은 테이블을 만드는 것이다 - 이봐, 그거 16이야.

그러나 설정 비트 수가 낮 으면 (평균 32 비트의 절반보다 훨씬 적음) 테이블 조회가 중단됩니다.

불행히도 테이블 조회는 곱하기를 추가하고 사용할 때마다 추가되므로 반드시 좋지는 않습니다. 시험을해야합니다.다시 말해 set 비트가 일정 시간 내에 발견되지만 상수는 루프보다 클 수 있습니다. 그것은 얼마나 많은 세트 비트를 가져야하는지에 달려 있습니다.

Answer 5

표준 라이브러리를 사용하는 것은 어떻습니까? 교대 할 필요가 없으며, 등등 ... 비트가 참이되는지 테스트합니다. bitset 내의 비트에 대한 테스트는 일정한 시간 동안 보장됩니다. 그리고 그것은 훨씬 더 깔끔하고 이해할 수있는 글을 씁니다.

const std::bitset<32> oldbits(oldBuffer); 
const std::bitset<32> newbits (newBuffer); 

for(size_t index = 0; index != oldbits.size(); ++index) { 
    if(oldbits[ index ] != newbits[ index ]) { 
     processNumber(index, newbits[ index ]) 
    } 
} 

참고 : 비트에 직접 액세스 할 수 있으므로 XOR은 필요하지 않습니다. 당신은 일 수도 있고, 그것을 사용하여 성능을 절약 할 수 있습니다.

Answer 6

당신은 재귀 B-나무처럼 할 수있다 :

go(oldBuffer^newBuffer, 16, 0, newBuffer); 
... 

void go(temp, half, pos, bitValue) 
{ 
    if (half > 1) { 
     uint32_t mask = (1 << half) - 1; 
     if (temp & mask) go(temp & mask, half/2, pos, bitValue & mask); 
     temp >>= half; 
     if (temp & mask) go(temp & mask, half/2, pos + half, (bitValue >> half) & mask); 
    } else { 
     if (temp & 1) processNumber(pos, bitValue&1); 
     if (temp & 2) processNumber(pos+1, bitValue/2&1); 
    } 
}