/* 格雷码与二进制的转换程序
* 本程序采用递推的方法进行推导,可以转换0~2147483647之间的数(1~31位)
* 推导方式如下(以三位格雷码为例):
* 序号 格雷码 格雷码实值 二进制码 二进制实值
* 0 000 0 000 0
* 1 001 1 001 1
* 2 011 3 010 2
* 3 010 2 011 3
* 4 110 6 100 4
* 5 111 7 101 5
* 6 101 5 110 6
* 7 100 4 111 7
* 由上面的数据可看出.如果,按照序号01327645的方式遍历格雷码.其编
* 码实值是按自然数顺序排列.反之,如果按此顺序遍历其二进制实值.则会发
* 现遍历过的数据的个数减一即为二进制码所对应格雷码的实值.再观察序号
* 顺序,我们会发现: 如果把二进制码分半,前半部分从前向后遍历,后半部分
* 从后向前遍历.如果分半部分可再分,则再将其分半.并按照前半部分从前向
* 后遍历(分解),后半部分从后向前遍历的方式遍历(分解).直到不可分.即可
* 实现按序号所描述顺序遍历二进制码.如果,按此顺序遍历二进制码,我们可
* 以很方便地在序列中找到所要的二进制码与其对应的格雷码.本思想可以很
* 方便地用递归实现.这样就实现了二进制到格雷码的转换.同样,格雷码到二
* 进制的转换,也可以用相同的方法推出.为了加快运算,我们跳过不必要的遍
* 历将递归改为递推.这样就实现了格雷码与二进制之间的快速转换.
* 此算法的时间复杂度约为O(n),n为要转换数据的BIT数.
* *****************************************************************
* 补充说明：
* 其它的转换方法还有
* 1、查表法（建立一个二进制与格雷码的对应表）
* 2、公式法（根据卡诺图建立一个二进制到格雷码的每一位的公式）
*/
//#define test
#include <stdio.h>
#ifdef test
#include <time.h>
#endif
/**
* 二进制转换成格雷码
* @param lStart lValue所在区间下界
* @param lEnd lValue所在区间上界
* @param lValue 要转换的二进制数的实值
* @return 返回格雷码对应的二进制数的实值
* @see g2b() g2b 格雷码转换二进制
* @see BtoG() BtoG 二进制转换格雷码
* @see GtoB() BtoG 格雷码转换二进制
* @author 黄毅
* @useage a=b2g(0,15,4); //取得4所对应格雷码的二进制值 结果a等于6
* @memo lValue的值必须在区间[lStart,lEnd]里,否则无法求得所求结果.相应地,如果区间越小,求得结
* 果所用的时间就越少.而且lStart,lEnd的值必须为2的N次方减1. 通常lStart为0.为了方便求得
* 其值,建议使用BtoG()函数来进行操作.不过这样会使计算时间加长到原来的120%~180%.
*/
unsigned long b2g(unsigned long lStart,unsigned long lEnd,unsigned long lValue)
{
unsigned long Start=lStart,End=lEnd,Temp=0,Counter=0;
bool Type=true;
while(Start<End)
{
Temp=(End+Start-1)>>1;
if (lValue<=Temp)
{
if(!Type)
Counter+=((End-Start+1)>>1);
End=Temp;
Type=true;
}
else
{
if(Type)
Counter+=((End-Start+1)>>1);
Start=++Temp;
Type=false;
}
}
return Counter;
}
/**
* 格雷码转换成二进制
* @param lStart lValue对应二进制数所在区间下界
* @param lEnd lValue对应二进制数所在区间上界
* @param lValue 要转换的格雷码的实值
* @return 返回二进制数对应的格雷码的实值
* @see b2g() b2g 二进制转换格雷码
* @see BtoG() BtoG 二进制转换格雷码
* @see GtoB() BtoG 格雷码转换二进制
* @author 黄毅
* @useage a=b2g(0,15,6); //取得6所对应二进制值的格雷码 结果a等于4
* @memo lValue对应二进制数的值必须在区间[lStart,lEnd]里,否则无法求得所求结果.相应地,如果区
* 间越小,求得结果所用的时间就越少.而且lStart,lEnd的值必须为2的N次方减1. 通常lStart为0.
* 为了方便求得其值,建议使用GtoB()函数来进行操作.但会使计算时间加长到原来的105%~140%.
*/
unsigned long g2b(unsigned long lStart,unsigned long lEnd,unsigned long lValue)
{
unsigned long Start=lStart,End=lEnd,Counter=0,Temp=0;
bool Type=true;
while(Start<End)
{
Temp=Counter+((End-Start+1)>>1);
if(Type^(lValue<Temp))
{
if(Type) Counter=Temp;
Start=(Start+End+1)>>1;
Type=false;
}
else
{
if(!Type) Counter=Temp;
End=(Start+End-1)>>1;
Type=true;
}
}
return Start;
}
//b2g外壳程序,用来算lStart,lEnd;
long BtoG(unsigned long lValue)
{
register unsigned long lV=lValue,lMax=1;
while (lV>0)
{
lV>>=1;
lMax<<=1;
}
if (lMax==0) return -1;
return b2g(0,--lMax,lValue);
}
//g2b外壳程序
long GtoB(unsigned long lValue)
{
register unsigned long lV=lValue,lMax=1;
while (lV>0)
{
lV>>=1;
lMax<<=1;
}
if (lMax==0) return -1;
return g2b(0,--lMax,lValue);
}
main()
{
long input=0;
#ifdef test
//程序测试部分
clock_t cStart,cEnd;
unsigned long dTime;
cStart=clock();
for (input=0;input<9999999;input++)
BtoG(32768);
cEnd=clock();
dTime=(cEnd-cStart);
printf("BtoG: %ld / %ld\n",dTime,CLOCKS_PER_SEC);
//------------------------------------------------------
cStart=clock();
for (input=0;input<9999999;input++)
b2g(0,65535,32768);
cEnd=clock();
dTime=(cEnd-cStart);
printf("b2g: %ld / %ld\n",dTime,CLOCKS_PER_SEC);
//------------------------------------------------------
cStart=clock();
for (input=0;input<9999999;input++)
GtoB(32768);
cEnd=clock();
dTime=(cEnd-cStart);
printf("GtoB: %ld / %ld\n",dTime,CLOCKS_PER_SEC);
//------------------------------------------------------
cStart=clock();
for (input=0;input<9999999;input++)
g2b(0,65535,32768);
cEnd=clock();
dTime=(cEnd-cStart);
printf("g2b: %ld / %ld\n",dTime,CLOCKS_PER_SEC);
#else
//程序演试部分
printf("Input(HEX):");
scanf("%x",&input);
while (input!=-1)
{
printf("------BtoG------\nBinary:%08Xh\nGray :%08Xh\n------GtoB------\nGray :%08Xh\nBinary:%08Xh\n----------------\n",input,BtoG(input),input,GtoB(input));
printf("Input(HEX):");
scanf("%x",&input);
}
#endif
}
