백준 17419번: 비트가 넘쳐흘러

문제 설명

• https://www.acmicpc.net/problem/17419
• K = K-(K&((~K)+1)) 연산을 몇 번 진행했을 때 K가 0이 되는지 구하는 문제입니다.

접근법

• ~K+1 연산은 K의 모든 비트값을 뒤집은 뒤 1을 더하는 연산입니다.

  • 1을 더하는 연산을 예시와 함께 살펴봅시다.
    • 1110+1 = 1111 입니다.
      • 해당 자리의 값이 0이면 1로 바뀌고 멈춥니다.
    • 0001+1 = 0010 입니다.
      • 해당 자리의 값이 1이면 0으로 바뀌고 다음 자리를 확인합니다.
        • 다음 자리의 값이 0이면 1로 바뀌고 멈춥니다.
        • 다음 자리의 값이 1이면 0으로 바뀌고 다음 자리를 확인합니다.
    • 1011+1 = 1100 입니다.
      • 원래 1이였던 __11은 0이 되고 최초로 연속된 1이 끊긴 지점 _0__의 값이 1로 변하게 됩니다.
  • 즉 1을 더하는 연산은 앞에서부터 연속된 1을 0으로 바꾸고, '1의 연속'이 최초로 끊기는 지점의 0을 1로 바꿉니다.
    • 결론적으로 ????1 혹은 ???10, 더 나아가 ??1000....0모양이 됩니다.
  • 이는 곧 앞에서부터 최초의 0이 나올때까지의 비트값을 뒤집는 것과 동일합니다.

• 이제 K & ((~K)+1) 연산을 살펴봅시다.

  • K와~K는 모든 비트값이 다릅니다. 그렇기 때문에 K&~K의 결과값은 0입니다.
  • 하지만 위에서 살펴본 것과 같이 +1연산은 ~K의 앞에서부터 최초의 0이 나올때까지의 비트값을 뒤집는 것이기 때문에 +1연산의 결과로 ~K의 최초의 0인 값은 1이 됩니다.
    또한 ~K가 0이던 위치은 결국 K가 1이던 위치와 동일한 말이기 때문에 K & ((~K)+1)는 K에서 1인 비트중 최하위 비트의 결과를 반환합니다.
  • ~K+1은 결국 aa...a10...0이 됩니다.
    • a: K와 반대라는 의미입니다.
    • a는 K와 값이 반대이기 때문에 &연산 시 0이, 0은 false이기 때문에 &연산 시 0이 나옵니다.
  • k가 10110라면 ~K는 01001, ~K+1은 01010이 됩니다.
    그리고 10110 & 01010의 결과는 00010으로 K에서 1인 비트중 최하위 비트를 반환하게 됩니다.

• ~K+1연산을 2의 보수라 부르며 이는 -K와 같습니다.

• K-(K&((~K)+1)) = K-(K&(-K)) = K에서 1인 비트중 최하위 비트를 0으로 바꿔라라는 내용과 동일합니다.

정답

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		String s = br.readLine();
//		int num = Integer.parseInt(s, 2);
//		int cnt = 0;		
//		while(true) {
//			if(num == 0) break;
//			cnt++;
//			num = num - (num & (~num + 1));
//			System.out.println(Integer.toBinaryString(num));
//
//		}
//		System.out.println(cnt);
		int answer = 0;
		for (int i = 0; i < s.length(); i++) {
			if(s.charAt(i) == '1') answer++;
		}
		System.out.println(answer);
	}
}