[백준 9527] 1의 개수 세기 (C#, C++) - soo:bak

문제 링크

9527번 - 1의 개수 세기

설명

A 이상 B 이하의 모든 정수를 이진수로 표현했을 때, 1의 개수의 총합을 구하는 문제입니다.

각 비트 자리마다 0과 1이 일정한 주기로 반복됩니다. 이 주기성을 이용하면 0부터 N까지의 1 총합을 효율적으로 계산할 수 있습니다.

접근법

먼저 0부터 7까지의 이진수를 살펴봅니다.

0: 000    1: 001    2: 010    3: 011
4: 100    5: 101    6: 110    7: 111

0번째 비트(맨 오른쪽)는 0,1,0,1,0,1,0,1로 주기가 2이고, 한 주기에서 1이 1번 나옵니다.

1번째 비트는 0,0,1,1,0,0,1,1로 주기가 4이고, 한 주기에서 1이 2번 나옵니다.

2번째 비트는 0,0,0,0,1,1,1,1로 주기가 8이고, 한 주기에서 1이 4번 나옵니다.

다음으로 이 패턴을 일반화합니다. i번째 비트는 2^(i+1) 주기로 반복되고, 한 주기에서 1이 2^i번 나옵니다. 0부터 N까지에서 완전한 주기 수와 나머지 부분의 1 개수를 각 비트마다 계산하여 모두 더합니다.

이후 구간 [A, B]의 답은 (0부터 B까지의 총합) - (0부터 A-1까지의 총합)으로 계산합니다.

시간 복잡도는 O(log N)입니다.

Code

C#

using System;

namespace Solution {
  class Program {
    static long CountOnes(long n) {
      if (n < 0)
        return 0;
      var sum = 0L;
      for (var i = 0; i < 63; i++) {
        var bit = 1L << i;
        var cycle = bit << 1;
        var full = (n + 1) / cycle;
        var rem = (n + 1) % cycle;
        sum += full * bit + Math.Max(0, rem - bit);
      }
      return sum;
    }

    static void Main(string[] args) {
      var parts = Array.ConvertAll(Console.ReadLine()!.Split(), long.Parse);
      var a = parts[0];
      var b = parts[1];
      var ans = CountOnes(b) - CountOnes(a - 1);
      Console.WriteLine(ans);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll countOnes(ll n) {
  if (n < 0)
    return 0;
  ll sum = 0;
  for (int i = 0; i < 63; i++) {
    ll bit = 1LL << i;
    ll cycle = bit << 1;
    ll full = (n + 1) / cycle;
    ll rem = (n + 1) % cycle;
    sum += full * bit + max(0LL, rem - bit);
  }
  return sum;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll a, b; cin >> a >> b;
  ll ans = countOnes(b) - countOnes(a - 1);
  cout << ans << "\n";

  return 0;
}