【攒rp】09/10/15搜狐笔试最后一题（and鄙视自己……）

kyqacecombat

10月15日参加搜狐笔试最后一题
不是俺收到的第一个，但是是时间最早的笔试，基本没有做什么准备就去了
一开始怀疑，搜狐说了是“海笔”，是不是只要投了简历，基本靠谱的就都有机会？不过这样也挺好的，至少有机会总比没有好。
考试开始一看到卷子，基本在我意料之中，有关java，数据结构，算法的题我都基本抓瞎啦，毕竟非CS专业的就是这样，理论知识薄弱……。接下来的一个星期要好好补一下。
名词解释题：很囧，回来一查发现分别把UML，COM的第一个英文单词搞错了……10个里面有4个不认识，哎，我已经感到肯定被bs勒。
最后得说说印象最深刻的最后一题：给一个字节（8bit），要求将第0和第7位对换，第1和第6位对换，第2和第5位对换，第3和第4位对换。条件：海量数据。要求：设计一个函数或类实现，并考虑性能。
性能的问题我没有考虑太多，直接写了一个函数就交了卷。回来上网查了一下，貌似方法还是不少的，主要还是位运算和移位操作，有采用循环的，有循环里调用一个交换函数的等等。我这个方法好像还没有看到有人使用哩，不知算不算独创？也不知有没有错误，回头要用开发环境验证一下。
void f(BYTE* origin) // 输入参数直接采用该字节的指针
{
BYTE temp = *origin; // 先保存原始的值，然后可以直接在原始值上操作……
       // 对于海量数据不知会不会造成内存换页操作方面的问题
// 思路：如果要比较的两个bit都是0或者都是1，实质上是不需要对换的；
// 需要对换的只有0，1的情况，而这种情况下0^1 = 1（异或）
// 异或结果为1就表明需要交换，为0则表明不需要交换
// 看一下原始bit的值与“异或结果”相异或的结果：
// 0与1异或，得1，也就是把0交换为1；1与1异或，得0，也就是把1交换到0；
// 0或者1，与0相异或的结果，原值保持不变。
// 因此把一个bit交换为需要的值（0->1或1->0）需要：
// （1）一次异或 + 一次移位，得到“异或结果”；
// （2）对“异或结果”进行一次按位与处理，只保留需要的那个bit；
// （3）把“异或结果”与原始值相异或。完成该bit的处理。
// 最后，要交换一个字节，只要进行8次这种运算
// 当时竟然忘了在origin前面写*号，ft
// 再次鄙视自己，泪……
// 运算过程
*origin ^= (temp ^ (temp<<7)) & 0x80; // bit 7
*origin ^= (temp ^ (temp<<5)) & 0x40; // bit 6
*origin ^= (temp ^ (temp<<3)) & 0x20; // bit 5
*origin ^= (temp ^ (temp<<1)) & 0x10; // bit 4
*origin ^= (temp ^ (temp>>7)) & 0x01; // bit 0
*origin ^= (temp ^ (temp>>5)) & 0x02; // bit 1
*origin ^= (temp ^ (temp>>3)) & 0x04; // bit 2
*origin ^= (temp ^ (temp>>1)) & 0x08; // bit 3
// 也可以减少位运算的次数，例如对于bit 7和bit 0，只要：
BYTE temp1 = (temp ^ (temp<<7)) & 0x80;
*origin ^= temp1;
*origin ^= (temp1>>7); // 余下可以类推，共进行4次
}

同时发在：http://hi_baidu_com/marine_kyq/blog/item/50589ffb08457d9d58ee905d_html