SWEA 10908. 짝수인 이항 계수

음이 아닌 정수 N이 주어진다. 이 때, N + 1개의 이항 계수(N 0)~(N N) 중에서 짝수인 것의 개수를 구하는 문제이다.

 

N을 이진수로 할 때 비트의 수를 c라고 하면  어떤 정수 N이 주어졌을 때, (N 0)~(N N)의 총 N+1개의 이항 계수 중 홀수의 개수는  2^c 개 이다. 전체 갯수에 2^c 를 빼주면 된다.

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

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        StringBuilder sb = new StringBuilder();
        for (int tc = 1; tc <= T; tc++) {
            sb.append('#').append(tc).append(' ');
            long n = Long.parseLong(br.readLine());
            long bitCount = Long.bitCount(n);
            long oddCount = 1L << bitCount;
            sb.append(n+1 - oddCount).append('\n');
        }
        
        br.close();
        System.out.print(sb);
    }
}