int x;
int cnt = 0;
1번
for(int i = 1; i < x ; i <<= 1) {
if( ( i & x ) != 0 ) ) cnt++;
}
2번
while(x) {
x = x & (x-1);
cnt++;
}
1번과 2번 모두 맞는 거 같은데 확인점.. 그리고 이 방법 말고 더 좋은 다른 방법 있나요
int x;
int cnt = 0;
1번
for(int i = 1; i < x ; i <<= 1) {
if( ( i & x ) != 0 ) ) cnt++;
}
2번
while(x) {
x = x & (x-1);
cnt++;
}
1번과 2번 모두 맞는 거 같은데 확인점.. 그리고 이 방법 말고 더 좋은 다른 방법 있나요
2는 x가 직접 바뀌니까 조심해서 써야겠죠
1은 등호 추가해야댈거고 __builtin_popcount 같은거도 쓸수있어요
C++ 20 부터는 bit헤더에 std::popcount가 있음 - dc App
loglog 시간에 찾을 수 있는 방법이 있긴 한데 이건 너무 나간거라 알 필요 없음 - dc App
각 비트에 1의 개수를 저장 -> 각 2비트마다 그 묶음에 있던 1의 개수를 저장 -> 각 4비트마다 그 묶음에 있던 1의 개수를 저장, 뭐 이런 식으로 하는 방법이 있음
팝카운트 못잃어~