#include<cstdlib>
#include<cstdint>

//From: https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightLinear
unsigned int trailing_zeros(unsigned int v)
{
    unsigned int c = 32;
    v &= -signed(v);
    if (v) c--;
    if (v & 0x0000FFFF) c -= 16;
    if (v & 0x00FF00FF) c -= 8;
    if (v & 0x0F0F0F0F) c -= 4;
    if (v & 0x33333333) c -= 2;
    if (v & 0x55555555) c -= 1;

    return c;
}

class Counter
{
private:
    const unsigned int k;
    int64_t **counters;

public:
    Counter(const unsigned int k) : k(k)
    {
        const unsigned int n = 1u << k;
        counters = new int64_t*[n];
        for(unsigned int i=0; i<n; i++)
        {
            unsigned int z = trailing_zeros(i);
            z = (z<=k)?z:(k+1);
            counters[i] = new int64_t[z];
            for(unsigned int j=0; j<z; j++)
                counters[i][j] = 0;
        }
    }

    ~Counter()
    {
        const unsigned int n = 1u << k;
        for(unsigned int i=0; i<n; i++)
            delete[] counters[i];

        delete[] counters;
    }

    void offset(unsigned int i, const unsigned int delta)
    {
        i++;
        unsigned int x = 0;
        for(int j = k; i; j--)
        {
            unsigned int y = (1u << j);
            if(i & y)
            {
                counters[x][j]+=delta;
                x+=y;
                i&=~y;
            }
        }
    }

    int64_t eval(unsigned int i)
    {
        int64_t r = 0;
        for(int j=0; j<=k; j++)
        {
            unsigned int y = (1u << j);
            if(i & y)
                i &= ~y;
            else
               r+=counters[i][j];
        }

        return r;
    }
};


int main()
{
    const unsigned int k = 12;
    const unsigned int n = 1u << k;

    Counter C(k);
    for(unsigned int i=0; i<n; i++)
    {
        C.offset(i, 1);
        for(unsigned int j=0; j<n; j++)
            if(C.eval(j) != ((j<=i)?(i+1-j):0))
                return EXIT_FAILURE;
    }

    return EXIT_SUCCESS;
}