haar_lib/algo/
bitwise_popcount.rs

1//! 0以上n以下の自然数について、2進数表記で各桁のビットが`1`である個数を数える。
2
3/// 0以上n以下の自然数について、2進数表記で各桁のビットが`1`である個数を数える。
4///
5/// # Problems
6/// - <https://atcoder.jp/contests/abc356/tasks/abc356_d>
7/// - <https://yukicoder.me/problems/no/2939>
8pub fn bitwise_popcount(n: u64) -> [u64; 64] {
9    let mut ans = [0; 64];
10
11    for (i, ans) in ans.iter_mut().enumerate() {
12        if n < (1 << i) {
13            break;
14        }
15
16        let n = n as u128 + 1;
17        let c = 1 << i;
18        let dc = 1 << (i + 1);
19
20        *ans = ((n / dc) * c) as u64;
21
22        if n % dc >= c && n % dc < dc {
23            *ans += (n % dc - c) as u64;
24        }
25    }
26
27    ans
28}