homeposts rss services talks gpg

Code Golf: Dedup an array of unsigned integers

2022-09-15

I stumbled across some code golf the other day. A fairly typical problem. Remove duplicates from an array/stream/whatever. Rather than use a set or other typical data structure that only allows one entry, I thought it’d be fun to convert the number to base 2

uint64_t get_mask(uint64_t i) {
	return(pow(2, i));
}

Then use a bitwise or to store the result in an array.

void insert(uint64_t i, uint64_t *b) {
	*b |= get_mask(i);
}

Then checking for the existence is a bit shift and bitwise and.

uint64_t member(uint64_t i, uint64_t *b) {
	return (*b >> i) & 1;
}

Anyway, here’s the whole thing

#include <stdbool.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <math.h>

enum { LEN = 8 };

uint64_t get_mask(uint64_t i) {
	return (pow(2, i));
}

bool member(uint64_t i, uint64_t *b) {
	return (*b >> i) & 1;
}

void insert(uint64_t i, uint64_t *b) {
	*b |= get_mask(i);
}
void display(uint64_t *t, int i, int j) {
	while (i <= j)
		printf("%ld ", t[i++]);
	printf("\n");
}

int main(void) {
	uint64_t i[] = { 9, 4, 6, 32, 5, 9, 8, 2, 1, 7, 8, 12, 11, 8, 9, 25 };
	uint64_t b[LEN] = {};
	size_t h = sizeof(i) / sizeof(uint64_t);
	int j = 0, k = 0, rl = h - 1;
	display(i, 0, rl);
	do {
		if (!member(i[j], b)) {
			i[k++] = i[j];
			insert(i[j], b);
		} else
			rl--;
	} while (j++ <= h);
	display(i, 0, rl + 1);
}