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

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

 

\[K = K-(K\&((\sim K)+1))\]

위 식을 그대로 직접 구현해버리면 n이 최대 100만이기 때문에 시간초과입니다.

논리회로 시간에 배웠던걸 생각해보면 (~K)+1은 사실 -K를 2의 보수로 나타낸 것임을 알 수 있습니다. 그럼 위 식은 아래와 같이 바뀝니다

\[K = K-(K \& -K)\]

K & -K는 K에서 1인 비트중 최하위 비트입니다. 예를 들어 이진법으로 K=10110이라고 하면 (K & -K)는 00010이 됩니다. 노트에 적어보면 바로 이해가 됩니다. 펜윅트리 인덱스 계산할 때도 이 방식이 이용된다고 하네요.

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n;
	string s;
	cin >> n >> s;

	int counter = 0;
	for (auto& c : s)
		if (c == '1')
			++counter;

	cout << counter << '\n';

	return 0;
}