/******** Problem 6--Hamming It Up ************************************
 This was another easy problem provided you knew C's built-in bitwise
 operators.
 **********************************************************************/

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

#define MIN(a,b) ((a)<(b)?(a):(b))

int main (int argc, char **argv);
static int hamming (int a, int b);
static int minhamming (int *code, int len);

FILE *in, *out;

/**** main ************************************************************
 This program continally reads in a line of integers.  The first integer
 tells us the number of integers that will follow.  We compute and
 print out the Hamming distance for these following integers.
 **********************************************************************/

int main (int argc, char **argv) {

  int code[20], len, /* the set of integers and their length */
      cs=0,            /* the case number */
      i;             /* loop iterator */

 in = fopen ("prob6.in","r");    /* redirect input and output */
 out = fopen ("prob6.out","w");
 while (1) {
  fscanf (in,"%d",&len); 
              /* read in the length and stop if length is zero */
  if (len==0) break;
  for (i=0;i<len;i++) /* read in the line of integers */
   fscanf (in,"%d",&code[i]);
                      /* Compute and print the hamming distance */
  fprintf (out,"Case %d.  Hamming distance = %d.\n",++cs,
           minhamming(code,len));
 }
 fclose (in);   /* Close our files */
 fclose (out);
 return EXIT_SUCCESS;
}

/****** hamming *******************************************************
 hamming accepts two integers and prints out the hamming distance
 between the two integers.  It uses C's bitwise exclusive-or operator.
 **********************************************************************/

static int hamming (int a, int b) {

  unsigned int c;    /* The bitwise difference of a and b */
  int ct;            /* The number of bits in the difference 
                        (to be returned) */

  /* bitwise exclusive or operator: ^ */       
 for (c=a^b,ct=0;c>0;ct+=c%2,c>>=1); 
                 /* loop until we run out of bits to check */
                 /* if rightmost bit is one, increment our count */
                 /* right shift */
 return ct;
}

/***** minhamming *****************************************************
 minhamming accepts an array of integers and its length and returns
 the minimum hamming distance of any pair of integers in the list.
 It simply uses a nested loop to hit all of the combinations.
 **********************************************************************/

static int minhamming (int *code, int len) {

  int mind,   /* The minimum hamming distance (that will be returned) */
      i, j,   /* loop variables */
      h;      /* hamming distance for a pair of nodes */

 mind = 32;  /* 32 is the limit given in the problem description */
             /* i iterates from 0 to len-2 */
 for (i=0;i<len-1;i++)
                  /* j iterates from i+1 to len-1 */
  for (j=i+1;j<len;j++) {
   h = hamming (code[i],code[j]);
   mind = MIN (mind, h);  /* if this code is smaller, replace it */
  }
 return mind;
}