Skip to content

Instantly share code, notes, and snippets.

@holland01
Last active Apr 23, 2017
Embed
What would you like to do?
generates a graycode (recently edited to be simpler, faster, stronger...)
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
void print_bin(int iteration, int value)
{
char buffer[36];
memset(buffer, 0, sizeof(buffer));
for (int i = 0; i < 32; ++i) {
int bit = value & (1 << (31 - i));
buffer[i] = (char)0x30 + (char)!!bit;
}
printf("[%i] 0b%s = %i\n", iteration, buffer, value);
}
static void graycode(int *codes, int n)
{
int len = 1 << n;
for (int bit = 0; bit < n; ++bit) {
int period = (1 << (bit + 1)) - 1;
int parity = 0;
int counter = 0;
int p = 1 << bit;
for (int i = p; i < len; ++i) {
if ((counter & period) == 0) {
parity ^= p;
}
codes[i] ^= parity;
counter++;
}
}
}
int main(int argc, const char * argv[])
{
const int N = 16;
int *codes = calloc(1 << N, sizeof(*codes));
graycode(codes, N);
int len = 1 << N;
for (int i = 0; i < len; ++i) {
print_bin(i, codes[i]);
}
puts("Running dupe check.");
for (int i = 0; i < len; ++i) {
for (int j = 0; j < len; ++j) {
if (j != i && codes[i] == codes[j]) {
printf("Dupe: [%i] ", i);
print_bin(j, codes[j]);
}
}
}
puts("Running count check.");
for (int i = 0; i < len; ++i) {
int found = 0;
for (int j = 0; j < len && !found; ++j) {
if (codes[j] == i)
found = 1;
}
if (!found) {
printf("Could not find %i!\n", i);
}
}
puts("Running bit comparison check.");
for (int i = 0; i < (len - 1); ++i) {
int diff_count = 0;
for (int k = 0; k < N; ++k) {
int b0 = codes[i] & (1 << k);
int b1 = codes[i + 1] & (1 << k);
if (b0 != b1) {
diff_count++;
}
}
if (diff_count > 1) {
printf("(%i, %i) differ by more than one bit!\n", i, i + 1);
}
}
free(codes);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment