[백준 17419번] 비트가 넘쳐흘러 (C++)

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

17419번: 비트가 넘쳐흘러

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N;
    string K;
    cin >> N >> K;

    int cnt = 0;

    for(int i=0; i<K.size(); i++)
    {
        if(K[i]=='1') cnt++;
    }

    cout << cnt;

    return 0;
}

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

위 연산에 대해서 직접 0이 될때까지 계산을 반복해 보았다.

예제 값을 기준으로 맨 처음 값은 10110이다.

10110 (~K) -> 01001

01001 + 1 -> 01010

10110 & 01010 -> 00010

10110 - 00010 -> 10100

 

10100을 시작으로 다시 계산하면 10000

10000을 시작으로 다시 계산하면 00000이 된다.

 

이러면 10110 -> 10100 -> 10000 -> 00000 순으로 변하는 것을 볼 수 있다.

이를 보면 최하위 비트 1의 값이 순서대로 없어지는 것을 볼 수 있다.

따라서 한 번의 계산마다 한 번의 1이 사라지므로 단순히 입력받은 2진수의 1만 카운트하면 된다.