백준17419 비트가 넘쳐흘러

작성일 | In

문제 링크

  • http://icpc.me/17419

문제 출처

  • 2019 선린 정올 1번

풀이

  1. 컴퓨터에서 음수를 저장할 때는 절댓값의 2의 보수를 저장합니다.
  2. 2의 보수를 만드는 것은 모든 비트를 반전시킨 뒤 1을 더하면 됩니다.

그러므로 (~K) + 1은 -K입니다.
식을 다시 쓰면 K = K - (K & -K) 가 됩니다.

Fenwick Tree를 알고 있는 사람이라면 K & -K 가 무엇을 의미하는지 바로 알 수 있습니다.
이진수에서 가장 뒤에 있는 1의 위치를 알아냅니다.

결국 문제에 주어진 식은 맨 뒤에 있는 1의 위치를 알아낸 후, 그 비트를 0으로 바꾸는 연산입니다.
비트열에서 1의 개수가 정답이 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
using namespace std;

int main(){
	int n; string s;
	cin >> n >> s;
	int ans = 0;
	for(auto i : s) ans += i == '1';
	cout << ans;
}