14bits.c

/* The challenge:
 * [from <https://plus.google.com/114096598438625047207/posts/1PaeD94qgDS>]
 *
 * Write a pure function z = f(x, y), where x and y are 7-bit unsigned
 * integers and z is a 32-bit unsigned integer, having the following
 * properties:
 *
 * - The function is one-to-one (that is, f(x, y) can only equal
 *   f(x', y') if x = x' and y = y')
 *
 * - If x and y are selected at random, each bit of z has an equal
 *   probability of being 0 or 1.
 *
 * - If x and y are selected at random, any pair of distinct bits in z
 *   is uncorrelated.
 *
 * Bonus points to the solution that can be implemented in the
 * smallest amount of code (assuming a 32-bit CPU).
 *
 */


#include <glib/gtypes.h>

guint8 rotate(const guint8 x, const guint8 bits) {
  return (x << bits) + (x >> (8-bits));
}

guint32 __attribute__((const)) f(guint8 x, guint8 y) {
  // start by repeating x enough times to fill z
  guint32 z = x + (x << 8) + (x << 16) + (x << 24);
  // mask it 4 ways by rotating y
  guint32 mask = rotate(y, 1) +
    (rotate(y, 2) << 8) +
    (rotate(y, 3) << 16) +
    (rotate(y, 4) << 24);
  return z ^ mask;
}


#include <stdlib.h>
#include <stdio.h>

int main(int argc, char **argv) {
  guint8 x, y;
  guint32 z = 0;
  if (argc != 3) {
    printf("usage: %s x y\n", argv[0]);
    return 1;
  }
  x = atoi(argv[1]);
  y = atoi(argv[2]);
  z = f(x, y);
  printf("x=%u\ny=%u\nz=%u\n", x, y, z);
  return 0;
}