정수에서 1의 개수 계산 C

Question

for 루프 또는 while 루프를 사용하지 않고 0xFF보다 큰 상수를 사용하지 않고 C의 32 비트 정수 x에서 1의 수를 계산하는 가장 좋은 방법은 무엇입니까?

내가 생각한 것은 x24를 오른쪽으로 시프트하고 이동 된 정수에 얼마나 많은 1이 있는지 계산하고이를 가변 개수로 저장하는 것입니다. 그런 다음 x 16을 오른쪽으로 시프트하고 시프트 된 정수에서 1의 수만큼 카운트를 증가시킵니다.

그럼 더 좋은 해결책이 있습니까?

Answer 1

모든 d 비트 수의 1의 수를 도표화 할 수 있습니다. 이 테이블은 d (<255)을 초과하지 않는 2^d 항목의 표를 사용합니다.

이제 d 비트의 조각으로 번호를 잘라 내고 모든 조각의 개수를 조회 할 수 있습니다.

공간/작업 수 사이의 좋은 절충은 아마도 d=4 (8 조각, 테이블 크기 = 16) 일 것입니다.