题目大意
求格雷码
解题思路
格雷码维基百科：
https://zh.wikipedia.org/wiki/%E6%A0%BC%E9%9B%B7%E7%A0%81
以二进制为0值的格雷码为第零项，第一项改变最右边的位元，第二项改变右起第一个为1的位元的左边位元，第三、四项方法同第一、二项，如此反复，即可排列出n个位元的格雷码。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution(object):
def grayCode(self, n):
"""
:type n: int
:rtype: List[int]
"""
res = []
size = 1 << n # 若n=4，左移4位，从1到了10000，就是16（高位丢弃，低位补0）
print bin(size)
for i in range(size):
# print i, bin(i), bin((i >> 1)), bin((i >> 1) ^ i) # 最后求异或
res.append((i >> 1) ^ i)
return res
|
看输出理解：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 0b10000
0 0b0 0b0 0b0
1 0b1 0b0 0b1
2 0b10 0b1 0b11
3 0b11 0b1 0b10
4 0b100 0b10 0b110
5 0b101 0b10 0b111
6 0b110 0b11 0b101
7 0b111 0b11 0b100
8 0b1000 0b100 0b1100
9 0b1001 0b100 0b1101
10 0b1010 0b101 0b1111
11 0b1011 0b101 0b1110
12 0b1100 0b110 0b1010
13 0b1101 0b110 0b1011
14 0b1110 0b111 0b1001
15 0b1111 0b111 0b1000
|
总结
位操作符复习：
http://www.runoob.com/python/python-operators.html