counting_bits.c

#include <stdio.h>
#include <stdint.h>
#include <limits.h>

#define BLOCK (1<<16)
#define MASK (BLOCK - 1)
typedef struct wordcount {
	int w0[BLOCK];
	int w1[BLOCK];
	int w2[BLOCK];
	int w3[BLOCK];
} wordcount;
typedef uint64_t bitcount[64];

void wordcount_add(wordcount *count, uint64_t v) {
	count->w0[(v>> 0) & MASK] += 1;
	count->w1[(v>>16) & MASK] += 1;
	count->w2[(v>>32) & MASK] += 1;
	count->w3[(v>>48) & MASK] += 1;
}

void bitcount_from(wordcount *count, bitcount *result){
	int n, bit;
	int value;
	bitcount total = {0};
	for(value = 0; value < BLOCK; value += 1){
		n = count->w0[value];
		if(n != 0){
			for(bit = 0; bit < 16; bit += 1){
				if((value >> bit) & 1){
					total[bit] += n;
				}
			}	
		}
		
		n = count->w1[value];
		if(n != 0){
			for(bit = 0; bit < 16; bit += 1){
				if((value >> bit) & 1){
					total[bit + 16] += n;
				}
			}			
		}

		n = count->w2[value];
		if(n != 0){
			for(bit = 0; bit < 16; bit += 1){
				if((value >> bit) & 1){
					total[bit + 32] += n;
				}
			}
		}
		
		n = count->w3[value];
		if(n != 0){
			for(bit = 0; bit < 16; bit += 1){
				if((value >> bit) & 1){
					total[bit + 48] += n;
				}
			}
		}
	}

	for(bit = 0; bit < 64; bit += 1){
		(*result)[bit] = total[bit];
	}
}

typedef struct { uint64_t state;  uint64_t inc; } pcg32_random_t;
uint32_t pcg32_random_r(pcg32_random_t* rng)
{
    uint64_t oldstate = rng->state;
    // Advance internal state
    rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
    // Calculate output function (XSH RR), uses old state for max ILP
    uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
    uint32_t rot = oldstate >> 59u;
    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}

int main(int argc, char const *argv[])
{
	srand(time(NULL));

	pcg32_random_t random = {0};

	printf("counting\n");
	wordcount count = {0};
	uint64_t i;
	for(i = 0; i < (1<<20); i += 1){
		uint32_t value = pcg32_random_r(&random);
		wordcount_add(&count, value);
	}

	printf("converting\n");
	bitcount result = {0};
	bitcount_from(&count, &result);

	printf("result\n");
	for(i = 0; i < 64; i += 1){
		printf("%d: %d\n", i, result[i]);
	}
	
	return 0;
}