c언어 17419번 비트가 넘쳐흘러 (백준)

#include <stdio.h>

int main(void)
{
    int n = 0;
    scanf("%d", &n);
    getchar();
    char s = 0;
    int ans = 0;
    while((s=getchar()) != '\n')
    {
        if(s=='1') ans++;
    } printf("%d", ans);
}

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

17419번: 비트가 넘쳐흘러

 

 

풀이  : 22(2) = 10110

 

10110

01010 == 22의 ~22+1

00010 == 2

 

22 - 2 == 20

 

20(2) = 10100

 

10100

01100 == 20의 ~20+1

00100 == 4

 

20 - 4 == 16

 

16(2) = 10000

10000

10000 == 16의 ~16+1

10000 == 16

 

16 - 16 == 0 //종료

 

위를 보면 알 수 있듯이

K = K-(K&(~K+1)) 가 한 번 수행되면 비트가 1인 것중 가장 아랫것 부터 0으로 바뀐다.

 

고로 이진수로 입력받은 수의 1의 비트의 개수가

K-(K&(~K+1))가 수행되는 횟수와 같다.