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

17419번 : 비트가 넘쳐흘러

---

문제)

🎶 DJ욱제는 비트에 몸을 맡기는 중이다. 🎶

DJ욱제는 비트에 심취한 나머지, 비트를 비틀어 제껴버리는 문제를 내 버렸다!

N자리 이진수 K가 주어진다. K가 0이 아닐 때까지 아래의 연산을 적용했을 때, 연산이 일어나는 횟수를 구하시오.

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

아래는 위의 연산에 사용된 연산자에 대한 설명이다.

• '+'는 산술 더하기 연산이다. (5 + 2 = 7)
• '-'는 산술 빼기 연산이다. (5 - 2 = 3)
• '&'는 비트 AND 연산이다. (1101 & 0111 = 0101)
• '~'는 비트 NOT 연산이다. 켜진 비트를 끄고, 꺼진 비트를 켜는 연산이다. (~1101 = 0010)

 

 

 

입력 :

첫째 줄에 N이 주어진다.

둘째 줄에 N자리 이진수 K가 주어진다. K는 0으로 시작하지 않는다. 즉, leading zero는 없다.

 

 

출력 :

연산이 일어나는 횟수를 출력한다.

 

 

 

 

 

풀이)

 

#include <iostream>
#include <bitset>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int n;
    cin >> n;
    
    char k;
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> k;
        if (k == '1') cnt++;
    }
 
    cout << cnt;
 
 
    // k =                "10101100" 이라고 하면
    // ~k =                "01010011"
    // ~k + 1 =            "01010100"
    // k & (~k + 1) =    "00000100"
    // k - k =            "10101000" 
 
    // 정리하면 
    // "10101100" => "10101000"
    // 가장 오른쪽에 있는 비트 1을 지우는 것이므로,
    // 주어진 이진수k에 비트1의 개수를 세어주면 된다.
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/17419 

17419번: 비트가 넘쳐흘러