haar_lib/misc/
bitwise_sum_popcount.rs

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