Bit counting, array convolution to uint64_t

// Denis Gorodetskiy, [email protected]

// Given an array A with elements A[i] from range [0..63]
// for instance, A = {1, 2, 5},
// we convolute their elements to a single uint64_t variable V = {0,1,1,0,0,1}
// with bits set at positions pointed by array elements A[i]

#include <assert.h>
#include <stdint.h>

using namespace std;

// sets a bit of integer v at position bitpos
void setbit(uint64_t & v, int bitpos)
{
    assert(bitpos >= 0 && bitpos < 64);
    uint64_t mask = 0x1;
    mask <<= bitpos;
    v |= mask;
}

template < typename T >
uint64_t value_bits(T & arr, size_t length)
{
    uint64_t ret = 0;
    for(int i = 0; i < length; ++i)
    {
        setbit(ret, arr[i]);
    }
    return ret;
}

static const int8_t bittable[] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
};

template < typename T >
int bitcount(T v)
{
    // use __popcnt(v) intrinsic instead of this function if your cpu supports it.

    int bits = 0;

    for(int i = 0; i < sizeof(T); ++i)
    {
        uint8_t ch = v & 0xFF;
        v >>= 8;
        bits += bittable[ch];
    }
    return bits;
}

int main(int argc, char * argv[])
{
    int arr1[] =  {0, 1, 2, 3, 10, 11, 23};
    int arr2[] = {1, 2, 3, 4, 23};

    uint64_t v1 = value_bits(arr1, 7);
    uint64_t v2 = value_bits(arr2, 5);

    int num_common_elements = bitcount(v1 & v2);

    assert(num_common_elements == 4);

    return 0;
}