Binary Circles

A binary circle is a series of 2^n binary digits
that represent all the possible combinations of
n-bit numbers. Amazingly it only takes 2^n bits
to represent all 2^n combinations of n-bit numbers.

Lets take for instance all the possible 2-bit
values:
  00 - 0
  01 - 1
  10 - 2
  11 - 3

The trick is to arrange 4 bits in a circle
such that as you go around the circle all 4
combinations of 2-bit values are represented.

  0
1   0
  1

If you start at the 0 on top of the circle
and continue around clock-wise using 2 bits
at a time, you can see
00, 01, 11, and 10.

Now for 8 bits in a circle:

        0
   1         0
 
 1             0
 
   1         1
        0
        
Starting at the 0 on top and continuing
around clock-wise 3 bits at a time,
you get:
000, 001, 010, 101, 011, 111, 110, 100

Which happen to represent all 8 (2^3) combinations
of 3 bit numbers.

This also works for 1-bit numbers, but it doesn't
look much like a circle:

   0

   1

revealing both 1-bit numbers: 0 and 1

As a matter of convenience I have come up with
a way to describe these patterns in hexidecimal
notation.  By unwrapping the circles above
and simply converting to hexidecimal you get:

n  2^n    binary   hexidecimal
-  ---  --------   -----------
1   2         01 = 1
2   4       0011 = 3
3   8   00010111 = 17

You might notice that if you start at some other point
in the circle you will get a different series of digits
that could be converted to a different hexidecimal value.
One challenge is to find THE pattern of digits that
converts to the smallest hexidecimal value.  You may already
start seeing a pattern form: The smallest binary circle
will always start with n zeroes and end with n ones.

Let's take a look at the binary circle where n = 4:

You can create a table like the one below
and by using a process of elimination fill in
the blanks.

Let X be the hex representation of 4 bits.
The "X<<0" column is what would happen if you
dropped the leftmost bit and added a zero on
the right.  The "X<<1" column is what would
happen if you dropped the leftmost bit and
added a one on the right. Let X' be the
hex representation of the 4 bit pattern that
will follow X in the series.

X X'  X X'  X<<0  X<<1
0-?   8-?     0     1 
1-?   9-?     2     3 
2-?   A-?     4     5 
3-?   B-?     6     7 
4-?   C-?     8     9 
5-?   D-?     A     B 
6-?   E-?     C     D 
7-?   F-?     E     F 
                       
Since you don't want to repeat any 4 bit pattern,
0 will never follow 0 and F will never follow F.
This allows you to fill in four of the blanks:
0-1, 8-0, F-E, 7-F

Next, abiding by the "smallest possible value" rule,
since the 4 zeroes must be at the beginning and the 4 ones
must be at the end (and the ends join to make the circle):
E-C, 6-D, and C-8, 4-9 must also be paired up.

Let's try a zero after the 1 (the sooner we place zeroes,
the smaller the overall number will be):
1-2, 9-3

Let's try squeezing another zero in after the 2:
2-4, A-5

Since A goes to 5, you can't let 5 go to A, so:
5-B, D-A

If 3 goes to 7 then
B-6-D-A-5-B and the circle gets short-circuited.

If 3 goes to 6 then
B-7-F-E-C-8-0-1-2-4-9-3-6-D-A-5-B

Voila! We have our circle:
0-1-2-4-9-3-6-D-A-5-B-7-F-E-C-8-0

X X'  X X'  X<<0  X<<1 
0-1   8-0     0     1  s
1-2   9-3     2     3  
2-4   A-5     4     5  
3-6   B-7     6     7  
4-9   C-8     8     9  s
5-B   D-A     A     B  s
6-D   E-C     C     D  s
7-F   F-E     E     F  s

                0
         1             0
     
     1                     0
     
   1                         0
     
  1                           1
     
   0                         0
     
     1                     0
         0             1
                1


Or in hex notation:
09AF or just 9AF

n  2^n            binary   hexidecimal
-  ---  ----------------   -----------
1   2                 01 = 1
2   4               0011 = 3
3   8           00010111 = 17
4  16   0000100110101111 = 9AF
5  32   (see below)      = 4674ADF
6  64   (see below)      = 218E4B3D14D5DBF

At this point if we want to find bigger binary
circles, it might be wise to create a computer
program to step through a table like the one
we created above.

n=5 from a computer program:
2^n = 32
binary = 00000100011001110100101011011111
   hex = 04674ADF

X  X'  X  X'  X     X         X'    X'
00-01  16-00  00000 10000 --> 00000 00001 s
01-02  17-03  00001 10001 --> 00010 00011
02-04  18-05  00010 10010 --> 00100 00101
03-06  19-07  00011 10011 --> 00110 00111
04-08  20-09  00100 10100 --> 01000 01001
05-10  21-11  00101 10101 --> 01010 01011
06-12  22-13  00110 10110 --> 01100 01101
07-14  23-15  00111 10111 --> 01110 01111
08-17  24-16  01000 11000 --> 10000 10001 s
09-18  25-19  01001 11001 --> 10010 10011
10-21  26-20  01010 11010 --> 10100 10101 s
11-22  27-23  01011 11011 --> 10110 10111
12-25  28-24  01100 11100 --> 11000 11001 s
13-27  29-26  01101 11101 --> 11010 11011 s
14-29  30-28  01110 11110 --> 11100 11101 s
15-31  31-30  01111 11111 --> 11110 11111 s

n=6 from a computer program:
2^n = 64
binary = 0000001000011000111001001011001111010001010011010101110110111111
   hex = 0218E4B3D14D5DBF

X  X'  X  X'  X      X          X'     X'
00-01  32-00  000000 100000 --> 000000 000001 s
01-02  33-03  000001 100001 --> 000010 000011
02-04  34-05  000010 100010 --> 000100 000101
03-06  35-07  000011 100011 --> 000110 000111
04-08  36-09  000100 100100 --> 001000 001001
05-10  37-11  000101 100101 --> 001010 001011
06-12  38-13  000110 100110 --> 001100 001101
07-14  39-15  000111 100111 --> 001110 001111
08-16  40-17  001000 101000 --> 010000 010001
09-18  41-19  001001 101001 --> 010010 010011
10-20  42-21  001010 101010 --> 010100 010101
11-22  43-23  001011 101011 --> 010110 010111
12-24  44-25  001100 101100 --> 011000 011001
13-26  45-27  001101 101101 --> 011010 011011
14-28  46-29  001110 101110 --> 011100 011101
15-30  47-31  001111 101111 --> 011110 011111
16-33  48-32  010000 110000 --> 100000 100001 s
17-34  49-35  010001 110001 --> 100010 100011
18-37  50-36  010010 110010 --> 100100 100101 s
19-38  51-39  010011 110011 --> 100110 100111
20-41  52-40  010100 110100 --> 101000 101001 s
21-43  53-42  010101 110101 --> 101010 101011 s
22-44  54-45  010110 110110 --> 101100 101101
23-46  55-47  010111 110111 --> 101110 101111
24-49  56-48  011000 111000 --> 110000 110001 s
25-51  57-50  011001 111001 --> 110010 110011 s
26-53  58-52  011010 111010 --> 110100 110101 s
27-55  59-54  011011 111011 --> 110110 110111 s
28-57  60-56  011100 111100 --> 111000 111001 s
29-59  61-58  011101 111101 --> 111010 111011 s
30-61  62-60  011110 111110 --> 111100 111101 s
31-63  63-62  011111 111111 --> 111110 111111 s

Binary circles can be of practical use in computer programs
when you need to convert between binary patterns and alphabets:

These are code fragments in perl:

---------------

#
# Using a 64-bit binary circle to convert between base64 and binary
# Note: the first five 0's are repeated at the end of $bits.
#
$bits = "000000100001100011100100101100111101000101001101010111011011111100000";
$b64  = "ABCEIQhDGMYxjHOc5ykJSlLWsZznPe960oRiFKUpTmNa1qVrXud72tb3vf/+84wg";

sub bits_to_b64 {
   my ($pattern) = @_;
   return substr($b64,index($bits,$pattern),1);
}

sub b64_to_bits {
   my ($char) = @_;
   return substr($bits,index($b64,$char),6);
}

---------------

#
# Using a 16-bit binary circle to convert between hex characters and binary
# Note: the first three 0's are repeated at the end of $bits.
#
$bits = "0000100110101111000";
$hex  = "0124936DA5B7FEC8";

sub bits_to_hex {
   my ($pattern) = @_;
   return substr($hex,index($bits,$pattern),1);
}

sub hex_to_bits {
   my ($char) = @_;
   return substr($bits,index($hex,$char),6);
}