leetcode-php/src/leetcode/CountingBits.php at master · imajinyun/leetcode-php · 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
56
57
58
59
60
61
62
63
64
65
66
67
<?php

declare(strict_types=1);

namespace leetcode;

class CountingBits
{
    public static function countBits(int $num): array
    {
        if ($num <= 0) {
            return [];
        }
        $bits = array_fill(0, $num + 1, 0);
        for ($i = 1; $i <= $num; $i++) {
            $bits[$i] = $bits[$i & ($i - 1)] + 1;
        }

        return $bits;
    }

    public static function countBits2(int $num): array
    {
        if ($num <= 0) {
            return [];
        }
        $bits = array_fill(0, $num + 1, 0);
        $bits[0] = 0;
        for ($i = 1; $i <= $num; $i++) {
            $bits[$i] = ($i & 1) === 0 ? $bits[$i >> 1] : $bits[$i - 1] + 1;
        }

        return $bits;
    }

    public static function countBits3(int $num): array
    {
        if ($num <= 0) {
            return [];
        }
        $bits = array_fill(0, $num + 1, 0);
        $bits[0] = 0;
        $pow = 1;
        for ($i = 1, $t = 0; $i <= $num; $i++, $t++) {
            if ($i === $pow) {
                $pow *= 2;
                $t = 0;
            }
            $bits[$i] = $bits[$t] + 1;
        }

        return $bits;
    }

    public static function countBits4(int $num): array
    {
        if ($num <= 0) {
            return [];
        }
        $bits = array_fill(0, $num + 1, 0);
        for ($i = 1; $i <= $num; $i++) {
            $bits[$i] = $bits[$i / 2] + $i % 2;
        }

        return $bits;
    }
}