代码之家 › 专栏 › 技术社区 › rajachan

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

optimization c

rajachan · 技术社区 · 16 年前

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

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

但面试官一直在问我是否可以进一步加快代码的速度(以cpu周期为单位),以及是否可以进行任何优化来实现它。很明显,我心情不好,我很想知道你会怎么做?

6 回复 | 直到 14 年前

Pascal Cuoq 16 年前

在extractBit中,如果你先移位,你可以用 1 而不是 (1<<pos) . 考虑到pos是函数的参数,这节省了计算。

return (byte >> pos) & 1;

在第二个函数中,我断言 startingPos 和 offset 两者都是正的,而不是断言它们的总和是正的,这样做更有意义。

user49117 16 年前

查表?

Marcin DeptuÅa 16 年前

另一种是在比特范围内进行的:


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

像 << 1 没什么了 *2 ,您可以对常量进行此操作(如果您对单字节进行操作,则只需去掉LSB)。

Kris 16 年前

您可以通过先向右移动,然后屏蔽位来加速第一个功能:

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)

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

kapilddit 12 年前

int extractBit(int byte, int pos) 
{
    if( !((pos >= 0) && (pos < 16)) )
    {
        return 0;
    }
    return ( ( byte & (1<<pos) ) >> 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;
}

-3

Edan Maor 16 年前

如果你想更快,你可以使用一个查找表。我猜这就是面试官想要的(作为“我怎样才能让面试更快”的最终答案)。

基本上,这意味着您需要提前创建一个巨大的表,将所有可能的参数组合映射到正确的结果。例如,你会有:

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

显然,这需要放入有效的c数据结构(数组,按字节和位置索引)。这将允许您在函数中根据所选的索引方案返回数组中的一个位置。

对于第一个函数, 这不会占用太多内存。我们说的是一个字节的值(一个字节可以有256个不同的值)乘以8个可能的起始位置值,这构成了一个2048的数组。

对于第二个函数, 这实际上会占用更多的空间。您需要将起始位置和结束位置的所有可能值相乘256倍(请记住,起始位置和结束位置存在非法组合)。

我猜面试官只是想让你回答,这将是一种加快面试速度的方法,然后提供上述想法,试图估算这将花费多少空间和节省多少时间。