SWAR(SIMD Within A Register)

분할정복, 비트 마스킹을 활용하여 레지스터 내부에서 병렬 덧셈을 수행함.
브랜치리스(Branchless) 알고리즘이다.

uint32_t popcount(uint32_t n) {
    n = n - ((n >> 1) & 0x55555555);                   // Step 1: 2비트 그룹 합산
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);    // Step 2: 4비트 그룹 합산
    n = (n + (n >> 4)) & 0x0F0F0F0F;                   // Step 3: 8비트 그룹 합산
    return (n * 0x01010101) >> 24;                     // Step 4: 최종 누적 및 시프트
}

Step1 (2bit 합산)

n = n - ((n >> 1) & 0x55555555) => 0101
1011 -> (1+0) (1+1) -> 01 10
1의 개수를 저장하게 되는데, n=11(10진수)라면, n=00001011, 비트연산 후(00000101)
n에서 빼면, 00000110이 된다.

Step2(4bit)

n=00000110이므로, 왼쪽 비트연산부터 하면, 00000010, 오른쪽은 00000001
더하면 즉, 00000010+00000001=00000011

Step3(8bit)

4bit끼리 더함

Step4(final)

총 32bit로 합친다.