algorithm-examples/cpp-algorithm/src/primitive/compute_parity.h at main · codejsha/algorithm-examples · 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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#ifndef CPP_ALGORITHM_COMPUTE_PARITY_H
#define CPP_ALGORITHM_COMPUTE_PARITY_H

#include <array>

namespace ComputingParity
{
    /**
     * \brief Count the number of bits that are set to 1.
     * \param x input number
     * \return count of 1s
     */
    short CountBits(unsigned int x);

    /**
     * \brief Compute parity of word.
     * \param x input number
     * \return parity of word
     */
    short Parity(unsigned long long x);

    /**
     * \brief Compute parity by dropping the lowest set bit.
     * \param x input number
     * \return parity of word
     */
    short ParityDropLowestBits(unsigned long long x);

    /**
     * \brief Compute parity by caching the results.
     * \param x input number
     * \return parity of word
     */
    short ParityLookupTable(unsigned long long x);

    // TODO: Implement ParityLookupTableXor
    short ParityXor(unsigned long long x);
}

// ----------------------------------------------------------------------------
inline short ComputingParity::CountBits(unsigned int x)
{
    short num_bits = 0;
    while (x)
    {
        num_bits += x & 1;
        x >>= 1;
    }
    return num_bits;
}

// ----------------------------------------------------------------------------
inline short ComputingParity::Parity(unsigned long long x)
{
    short result = 0;
    while (x)
    {
        result ^= (x & 1);
        x >>= 1;
    }
    return result;
}

// ----------------------------------------------------------------------------
inline short ComputingParity::ParityDropLowestBits(unsigned long long x)
{
    short result = 0;
    while (x)
    {
        result ^= 1;
        x &= (x - 1);
    }
    return result;
}

// ----------------------------------------------------------------------------
inline std::array<short, 1 << 16> BuildTable()
{
    std::array<short, 1 << 16> result{};
    for (int i = 0; i < (1 << 16); ++i)
    {
        result[i] = ComputingParity::Parity(i);
    }
    return result;
}

// ----------------------------------------------------------------------------
inline short ComputingParity::ParityLookupTable(const unsigned long long x)
{
    constexpr int mask_size = 16;
    constexpr int bit_mask = 0xFFFF;
    static std::array<short, 1 << 16> precomputed_parity = BuildTable();

    return precomputed_parity[x >> (3 * mask_size)]
           ^ precomputed_parity[(x >> (2 * mask_size)) & bit_mask]
           ^ precomputed_parity[(x >> mask_size) & bit_mask]
           ^ precomputed_parity[x & bit_mask];
}

#endif