Skip to content

Instantly share code, notes, and snippets.

@sparr

sparr/gist:9875737

Last active August 29, 2015 13:57
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save sparr/9875737 to your computer and use it in GitHub Desktop.
Save sparr/9875737 to your computer and use it in GitHub Desktop.
Download ZIP
one bitflip per increment
Raw
gistfile1.txt
A binary numerical encoding wherein sequential integers only differ from each other
by a single bit. I'm calling this "one bitflip per increment" encoding. This is my
proposal to a question posed on the Artisan's Asylum discussion mailing list, with
the topic being looking for numerical encodings that are friendly to possibly-genetic
algorithmic solutions to problems where only bitwise operations are used, and thus
finding a solution of "10000" from "01111" is unlikely, while finding "10000" from
"10001" is easy. The nth lsbit of the mask flips every 2^n increments.
bin | obpi | mask
0000 | 0000 | 0000
0001 | 0001 | 0000
0010 | 0011 | 0001
0011 | 0010 | 0001
0100 | 0110 | 0010
0101 | 0111 | 0010
0110 | 0101 | 0011
0111 | 0100 | 0011
1000 | 1100 | 0100
1001 | 1101 | 0100
1010 | 1111 | 0101
1011 | 1110 | 0101
1100 | 1010 | 0110
1101 | 1011 | 0110
1110 | 1001 | 0111
1111 | 1000 | 0111
10000 | 11000 | 01000
10001 | 11001 | 01000
10010 | 11011 | 01001
10011 | 11010 | 01001
10100 | 11110 | 01010
10101 | 11111 | 01010
10110 | 11101 | 01011
10111 | 11100 | 01011
etc
@sparr
Copy link
Author

sparr commented Mar 31, 2014

Discovered a bit later that I've basically reinvented Gray Codes, which are about 65 years old.

gray = binary ^ (binary >> 1)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment