当前位置： 面试刷题>> 格雷编码 (经典算法题500道)
### 题目描述补充
格雷编码（Gray Code），也称反射二进制码或循环二进制码，是一种二进制数的编码方式，其中两个连续的数值仅有一个位数的差异。格雷码在数字系统错误检测、通信、密码学等领域中有重要应用。
给定一个非负整数 `n`，代表需要生成的格雷码的位数，请编写一个算法来生成长度为 `2^n` 的格雷码序列。格雷码序列必须按从小到大的顺序排列（即，从 `0` 开始，到 `2^n - 1` 结束）。
### 示例
对于 `n = 2`，格雷码序列为 `[0, 1, 3, 2]`。
对于 `n = 3`，格雷码序列为 `[0, 1, 3, 2, 6, 7, 5, 4]`。
### PHP 示例代码
```php
function grayCode($n) {
$result = [0];
$num = 1;
for ($i = 0; $i < $n; $i++) {
$num = $num << 1; // 左移一位，相当于乘以2
for ($j = $num - 1; $j >= 0; $j--) {
$result[] = $result[$j] | $num; // 或运算，相当于当前元素+2^i
}
}
return $result;
}
// 测试
echo implode(', ', grayCode(2)); // 输出: 0, 1, 3, 2
echo "\n";
echo implode(', ', grayCode(3)); // 输出: 0, 1, 3, 2, 6, 7, 5, 4
```
### Python 示例代码
```python
def grayCode(n):
if n == 0:
return [0]
prev = grayCode(n - 1)
curr = [x + (1 << (n - 1)) for x in reversed(prev)]
return prev + curr
# 测试
print([str(x) for x in grayCode(2)]) # 输出: ['0', '1', '3', '2']
print([str(x) for x in grayCode(3)]) # 输出: ['0', '1', '3', '2', '6', '7', '5', '4']
```
### JavaScript 示例代码
```javascript
function grayCode(n) {
if (n === 0) return [0];
const prev = grayCode(n - 1);
const curr = prev.reverse().map(x => x | (1 << (n - 1)));
return prev.concat(curr);
}
// 测试
console.log(grayCode(2).toString()); // 输出: "0,1,3,2"
console.log(grayCode(3).toString()); // 输出: "0,1,3,2,6,7,5,4"
```
### 码小课网站分享
码小课网站中有更多关于算法和数据结构的详细解析、面试题讲解以及实战案例分享，欢迎大家访问学习，提升编程技能。