89.go 580 B

123456789101112131415161718192021222324252627282930313233343536373839
  1. package main
  2. import (
  3. "fmt"
  4. )
  5. // generate gray code directly
  6. func grayCodeOld(n int) []int {
  7. res := make([]int, 1<<uint(n))
  8. code := 0
  9. for i := 1; i < 1<<uint(n); i++ {
  10. if i&1 == 1 {
  11. code ^= 1
  12. } else {
  13. base := 1
  14. for ; base&code == 0; base <<= 1 {
  15. }
  16. code ^= base << 1
  17. }
  18. res[i] = code
  19. }
  20. return res
  21. }
  22. func grayCode(n int) (res []int) {
  23. m := uint(n)
  24. // binary to gray code: G(n) = (B(n)/2) xor B(n)
  25. // form wikipedia
  26. for i := 0; i < 1<<m; i++ {
  27. res = append(res, i)
  28. res[i] ^= res[i] >> 1
  29. }
  30. return
  31. }
  32. func main() {
  33. fmt.Println(grayCode(2))
  34. }