package main

// generate gray code directly
func grayCodeOld(n int) []int {
	res := make([]int, 1<<uint(n))
	code := 0
	for i := 1; i < 1<<uint(n); i++ {
		if i&1 == 1 {
			code ^= 1
		} else {
			base := 1
			for ; base&code == 0; base <<= 1 {
			}
			code ^= base << 1
		}
		res[i] = code

	}
	return res
}

func grayCode(n int) (res []int) {
	m := uint(n)
	// binary to gray code: G(n) = (B(n)/2) xor B(n)
	// form wikipedia
	for i := 0; i < 1<<m; i++ {
		res = append(res, i)
		res[i] ^= res[i] >> 1
	}
	return
}

/* func main() {
	fmt.Println(grayCode(2))
} */