0089. 格雷编码 #
- 标签:位运算、数学、回溯
- 难度:中等
题目大意 #
- 格雷编码:二进制数字系统,两个连续的数值仅有一个位数的差异。
现在给定一个代表格雷编码总位数的非负整数 n
,打印对应的格雷编码序列。只需要返回其中一个答案即可。
解题思路 #
-
格雷编码生成规则:以二进制值为
0
的格雷编码作为第0
项,第一次改变最右边的数位,第二次改变从右边数第一个为1
的数位左边的数位,第三次跟第一次一样,改变最右边的数位,第四次跟第二次一样,改变从右边数第一个为1
的数位左边的数位。此后,第五、六次,第七、八次 … 都跟第一二次一样反复进行,直到生成 $2^n$ 个格雷编码。 -
也可以直接利用二进制转换为格雷编码公式:
代码 #
|
|