[백준 17419번] 비트가 넘쳐흘러 - JAVA

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

17419번: 비트가 넘쳐흘러

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(br.readLine());
		String binaryStr=br.readLine();
		int cnt=0;
		for(char a:binaryStr.toCharArray()) {
			if(a=='1') {
				++cnt;
			}
		}
		System.out.println(cnt);
	}
}

문제에서 주어진 식 k=k-(k&((~K)+1))에 대한 이해가 필요하다.

~k+1은 k의 2의 보수로, k=10110(2)=-10 이라면 ~k+1=01001(2)+1=01010(2)=10 이다.

여기서 k와 그의 2의 보수인 ~k+1을 &연산하게 되면 둘의 비트 중 공통된 가장 작은 비트만 1로 남고 나머지는 0이 된다.

k&((~k)+1)=00010(2)

따라서 주어진 식은 k가 갖고 있는 비트 중 값이 1인 최하위 비트를 구하는 것이었다.

그런데 이가 0이 될 때까지 반복하라고 했으므로 k 내부의 비트 중 1의 개수를 구하는 것과 동일한 의미가 된다.

따라서 k가 가진 1의 개수를 카운트하고 출력하면 정답이 된다.