Skip to content

Instantly share code, notes, and snippets.

@dustMason
Last active December 31, 2019 07:10
Show Gist options
  • Save dustMason/e746693ec3db5483ae81f63835d3a58b to your computer and use it in GitHub Desktop.
Save dustMason/e746693ec3db5483ae81f63835d3a58b to your computer and use it in GitHub Desktop.
Gray Codes
package main
import (
"fmt"
"math"
)
func main() {
fmt.Printf("%010b", gray(10))
}
// from https://en.wikipedia.org/wiki/Gray_code
// "... an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit)"
func gray(n int) []int {
if n == 0 {
return []int{}
}
if n == 1 {
return []int{0b0, 0b1}
}
prev := gray(n-1)
left, right := make([]int, pow2(n-1)), make([]int, pow2(n-1))
for i, c := range prev {
left[i] = c << 1
right[len(right)-i-1] = left[i] | 0b1
}
return append(left, right...)
}
func pow2(n int) int {
return int(math.Exp2(float64(n)))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment