정수에서 최하위 세트 비트의 위치를 ​​효율적으로 찾을 수 있는 방법은 무엇입니까?

최하위 세트 비트 위치 판별

프로그래밍에서 세트되는 최하위 비트(LSB) 위치 판별 정수로 사용하는 것은 유용한 작업이 될 수 있습니다. 간단한 구현에는 정수를 1로 반복적으로 마스킹하고 결과가 0이 아닐 때까지 오른쪽으로 이동하는 것이 포함되지만 이 방법은 큰 정수의 경우 속도가 느릴 수 있습니다.

비트 조정 최적화

비트 조작 해킹은 효율적인 대안을 제공합니다. "곱하기 및 조회" 방법으로 알려진 이러한 해킹 중 하나는 de Bruijn 수열의 속성을 활용하여 단일 단계로 계산을 수행합니다.

코드 구현

unsigned int v;  // find the number of trailing zeros in 32-bit v
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

설명

이 코드는 정수 v를 곱하여 작동합니다. 마법 상수를 사용하여 결과에 비트 시프트를 수행합니다. MultiplyDeBruijnBitPosition 배열은 곱셈 결과를 LSB의 원하는 위치에 매핑합니다.

이점 및 참조

이 방법은 특히 다음과 같은 경우 간단한 구현보다 훨씬 빠릅니다. 큰 정수. 이 기술에 대한 더 많은 통찰력과 자세한 설명은 다음을 참조하세요.

• "De Bruijn 시퀀스를 사용하여 컴퓨터 단어에서 1 색인 생성"
• "보드 표현 > Bitboards > 비트스캔"

위 내용은 정수에서 최하위 세트 비트의 위치를 ​​효율적으로 찾을 수 있는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!