笔试题–反转一个字节

这道题很古老了，可别将它和大端转小端混淆了，所谓大端和小端指的是字节序，而这里反转一个字节说的是位序，算法更是不胜枚举，说实话都能达到目的，剩余的就是看看谁的效率更高了，基本上这是一个最难的问题，高手不是能写出最美丽的程序而是能写出既美丽同时效率又是最高的程序，如果一个人写的程序很美丽，很直观，只能说明该程序员对语言掌握的很好，但是语言毕竟只是工具，真正做事的是计算机，只有对计算机很了解，才能写出效率最高的程序，正如文学家的文笔很多不如花季少女，但是花季少女永远也超越不了时代。

不管什么样的程序，落实到底层的cpu都是那几样，尽量不要使用跳转，因为会清空流水线，相比之下，跳转的危害在x86机器上intel比AMD更甚，因为后者的流水线更浅；充分利用超标量cpu的超标量特性，也就是尽量使相邻指令不要关联，这样可以乱序执行，乱序执行就是将指令发射到不同的流水线序列；彻底理解cpu的HT特性，HT不一定会更好，因为它们毕竟是要共享一套算术单元，有时切换的开销会抵消对空闲周期的弥补，总的看来，cpu类型的程序应该避免使用HT，映射到进程/线程模型，并不是线程越多越好，当线程太少，不能利用多cpu特性，并且可能会使cpu闲置，但是太多的话又会引入切换/保存上下文开销，因此线程的数量和cpu数量相等或者比cpu数量大1个或者2个最好，因为强制和cpu数量相等会加大操作系统的运行开销，并且万一线程陷入IO没有替补，因此Windows的IO完成端口就设计的特别好，windows内核会限制完成端口上的活跃线程和创建时传入的参数一致，但是我并不赞成这种策略在内核实现，因此机制和策略严格分离的unix就没有这么做，你完全可以在用户空间通过cpu绑定和线程数量限制来调优；要尽可能的利用cpu的L1/L2 cache，理想情况就是，静态数据在cache中，该线程永不换出，cache永不刷新，但是这仅仅是一种理想，因此就要在理想和现实之间折中，将静态数据减少，既然不能将cache归为己有，那么也没有必要为止付出太多空间开销。

在上一段的指导下，高效的算法应该是很少的跳转，也就是很少的判断，不多不少的静态数据，该算法是cpu类型的，HT应关闭，如此的条件用汇编最好了，但是还要和另一个条件折中，这就是程序的美观性，于是还是用c吧：

unsigned char func( unsigned char c)

{

static unsigned char sta[16] = //不多不少的静态数据

{

0x00,0x08,0x04,0x0C,0x02,0x0A,0x06,0x0E,0x01,0x09,0x05,0x0D,0x03,0x0B,0x07,0x0F

};

unsigned char d = 0; //没有判断

d |= (sta[c&0xF]) << 4;

d |= sta[c>>4];

return d;

}

小声说一句，此题的解法甚多，比如可以定义一个大表，比如可以用二分法，或者按照管道的思想，一端进一端出，其实就是堆栈，将一个数按照一位一位的进入一个堆栈，然后再弹出，如果不是按位倒序，linux内核中有足够的算法供你参考，如果你在笔试时写上了linux内核的算法，那么考官最起码会觉得你说的读过内核并不假，但是可悲的是考官他自己不一定读过内核。要知道很多30岁以上的软件工程师都不一定能写出什么高效的算法，我们公司就有一批这样的可悲人群，乃不知有寄存器，无论堆栈！