Link | 백준 9527번 문제 : 1의 개수 세기
문제만 보았을 때는 범위 내의 숫자들를 비트열로 변환하고 1의 개수를 세면 될 것 같다.
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
long from = Long.parseLong(tokenizer.nextToken());
long to = Long.parseLong(tokenizer.nextToken());
LongStream.rangeClosed(from, to).map(i -> Long.toString(i, 2).replaceAll("0", "").length())
.sum();
하지만 입력값의 범위를 보면 너무 크다는 것을 알 수 있다.
입력값은 1 이상 이다. 즉, 위의 방법으로는 단순 탐색만하는데도 시간초과가 발생한다.
그렇기 때문에 이번 문제는 수학적으로 해결해야 한다.
숫자들을 비트열로 차례대로 탐색하면 규칙을 확인할 수 있다.
첫 번째 비트는 0101010101...으로 반복된다.
두 번째 비트는 001100110011...으로 반복된다.
세 번째 비트는 0000111100001111...으로 반복된다.
정리하자면 비트의 위치에 따라 반복되는 숫자를 알 수 있고 숫자 N까지의 1 개수를 계산할 수 있다.
계산식은 다음과 같다.
N의 비트열 길이를 L이라 하고 비트의 위치를 오른쪽부터 1이라고 하면,
위치 의 1 비트 수 이다.
1부터 N까지의 1비트 개수는 이다.
주어진 범위가 FROM ~ TO 일 때 (N = TO) - (N = FROM - 1)을 계산하면 된다.
public void solve() throws IOException {
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
long from = Long.parseLong(tokenizer.nextToken());
long to = Long.parseLong(tokenizer.nextToken());
result.append(count(to) - count(from - 1));
}
private long count(long num) {
long count = 0;
int len = Long.toString(num, 2).length();
for (long i = 1; i <= len; i++) {
long ca = ((num + 1) / (long) Math.pow(2, i)) * (long) Math.pow(2, i - 1);
long cb = ((num + 1) % (long) Math.pow(2, i)) - (long) Math.pow(2, i - 1);
count += ca + Math.max(cb, 0);
}
return count;
}