algorithms/binary/counting_bits.py at main · dichev/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
"""
# Counting Bits
Given an integer n, compute the number of 1 bits in the binary
representation of every number from 0 to n.
Return a list output such that output[i] represents the count of 1
bits in the binary form of i.
-----------------
for n = 8       vertical patterns                                                count
                                      base offset           right shift
                  --------------
0  000     ->       0    0    0          -0                           0           -> 0
1  001     ->       0    0    1          -1                           1           -> 1
2  010     ->       0    1    0          -2                    [1]    0           -> 1
3  011     ->       0    1    1          -2                    [1]    1           -> 2
4  100     ->       1    0    0          -4               [1    0]    0           -> 1
5  101     ->       1    0    1          -4               [1    0]    1           -> 2
6  110     ->       1    1    0          -4               [1    1]    0           -> 2
7  111     ->       1    1    1          -4               [1    1]    1           -> 3
8 1000     ->  1    0    0    0          -8          [1    0    0]    0           -> 1
"""""

def counting_bits(n):
    assert n >= 0 # ignoring negative integers:

    counts = [0] * (n + 1)
    base = 0
    for i in range(1, n + 1):
        if (i & (i - 1)) == 0:  # power of 2 check
            base = i
        counts[i] = counts[i - base] + 1

    return counts

def counting_bits_shift(n):
    assert n >= 0 # ignoring negative integers:

    counts = [0] * (n + 1)
    for i in range(1, n + 1):
        counts[i] = counts[i >> 1] + (isodd := i & 1)

    return counts

if __name__ == '__main__':
    from utils import test
    test(counting_bits(8), [0,1,1,2,1,2,2,3,1])
    test(counting_bits(5), [0,1,1,2,1,2])
    test(counting_bits(3), [0,1,1,2])
    for n in range(100):
        test(counting_bits(n), [i.bit_count() for i in range(n + 1)])
        test(counting_bits_shift(n), [i.bit_count() for i in range(n + 1)])


    from utils import plot_time_complexity
    plot_time_complexity(counting_bits, lambda n: n)
    plot_time_complexity(counting_bits_shift, lambda n: n)