서명되지 않은 int에서 비트 전환 수를 계산하는 가장 빠른 방법

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

  •  19-08-2019
  •  | 
  •  

문제

비트 전환 수를 세는 가장 빠른 방법을 찾고 있습니다. unsigned int.

int에 포함 된 경우 : 0b00000000000000000000000000001010

전환 수는 다음과 같습니다. 4

int에 포함 된 경우 : 0b00000000000000000000000000001001

전환 수는 다음과 같습니다. 3

언어는 C입니다.

도움이 되었습니까?

해결책 

int numTransitions(int a)
{
  int b = a >> 1; // sign-extending shift properly counts bits at the ends
  int c = a ^ b;  // xor marks bits that are not the same as their neighbors on the left
  return CountBits(c); // count number of set bits in c
}

효율적인 구현을 위해 카운트 비트 보다 http://graphics.stanford.edu/~seander/bithacks.html#countbitssetparallel

다른 팁

가장 빠른 시나리오에 따라 다릅니다. 데이터 타입을 일정한 크기 (부호없는 INT)로 지정하면 조회 테이블에서는 가능합니다. 그러나이 작업이 필요한 경우 테이블을 시작하기위한 일정한 오버 헤드가 너무 커서 INT를 통한 스캔+계산이 훨씬 빠릅니다.

전반적인 최선은 조합 일 것 같아요 : 바이트 또는 단어의 테이블을 찾아 보면 (256 또는 64k 항목이 그리 많지 않음), 바이트/단어를 마지막/첫 비트로 결합합니다.

C/C ++에서는 다음을 수행합니다.

unsigned int Transitions(unsigned int value)
{
    unsigned int result = 0;

    for (unsigned int markers = value ^ (value >> 1); markers; markers = markers >> 1)
    {
        if (markers & 0x01) result++;
    }

    return result;
}

Arithmetic Shift + XOR 및 Kernighan의 비트 계산 방법을 사용한 코드는 다음과 같습니다.

int count_transitions(int x)
{
    assert((-1 >> 1) < 0); // check for arithmetic shift
    int count = 0;
    for(x ^= (x >> 1); x; x &= x - 1)
        ++count;
    return count;
}

어떤 언어?

나는 64 번 반복 한 다음 비트를 비트를 비트를 검사하기 위해 숫자를 바꾸고 이전 비트를 저장하고 현재 비트와 비교할 것입니다. 다르면 카운트를 점점 봅니다.

자, 전환으로 0-s와 1-s의 문자열을 걸어 다니면 0이 1을 따르거나 1이 0을 따른다는 각각의 경우를 계산합니다.

비트를 바꾸고 변경 사항을 계산하여 쉽습니다.

transitions(n)
  result = 0
  prev = n mod 2
  n = n div 2
  while n<>0 
    if n mod 2 <> prev then
      result++
      prev = n mod 2
    fi
    n = n div 2
  elihw
  return result

모드와 div를 교대로 교체 할 수 있습니다.

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