[JAVA 알고리즘]BAEKJOON 9527번 1의 개수 세기

1의 개수 세기

---

문제 설명

두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라고 정의하고, 아래 식의 결과를 구하자.

 ∑𝑥=𝐴𝐵𝑓(𝑥)

입력

첫 줄에 두 자연수 A, B가 주어진다. (1 ≤ A ≤ B ≤ 10^16) 

출력

1의 개수를 세어 출력한다.

제한사항

• 없음

입출력 예

input	return
2 12	21

---

문제 분석

문제에서 주어지는 값이 10^16으로 int의 범위를 넘어 가므로 long을 사용해야 한다.

비트마스크를 사용하기 위해서 최대 값인 10^16을 이진수로 했을 경우, 총 57자리의 크기가 필요하므로 최대크기를 57로 지정해 준다.

이진수에서 나올 수 있는 1의 개수를 먼저 확인해 본다. 

1	0	0	0	1
2	0	0	1	0
3	0	0	1	1
4	0	1	0	0
5	0	1	0	1
6	0	1	1	0
7	0	1	1	1
8	1	0	0	0
9	1	0	0	1
10	1	0	1	0
11	1	0	1	1
12	1	1	0	0
13	1	1	0	1
14	1	1	1	0
15	1	1	1	1

 

비트마스크로 표기하기 위해서 자릿수 기준으로 나누게 되면 1 -> 2 -> 4 -> 8개로 증가하는 것을 볼 수 있다.

나머지 1의 경우는 맨 앞 개수의 절반 x 남은 자릿수로 규칙이 나와 자리별로 나올 수 있는 1의 총 개수들을 알 수 있다.

그럼 이제 기준이 되는 1의 개수들을 가지고 주어지는 값에 들어가는 1의 수를 더해준다.

주어진 값을 큰 값 - 작은 값을 해주면 작은 값에서 큰 값까지의 합을 구할 수 있다.

나의 문제풀이

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

public class Main {

    static int max = 57;
    static long[] nums;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        long A = Long.parseLong(stringTokenizer.nextToken()) - 1;
        long B = Long.parseLong(stringTokenizer.nextToken());

        nums = new long[max];
        nums[0] = 1;
        for (int i = 1; i < max; i++) {
            nums[i] = nums2[i - 1] + (1L << i) + ((1L << i) / 2) * i;
        }

        System.out.println(getOne(B) - getOne(A));
    }

    private static long getOne(long num) {
        long sum = num & 1;
        for (int i = max - 1; i > 0; i--) {
            if ((num & (1L << i)) != 0) {
                sum += nums[i - 1] + (num - (1L << i) + 1);
                num -= 1L << i;
            }
        }
        return sum;
    }
}

---

알고리즘 분류

• 수학
• 누적 합
• 비트마스킹

문제 출처 - https://www.acmicpc.net/problem/9527