[백준 17419] 비트가 넘쳐흘러

문제 링크 : https://www.acmicpc.net/problem/17419

17419번: 비트가 넘쳐흘러

K = K-(K&((~K)+1))

 

문제에 나오는 연산을

 

10110을 대상으로 한번 실행해보자

 

~K 는 01001

 

여기에 1을 더하면

 

01010

 

기존의 K와 &연산을 하면 00010

 

기존에 K에서 이를 빼면 10100

 

---

 

연산을 여러번 반복해보면 알겠지만

 

위 식은 K라는 이진수에서 마지막 1을 빼는 연산이다

 

팬윅트리에서 사용되기도 한다.

 

---

 

결국 입력에서 1의 개수를 세는 문제이다.

 

#include <iostream>
using namespace std;

int main(void) {
	int n, res = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		scanf("%1d", &a);
		if (a == 1) {
			res++;
		}
	}
	cout << res << endl;

	return 0;
}