brian kernighan's algorithm

2진법 수에서 1의 수(cnt) 를 세는 알고리즘.

 

N = 11010(2) 에서 1의 수를 세보자.

일단 N - 1을 구한다.  N - 1  = 11001(2)

N, (N - 1)을 AND 연산한다.  N & (N - 1)  = 11000(2)

연산 결과는 N에서 뒤에서부터 가장 처음나오는 1 비트를 삭제한 결과와 같다.

1비트가 하나 있어서 삭제되었으므로 cnt + 1을 해준다.

이를 N이 0보다 큰경우 반복한다. (N이 0보다 큰 경우 1이 반드시 한 개 있다는 의미이므로)

 

#include<iostream>

using namespace std;

int main() {
	int N;
	cin >> N;
    
	int cnt = 0;
	while (N > 0) {
		N &= (N - 1);
		cnt++;
	}
	cout << cnt << endl;
    
	return 0;
}

 

시간복잡도는 O(logN)