Как мне извлечь немного более оптимальным способом?

Question

Сегодня у меня было интервью, в котором меня попросили написать две функции «С»: одну для извлечения одного бита, а другую для извлечения диапазона битов из символа. Я взял некоторое время и придумал эти методы.

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));
}

Но интервьюер продолжал спрашивать меня, могу ли я еще ускорить код (с точки зрения циклов ЦП) и есть ли какая-то область оптимизации, которую я мог бы сделать для ее достижения. Я был явно не в духе, и мне любопытно узнать, как бы вы это сделали?

Answer 1

В extractBit, если вы переключаетесь первым, вы можете маскировать 1 вместо (1<<pos). Учитывая, что pos является аргументом функции, которая сохраняет вычисления.

return (byte >> pos) & 1;

Во второй функции я бы сказал, что startingPos и offset оба положительны, вместо того, чтобы утверждать, что их сумма положительна, это имеет больше смысла.

Answer 2

Таблица поиска?

Answer 3

Вы можете ускорить первую функцию, сначала сместившись вправо, а затем замаскировав бит:

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);
}

Конечно, вы должны быть осторожны с диапазонами, как вы это делали в своем коде.

EDIT: если вы хотите, чтобы extractBitRange(b,i,0) вел себя как extractBit(b,i) и извлекал один бит в позиции i, этот вариант делает это:

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

Answer 4

Еще один, который вы делаете в диапазоне битов:

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

Поскольку << 1 является не чем иным, как *2, вы можете сделать эту операцию с вашей константой (которая, если вы работаете с байтами сигнала, просто избавляется от LSB).

Answer 5

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;
}

Answer 6

Если вы хотите получить действительно быстро, вы можете использовать таблицу поиска. Я предполагаю, что именно к этому стремился интервьюер (в качестве окончательного ответа на вопрос «как я могу сделать это быстрее»).

По сути, это означает, что вы заранее создаете огромную таблицу, сопоставляя каждую возможную комбинацию параметров с правильным результатом. Например, у вас будет:

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

Очевидно, что это необходимо поместить в допустимые структуры данных c (массивы, проиндексированные байтом и положением). Это позволит вам в вашей функции просто возвращать место в массиве на основе любой схемы индексации, которую вы выберете.

Для первой функции это не займет слишком много памяти. Мы говорим о значении байтовых значений (байт может иметь 256 различных значений), умноженных на 8 возможных значений для запуска pos, что составляет массив 2048.

Для второй функции, , на самом деле это заняло бы намного больше места. Вам нужно умножить 256 возможных значений для начального и конечного положений (помните, что существуют недопустимые комбинации начального и конечного положений).

Полагаю, что интервьюер просто хотел, чтобы вы ответили, что это будет способ ускорить его, а затем предложите вышеизложенное, чтобы попытаться оценить, сколько места это будет стоить по сравнению с сэкономленным временем.