字符串逆反序输出算法

题目拆分：输入模块操作要求 求解思路p.s.:其他逆序方案1、传统的逐位取值移位2、原数与1位与，再与新数位或，新数左移腾空间，原数右移去旧值3、分治的方法 五一放假了，小伙伴们都去玩耍了，每个小伙伴均被分配一个编号，编号格式为一组16进制表示的数字串，如123456789abc，表示由0x12/0x34/0x56/0x78/0x9a/0xbc组成的6个数字串。 伙伴编号是通过一种称为逆反序输出的算法求得，算法原理是对于一串输入，先按bit逆向反转，再对每个bit取反输出。 逆向反转的意思是将输入的第1位移到最后1位，第2位移到倒数第2位，依次类推。 如对于16进制表示的输入数据：123456789abc，按二进制表示为： 000100100011010001010110011110001001101010111100，先按bit反转，得到： 001111010101100100011110011010100010110001001000，再按bit取反，得到： 110000101010011011100001100101011101001110110111，最后，换算成16进制格式表示输出： c2a6e195d3b7 注：一个字节的16进制格式表示总是由2个字符组成，即使高4位为0，且字母部分使用小写表示。转换完的数字串长度总是与转换前的一致。 要求设计这样一个算法： 输入 第一行为一个数字，表示用例数N，从第二行开始，每行表示一个测试用例，内含使用16进制格式表示的输入数据（最大长度为100字节）。 输出 输出N行，每一行对应一个用例的逆反序运算结果，使用16进制格式表示。

题目拆分：

输入模块

键盘输入一组字符：0 ~ 9， a ~ f，来表示。 例: 键入“123456789abc”，共12个字节， 表示0x12/0x34/0x56/0x78/0x9a/0xbc，6个数字

操作要求

逆反序输出算法 算法原理是对于一串输入，先按bit逆向反转，再对每个bit取反输出。

例： 12/ 34/ 56/ 78/ 9a/ bc 16进制表示： 0x12/ 0x34/ 0x56/ 0x78/ 0x9a/ 0xbc 2进制表示： 00010010/ 00110100/ 01010110/ 01111000/ 10011010/ 10111100 按bit逆序： 00111101/ 01011001/ 00011110/ 01101010/ 00101100/ 01001000 按bit取反： 11000010/ 10100110/ 11100001/ 10010101/ 11010011/ 10110111 16进制表示： c2/ a6/ e1/ 95/ d3/ b7

一个字节的16进制格式表示总是由2个字符组成，即使高4位为0，且字母部分使用小写表示。转换完的数字串长度总是与转换前的一致。

求解思路

首先考虑用什么方式来接收输入信息”123456789abc”。按题意应该是要按12，34，56，78，9a，bc这样接收，但一时想不出之后要如何处理。 于是就想按1，2，……，b，c这样先逐个字符的接收处理，并为了防止移位时符号位的干扰，存储变量皆定义为无符号字符类型。

按1，2，……，b，c接收到的字符以16进制显示如0x01, 0x02, ……, 0x0b, 0x0c。此处对 ’0’ ~ ’9’ 进行了减 ’0’ 操作，对 ‘a’ ~ ’f’ 进行了减 ’a’ 加 10 的操作。

因为对整体按bit进行逆序排列 等价于 对各字节按bit进行逆序排列后再对各字节按字节进行逆序排列。

此处上网查阅到了一种跟巧妙地按bit逆序的方法： 链接：https://blog.csdn.net/jakee304/article/details/2152655.

#define exchange(x,y) / { (x) ^= (y); / (y) ^= (x); / (x) ^= (y); / } unsigned char fun1(unsigned char c) { union { unsigned char c; struct { unsigned char bit0:1; unsigned char bit1:1; unsigned char bit2:1; unsigned char bit3:1; unsigned char bit4:1; unsigned char bit5:1; unsigned char bit6:1; unsigned char bit7:1; } bchar; } ubc; ubc.c = c; exchange(ubc.bchar.bit0, ubc.bchar.bit7); exchange(ubc.bchar.bit1, ubc.bchar.bit6); exchange(ubc.bchar.bit2, ubc.bchar.bit5); exchange(ubc.bchar.bit3, ubc.bchar.bit4); return ubc.c; }

其设计一个共用体 uc: 包含一个无符号字节变量 c 和一个结构体sc， 其中结构体中包含8个取位域为1的无符号字符变量。

这种方法很巧妙地利用了共用体中各变量内存共用的特性，以及位域后结构体中各变量的对齐性质。 其实现了共用体 uc 中无符号字节变量 c 各个bit与结构体 sc 中的各个变量相对应，然后将对应bit表示的结构体中的变量值进行交换。

交换后的16进制显示效果为 0x80, 0x40, ……, 0xd0, 0x30 按位取反后的16进制显示效果为 0x7f, 0xbf, ……, 0x2f, 0xcf 右移4位保留高四位值为：0x07, 0x0b, ……, 0x02, 0x0c 在对各字节按字节进行逆序排列，此处记录输出次数为id(方便日后输出)， 得到：0x0c, 0x02, ……, 0x0b, 0x07

显示阶段仅显示16进制的低四位(%hhx)，最终输出：c2a6e195d3b7。

#include <stdio.h> /** 用于元素交换 */ #define SWAP(x,y)\ {\ (x) ^= (y);\ (y) ^= (x);\ (x) ^= (y);\ } typedef unsigned char u8; /** 定义在字节内按bit逆序排列的方法 */ u8 fun1(u8 c) { /** 创建共共用体 */ union { /** 字节c与结构体变量sc共用8bit内存空间 */ u8 c; /** 8个位域后的变量恰好可以表示一个字节的8位 */ struct { u8 bit0:1; u8 bit1:1; u8 bit2:1; u8 bit3:1; u8 bit4:1; u8 bit5:1; u8 bit6:1; u8 bit7:1; } sc; } uc; /** 对字节c进行bit逆序排列 */ uc.c = c; SWAP(uc.sc.bit0, uc.sc.bit7); SWAP(uc.sc.bit1, uc.sc.bit6); SWAP(uc.sc.bit2, uc.sc.bit5); SWAP(uc.sc.bit3, uc.sc.bit4); return uc.c; } int main(){ u8 c; // 存储输入字节 u8 cnew; // 存储中间操作结果 u8 buff[100] = {0}; // 存储各字节的操作结果 int id = 0; // 用来记录输出字节的数量 while((c = getchar())!='\n'){ /** 将字节转化为所表示的16进制值 */ if(c>='0' && c<='9'){ c -= '0'; }else if(c>='a' && c<='f'){ c = 10+c-'a'; } // 原先的处理方法，多了一步位与运算 //cnew = fun1(c)>>4; //cnew = ~cnew&(0x0f); /** 字节内逆序以及取反 */ cnew = ~fun1(c); /** 右移仅保留高4位 */ cnew = cnew>>4; /** 结果存入 */ buff[id++] = cnew; } /** 字节间的逆序排列 */ int i=0; int j=id-1; while(i<j){ SWAP(buff[i],buff[j]); i++; j--; } /** 输出结果 */ for(int i=0; i<id; i++){ printf("%hhx", buff[i]); } /** 实际输出字节数 */ printf("\n%d\n", id); return 0; }

其实际输出了12个仅显示低位信息的字节，并非要求的6个字节。

改进： 再回到如何一次处理2个字节，以及字节合并的问题： 事先将第一个输入的字节temph的16进制表示向左移动4位，再加上第二个输入的字节templ。后面操作基本不变。

#include <stdio.h> /** 用于元素交换 */ #define SWAP(x,y)\ {\ (x) ^= (y);\ (y) ^= (x);\ (x) ^= (y);\ } /** 较demo001进行了封装处理 */ /** 用于将字节转化为所表示的16进制值 */ #define TRANS(x)\ {\ if((x)>='0' && (x)<='9'){\ (x) -= '0';\ }else if((x)>='a' && (x)<='f'){\ (x) = 10+(x)-'a';\ }\ } typedef unsigned char u8; /** 定义在字节内按bit逆序排列的方法 */ u8 fun1(u8 c) { /** 创建共共用体 */ union { /** 字节c与结构体变量sc共用8bit内存空间 */ u8 c; /** 8个位域后的变量恰好可以表示一个字节的8位 */ struct { u8 bit0:1; u8 bit1:1; u8 bit2:1; u8 bit3:1; u8 bit4:1; u8 bit5:1; u8 bit6:1; u8 bit7:1; } sc; } uc; /** 对字节c进行bit逆序排列 */ uc.c = c; SWAP(uc.sc.bit0, uc.sc.bit7); SWAP(uc.sc.bit1, uc.sc.bit6); SWAP(uc.sc.bit2, uc.sc.bit5); SWAP(uc.sc.bit3, uc.sc.bit4); return uc.c; } int main(){ u8 temph; //实际的高4位 u8 templ; //实际的低4位 u8 cnew; //中间处理结果保存 u8 buff[100] = {0}; // 存储各字节的操作结果 int id = 0; // 用来记录输出字节的数量 while((temph = getchar())!='\n'){ /** 默认输入成对出现 */ /** 继续捕获低4位地址 */ templ = getchar(); /** 分别进行实际16进制转化操作 */ TRANS(temph); TRANS(templ); /** 高低字节合并 */ cnew = (temph<<4) + templ; /** 字节内取逆、求反 */ cnew = ~fun1(cnew); /** 结果存入 */ buff[id++] = cnew; } /** 字节间的逆序排列 */ int i=0; int j=id-1; while(i<j){ SWAP(buff[i],buff[j]); i++; j--; } /** 输出结果 */ for(int i=0; i<id; i++){ printf("%hhx", buff[i]); } /** 实际输出字节数 */ printf("\n%d\n", id); return 0; }

p.s.:其他逆序方案

参考自：https://blog.csdn.net/jakee304/article/details/2152655.

1、传统的逐位取值移位

unsigned char fun2(unsigned char c) { int i = 7; // 取位字符 unsigned char tmp = 0x01; // 逆序后的存储字节 unsigned char newc = 0x00; // 低4位的取值与移位 // 第0位->第1位，左移7位 // 第1位->第6位，左移5位 // 第2位->第5位，左移3位 // 第3位->第4位，左移1位 for ( ; i > 3; i--) { // 位或操作进行合并 newc |= ((c & tmp) << (i - (8 - i -1))); tmp <<= 1; } // 高4位的取值与移位，基本同上 for ( ; i >=0; i--) { newc |= ((c & tmp) >> ((8 - i -1) - i)); tmp <<= 1; } return newc; }

2、原数与1位与，再与新数位或，新数左移腾空间，原数右移去旧值

unsigned char fun3(unsigned char c) { int i; unsigned char newc = 0x00; for (i = 0; i < 7; i++) { newc |= (c & 1); newc <<= 1; c >>= 1; } return newc; }

举例： 原数10101010，新数00000000 原数与1位与 10101010 & 00000001 = 00000000 再与新数位或 00000000 & 00000000 = = 00000000 新数左移腾空间： 00000000 原数右移去旧值：01010101

3、分治的方法

unsigned char fun4(unsigned char c) { // 首先1位1位的换 c = (c & 0xaa) >> 1 | (c & 0x55) << 1; // 接着2位2位的换 c = (c & 0xcc) >> 2 | (c & 0x33) << 2; // 最后4位4位的换 c = (c & 0xf0) >> 4 | (c & 0x0f) << 4; return c; }