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}