Bitwise pop count and find first set

A Swar Algorithm for popcount 

/**
Bitwise pop count and find first set

Find First Set
get least significant bit index
comkiwer

https://www.playingwithpointers.com/blog/swar.html
*/
#include <cstdio>
 
typedef unsigned int UI;
 
UI popcount(UI x){
    x -= (x>>1) & 0x55555555;
    x = (x&0x33333333) + ((x>>2)&0x33333333);
    return (((x+(x>>4))&0x0F0F0F0F)*0x01010101)>>24;
}
 
/***
swar 코드를 풀어 보면 아래와 같다.
swar 코드는
2비트에서 나올 수 있는 popcount는 2비트(3)를 넘지 않고,
8비트에서 나올 수 있는 popcount는 4비트(15)를 넘지 않고,
32비트에서 나올 수 있는 popcount는 8비트(127)를 넘지 않는 특징을 이용한다.

< 2개의 비트씩 구하기 >
j = (i >> 1) & 0x55555555; 짝수 비트 자리의 1인 비트 남기기
i = i - j; // 결국엔 두개의 비트씩 popcount를 구하는 것이다.
두 비트는 아래 4가지가 있다.
00 에서 popcount는 0개 (00 - 00 = 00)
01 에서 popcount는 1개 (01 - 00 = 01)
10 에서 popcount는 1개 (10 - 01 = 01)
11 에서 popcount는 2개 (11 - 01 = 10)

< 4개의 비트씩 구하기 >
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);

< 8개의 비트씩 구하기 >
i = (i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F)
그런데 8비트에서 popcount는 4비트를 넘지 않으므로
i = ((i + (i>>4)) & 0x0F0F0F0F) 로 줄여 쓸 수 있다.

< 전체 비트수 구하기 >
8개의 비트씩 나누어 구한 결과가 8비트씩 4곳에 저장되어 있다.
i = i * 0x01010101
i = i>>24           를 이해 하기 위하여 아래 예를 보자.
abcd * 1111의 결과는 아래와 같다.
   (a)bcd
  a(b)cd
 ab(c)d
abc(d)

비트 연산에서는 ()값들 왼쪽 값은 범위를 벗어나므로 버림된다.
남은 값에서 ()값들만 남기는 것이 i = i>>24이다.
*/
 
 
 
UI popcount2(UI x){
    x = (x & 0x55555555) + ((x>>1) & 0x55555555);
    x = (x & 0x33333333) + ((x>>2) & 0x33333333);
    x = (x & 0x0F0F0F0F) + ((x>>4) & 0x0F0F0F0F);
    x = (x & 0x00FF00FF) + ((x>>8) & 0x00FF00FF);
    x = (x & 0x0000FFFF) + ((x>>16) & 0x0000FFFF);
    return x;
 
}
 
UI ffs(UI x){
    if(!x) return 0;
    return popcount((x&-x)-1)+1;
}
 
 
UI popcount64(UI x) {
  x -= ((x >> 1) & 0x5555555555555555);
  x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
  return (((x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F) * 0x0101010101010101) >> 56;
 
}
 
int main(){
    int i, N = 10000000;
    for(i=1;i<=N;++i){
        int p1 = __builtin_ffs(i);
        int p2 = ffs(i);
        if(p1 != p2){
            printf("%d : %d %d\n", i, p1, p2);
        }
    }
    return 0;
}