Положение младшего значащего бита, который установлен

Если у вас есть ресурсы, вы можете пожертвовать памятью для повышения скорости:

static const unsigned bitPositions[MAX_INT] = { 0, 0, 1, 0, 2, /* ... */ };

unsigned GetLowestBitPos(unsigned value)
{
    assert(value != 0); // handled separately
    return bitPositions[value];
}

Примечание : Эта таблица будет использовать не менее 4 ГБ (16 ГБ, если мы оставим тип возврата как без знака ). Это пример обмена одного ограниченного ресурса (ОЗУ) на другой (скорость выполнения).

Если ваша функция должна оставаться переносимой и работать как можно быстрее любой ценой, это будет путь. В большинстве реальных приложений таблица 4 ГБ нереальна.

unsigned GetLowestBitPos(unsigned value)
{
    if (value & 1) return 1;
    if (value & 2) return 2;
    if (value & 4) return 3;
    if (value & 8) return 4;
    if (value & 16) return 5;
    if (value & 32) return 6;
    if (value & 64) return 7;
    if (value & 128) return 8;
    if (value & 256) return 9;
    if (value & 512) return 10;
    if (value & 1024) return 11;
    if (value & 2048) return 12;
    if (value & 4096) return 13;
    if (value & 8192) return 14;
    if (value & 16384) return 15;
    if (value & 32768) return 16;
    if (value & 65536) return 17;
    if (value & 131072) return 18;
    if (value & 262144) return 19;
    if (value & 524288) return 20;
    if (value & 1048576) return 21;
    if (value & 2097152) return 22;
    if (value & 4194304) return 23;
    if (value & 8388608) return 24;
    if (value & 16777216) return 25;
    if (value & 33554432) return 26;
    if (value & 67108864) return 27;
    if (value & 134217728) return 28;
    if (value & 268435456) return 29;
    if (value & 536870912) return 30;
    return 31;
}

50% всех чисел вернутся в первой строке кода.

75% всех чисел вернутся в первых 2 строках кода.

87% всех номеров вернутся в первых 3 строках кода. код.

94% всех чисел вернутся в первые 4 строки кода.

97% всех чисел вернутся в первые 5 строк кода.

и т. д.

Вы можете проверить, установлены ли какие-либо биты младшего разряда. Если это так, то посмотрите на нижний порядок оставшихся битов. Например:

32bit int - проверить, установлены ли какие-либо из первых 16. Если это так, проверьте, установлены ли какие-либо из первых 8. если так, ....

, если нет, проверьте, установлены ли какие-либо из верхних 16 ..

По сути, это бинарный поиск.

Это может быть сделано в худшем случае менее 32 операций:

Принцип: Проверка на 2 или более бит так же эффективна, как и проверка на 1 бит.

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

Итак ...
если вы проверяете 2 бита за раз, у вас в худшем случае (Нбит / 2) + 1 проверка всего.
если вы проверяете 3 бита за раз, у вас есть в наихудшем случае (Нбит / 3) + 2 проверки всего.
...

Оптимальным было бы проверять в группах по 4. Что в худшем случае потребовало бы 11 операций вместо ваших 32.

Наилучший случай - от 1 проверки вашего алгоритма, хотя до 2 проверок, если вы используете это идея группировки. Но эта дополнительная 1 проверка в лучшем случае того стоит для экономии в худшем случае.

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

int getLowestBitPos(unsigned int value)
{
    //Group 1: Bits 0-3
    if(value&0xf)
    {
        if(value&0x1)
            return 0;
        else if(value&0x2)
            return 1;
        else if(value&0x4)
            return 2;
        else
            return 3;
    }

    //Group 2: Bits 4-7
    if(value&0xf0)
    {
        if(value&0x10)
            return 4;
        else if(value&0x20)
            return 5;
        else if(value&0x40)
            return 6;
        else
            return 7;
    }

    //Group 3: Bits 8-11
    if(value&0xf00)
    {
        if(value&0x100)
            return 8;
        else if(value&0x200)
            return 9;
        else if(value&0x400)
            return 10;
        else
            return 11;
    }

    //Group 4: Bits 12-15
    if(value&0xf000)
    {
        if(value&0x1000)
            return 12;
        else if(value&0x2000)
            return 13;
        else if(value&0x4000)
            return 14;
        else
            return 15;
    }

    //Group 5: Bits 16-19
    if(value&0xf0000)
    {
        if(value&0x10000)
            return 16;
        else if(value&0x20000)
            return 17;
        else if(value&0x40000)
            return 18;
        else
            return 19;
    }

    //Group 6: Bits 20-23
    if(value&0xf00000)
    {
        if(value&0x100000)
            return 20;
        else if(value&0x200000)
            return 21;
        else if(value&0x400000)
            return 22;
        else
            return 23;
    }

    //Group 7: Bits 24-27
    if(value&0xf000000)
    {
        if(value&0x1000000)
            return 24;
        else if(value&0x2000000)
            return 25;
        else if(value&0x4000000)
            return 26;
        else
            return 27;
    }

    //Group 8: Bits 28-31
    if(value&0xf0000000)
    {
        if(value&0x10000000)
            return 28;
        else if(value&0x20000000)
            return 29;
        else if(value&0x40000000)
            return 30;
        else
            return 31;
    }

    return -1;
}

Существует инструкция по сборке x86 ( bsf ), которая сделает это. :)

Больше оптимизировано?!

Стороннее примечание:

Оптимизация на этом уровне по своей природе зависит от архитектуры. Современные процессоры слишком сложны (с точки зрения предсказания ветвлений, пропадания кэша, конвейерной обработки), поэтому предсказать, какой код на какой архитектуре будет выполняться быстрее, так сложно. Сокращение операций с 32 до 9 или подобных вещей может даже снизить производительность на некоторых архитектурах. Оптимизированный код в одной архитектуре может привести к ухудшению кода в другой. Я думаю, что вы либо оптимизируете это для конкретного процессора, либо оставите его как есть и позволите компилятору выбирать, что он считает лучше.

См. Мой ответ здесь , чтобы узнать, как это сделать с помощью одной инструкции x86, за исключением того, что найдите младший значащий установленный бит, который вы хотите использовать вместо инструкции BSR BSF («bit scan forward»).

Почему бы не использовать встроенные ffs ? (Я взял man-страницу из Linux, но она более широко доступна.)

ffs (3) - man-страница Linux

Имя

ffs - найти первый бит, заданный в слове

Резюме

 #include 
int ffs (int i);
#define _GNU_SOURCE
#include 
int ffsl (long int i);
int ffsll (long long int i);

Описание

Функция ffs () возвращает позицию первого (младшего) бита, установленного в слове i. Наименее значимый бит - это позиция 1, а наиболее значимая позиция, например, 32 или 64. Функции ffsll () и ffsl () делают то же самое, но принимают аргументы, возможно, разного размера.

Возвращаемое значение

Эти функции возвращают позицию первого установленного бита или 0, если в i не установлены биты.

Соответствует

4.3BSD, POSIX.1-2001.

Примечания

Системы BSD имеют прототип в < string.h> .

Why not use binary search? This will always complete after 5 operations (assuming int size of 4 bytes):

if (0x0000FFFF & value) {
    if (0x000000FF & value) {
        if (0x0000000F & value) {
            if (0x00000003 & value) {
                if (0x00000001 & value) {
                    return 1;
                } else {
                    return 2;
                }
            } else {
                if (0x0000004 & value) {
                    return 3;
                } else {
                    return 4;
                }
            }
        } else { ...
    } else { ...
} else { ...

Самое быстрое (не внутреннее / не ассемблерное) решение этой проблемы - найти младший байт и затем использовать этот байт в таблице поиска с 256 записями. Это дает вам наихудшую производительность из четырех условных инструкций и наилучший случай из 1. Не только это наименьшее количество инструкций, но и наименьшее количество ветвей, что очень важно для современного оборудования.

Ваша таблица (256 8-битных записей) должны содержать индекс LSB для каждого числа в диапазоне 0-255. Вы проверяете каждый байт своего значения и находите младший ненулевой байт, а затем используете это значение для поиска реального индекса.

Для этого требуется 256 байт памяти, но если скорость этой функции так важна, то 256 байтов того стоят,

Например

Вдохновленный этим аналогичным постом , который включает в себя поиск установленного бита, я предлагаю следующее:

unsigned GetLowestBitPos(unsigned value)
{
   double d = value ^ (value - !!value); 
   return (((int*)&d)[1]>>20)-1023; 
}

Плюсы:

• нет циклов
• нет ветвлений
• выполняется в постоянное время
• обрабатывает значение = 0, возвращая результат, выходящий за пределы
• , только две строки кода

Минусы:

• предполагает, что в кодированном виде используется маленький порядок байтов (может быть исправлено путем изменения констант).
• предполагает, что double - это действительное число с плавающей запятой * 8 IEEE (IEEE 754)

Обновление: Как отмечено в комментариях, объединение является более чистой реализацией (по крайней мере для C) и будет выглядеть следующим образом:

unsigned GetLowestBitPos(unsigned value)
{
    union {
        int i[2];
        double d;
    } temp = { .d = value ^ (value - !!value) };
    return (temp.i[1] >> 20) - 1023;
}

Это предполагает 32-разрядные целочисленные значения с сохранением порядка байтов для всего (например, процессоры x86).

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

Ваша таблица (256 8-битных записей) должна содержать индекс младшего разряда для каждого числа в диапазоне 0–255. Вы проверяете каждый байт своего значения и находите младший ненулевой байт, а затем используете это значение для поиска реального индекса.

Для этого действительно требуется 256 байт памяти, но если скорость этой функции настолько важна, то 256 байт того стоят,

Например.

byte lowestBitTable[256] = {
.... // left as an exercise for the reader to generate
};

unsigned GetLowestBitPos(unsigned value)
{
  // note that order to check indices will depend whether you are on a big 
  // or little endian machine. This is for little-endian
  byte* bytes = (byte*)value;
  if (bytes[0])
    return lowestBitTable[bytes[0]];
  else if (bytes[1])
      return lowestBitTable[bytes[1]] + 8;
  else if (bytes[2])
      return lowestBitTable[bytes[2]] + 16;
  else
      return lowestBitTable[bytes[3]] + 24;  
}