如何以更优化的方式提取一点？

我今天接受了采访，他们要求我写两个“C”函数，一个用于提取单个位，另一个用于从字符中提取一系列位。 我花了一段时间想出了这些方法。

int extractBit(char byte, int pos) { assert( (pos >= 0) && (pos < 8) ); return ( ( byte & (1<> pos); } char extractBitRange(char byte, int startingPos, int offset) { assert( ( (startingPos + offset) >= 0) && ( (startingPos + offset) > startingPos ) & ~(0xff << (offset + 1)); } 

但是面试官不停地问我是否可以进一步加快代码（就cpu周期而言）以及是否有任何优化范围可以实现它。 我显然不合适，我很想知道你会怎么做？

Answer 1

在extractBit中，如果先移动，则可以使用1而不是(1<进行掩码。 考虑到pos是函数的参数，可以节省计算量。

return (byte >> pos) & 1;

在第二个函数中，我会断言startingPos和offset都是正数而不是断言它们的和是正数，这样就更有意义了。

Answer 2

一张查表？

Answer 3

你在比特范围内做的另一个：

 ~(0xff << (offset + 1)) --> ~(0xfe << offset) 

因为<< 1是*2 ，你可以对你的常量进行这个操作（如果你在单元字节上操作就是摆脱LSB）。

Answer 4

您可以通过先向右移动然后屏蔽该位来加速第一个function：

 int extractBit(char byte, int pos) { return (byte >> pos) & 0x01; } 

这可以节省您一次操作。

对于第二个问题，我假设startingPos是你要提取的块的第一位，而offset是你需要的块中有多少位。 然后你可以使用这个：

 char extractBitRange(char byte, int startingPos, int offset) { return (byte >> startingPos) & ((1 << offset)-1); } 

当然，您必须小心范围，就像在代码中一样。

编辑：如果你想让extractBitRange(b,i,0)表现得像extractBit(b,i)并在位置i提取一个位，这个变量做到了：

 return (byte >> startingPos) & ((2 << offset) - 1); 

Answer 5

 int extractBit(int byte, int pos) { if( !((pos >= 0) && (pos < 16)) ) { return 0; } return ( ( byte & (1<> pos); } int _tmain() { // TODO: Please replace the sample code below with your own. int value; signed int res,bit; value = 0x1155; printf("%x\n",value); //Console::WriteLine("Hello World"); //fun1(); for(bit=15;bit>=0;bit--) { res =extractBit(value,bit); printf("%d",res); } return 0; } 

Answer 6

如果您想快速获得，可以使用查找表。 我猜这就是面试官的目的（作为“我怎样才能让这更快”的最终答案）。

基本上，这意味着您事先创建了一个巨大的表，将每个可能的参数组合映射到正确的结果。 例如，你有：

 byte = 0x0, pos = 0, result = 0 byte = 0x0, pos = 1, result = 0 ... byte = 0x1, pos = 0, result = 1 

显然，这需要放入有效的c数据结构（数组，由byte和pos索引）。 这将允许您在函数中根据您选择的索引方案返回数组中的位置。

对于第一个函数，这不会占用太多内存。 我们讨论的是一个字节的值（一个字节可以有256个不同的值）乘以8个可能的值来启动pos，这使得一个2048的数组。

对于第二个function，这实际上会占用更多空间。 您需要将开始和结束位置的所有可能值乘以256倍（请记住，有起始和结束位置的非法组合）。

我猜测面试官只是想让你回答这将是一种加快速度的方法，然后提供上述思路，试图估计它将节省多少空间。