[BaekJoon] 9527 1의 개수 세기 (Java)

1.  문제 링크

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

2.  문제

요약

• 두 자연수 A, B가 주어졌을 때, A <= x <= B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 $10^16$보다 작거나 같은 두 자연수 A, B가 주어집니다.
• 출력: 첫 번째 줄에 1의 개수를 세어 출력합니다.

3.  소스코드

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

public class Main {
    static long A, B;
    static long[] oneNumByBit;

    static void input() {
        Reader scanner = new Reader();

        A = scanner.nextLong();
        B = scanner.nextLong();
        oneNumByBit = new long[55];
    }

    static void solution() {
        calcAllOneNum();

        System.out.println(getOneNum(B) - getOneNum(A - 1));
    }

    static long getOneNum(long num) {
        long answer = num & 1;

        for(int idx = oneNumByBit.length - 1; idx > 0; idx--) {
            if((num & (1L << idx)) > 0L) {
                answer += oneNumByBit[idx - 1] + (num - (1L << idx) + 1);
                num -= (1L << idx);
            }
        }

        return answer;
    }

    static void calcAllOneNum() {
        oneNumByBit[0] = 1L;

        for(int idx = 1; idx < oneNumByBit.length; idx++)
            oneNumByBit[idx] = oneNumByBit[idx - 1] * 2 + (1L << idx);
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}