注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex89 Gray Code  

2015-05-15 22:10:44|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
格雷码的问题,看下变换过程就行了。

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2
参考:http://baike.haosou.com/doc/3793519-3984486.html
见c代码

/*
*格雷码是指 n个bit 连续出现的数字只有一位不相同
*例如 n =2;
* 00 -> 01 -> 11 -> 10
* http://baike.haosou.com/doc/3793519-3984486.html
* 一般的,普通二进制码与格雷码可以按以下方法互相转换:

二进制码->格雷码(编码):从最右边一位起,依次将每一位与左边一位异或(XOR),
作为对应格雷码该位的值,最左边一位不变(相当于左边是0);

格雷码-〉二进制码(解码):从左边第二位起,将每位与左边一位解码后的值异或,
作为该位解码后的值(最左边一位依然不变)。
*/
int* grayCode(int n, int* returnSize) {
//if (n <= 0)
//return NULL;
int len = pow(2, n); //计算生成的序列的长度
int* result = (int*)malloc(len*sizeof(int));
int i, j;
int index1, index2,mark1,mark2;
//int standard = (len-1)>>1;
int temp;
//printf("%d \n", standard);
for (i = 0; i < len; i++)
{
temp = 0; //用于存储最后的结果
index1 = 1;
index2 = 2;
for (j = 0; j < n; j++)
{
mark1 = index1&i; //取第j个位置 比如,0101,取第二位数字就是 0100
mark2 = index2&i; //取第j+1个位置
mark2 = mark2 >> 1;//右移一位 与mark1对齐
temp = temp|(mark1^mark2); //mark1与mark2 与一下 加到temp上

index2 = index2 << 1; //index2 左移一位
index1 = index1 << 1;
}
//printf("%d \n",temp);
result[i] = temp;
}
returnSize[0] = len;
return result;
}



  评论这张
 
阅读(10)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017