Позиция наименее значимых бита, который устанавливается

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

FFS (3) - Linux man page

имя

ffs-найти Первый БИТ, установленный в слове

справка

#include <strings.h>
int ffs(int i);
#define _GNU_SOURCE
#include <string.h>
int ffsl(long int i);
int ffsll(long long int i);

описание

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

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

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

соответствующей

4.3 BSD, POSIX.1-2001.

Примечания

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

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

более оптимизирован?!

Примечание:

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

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

Если у вас есть одна инструкция этого класса вы можете дешево подражать другим.

найдите время, чтобы проработать его на бумаге и понять, что x & (x-1) очистит самый низкий бит набора в x, и ( x & ~(x-1) ) вернет только самый низкий бит набора, независимо от архитектуры, длины слова и т. д. Зная это, тривиально использовать аппаратное количество ведущих нулей / самый высокий набор бит, чтобы найти самый низкий набор бит, если нет явной инструкции для этого.

Если нет никакой соответствующей аппаратной поддержки вообще, реализация множественного и уточняющего запроса count-leading-zeroes дана здесь или на Немного Вертя Хаки страница может быть тривиально преобразована, чтобы дать самый низкий бит набора, используя вышеуказанные идентификаторы и имеет преимущество быть без ветвей.

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

ваша таблица (256 8-битных записей) должна содержать индекс LSB для каждого числа в диапазоне 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;  
}

Weee, множество решений, а не эталон в поле зрения. Вам должно быть стыдно за себя; -)

моя машина-это Intel i530 (2.9 GHz), работающий под управлением Windows 7 64-бит. Я скомпилировал с 32-разрядной версией MinGW.

$ gcc --version
gcc.exe (GCC) 4.7.2

$ gcc bench.c -o bench.exe -std=c99 -Wall -O2
$ bench
Naive loop.         Time = 2.91  (Original questioner)
De Bruijn multiply. Time = 1.16  (Tykhyy)
Lookup table.       Time = 0.36  (Andrew Grant)
FFS instruction.    Time = 0.90  (ephemient)
Branch free mask.   Time = 3.48  (Dan / Jim Balter)
Double hack.        Time = 3.41  (DocMax)

$ gcc bench.c -o bench.exe -std=c99 -Wall -O2 -march=native
$ bench
Naive loop.         Time = 2.92
De Bruijn multiply. Time = 0.47
Lookup table.       Time = 0.35
FFS instruction.    Time = 0.68
Branch free mask.   Time = 3.49
Double hack.        Time = 0.92

мой код:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


#define ARRAY_SIZE 65536
#define NUM_ITERS 5000  // Number of times to process array


int find_first_bits_naive_loop(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned value = nums[i];
            if (value == 0)
                continue;
            unsigned pos = 0;
            while (!(value & 1))
            {
                value >>= 1;
                ++pos;
            }
            total += pos + 1;
        }
    }

    return total;
}


int find_first_bits_de_bruijn(unsigned nums[ARRAY_SIZE])
{
    static const int MultiplyDeBruijnBitPosition[32] = 
    {
       1, 2, 29, 3, 30, 15, 25, 4, 31, 23, 21, 16, 26, 18, 5, 9, 
       32, 28, 14, 24, 22, 20, 17, 8, 27, 13, 19, 7, 12, 6, 11, 10
    };

    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned int c = nums[i];
            total += MultiplyDeBruijnBitPosition[((unsigned)((c & -c) * 0x077CB531U)) >> 27];
        }
    }

    return total;
}


unsigned char lowestBitTable[256];
int get_lowest_set_bit(unsigned num) {
    unsigned mask = 1;
    for (int cnt = 1; cnt <= 32; cnt++, mask <<= 1) {
        if (num & mask) {
            return cnt;
        }
    }

    return 0;
}
int find_first_bits_lookup_table(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned int value = nums[i];
            // note that order to check indices will depend whether you are on a big 
            // or little endian machine. This is for little-endian
            unsigned char *bytes = (unsigned char *)&value;
            if (bytes[0])
                total += lowestBitTable[bytes[0]];
            else if (bytes[1])
              total += lowestBitTable[bytes[1]] + 8;
            else if (bytes[2])
              total += lowestBitTable[bytes[2]] + 16;
            else
              total += lowestBitTable[bytes[3]] + 24;
        }
    }

    return total;
}


int find_first_bits_ffs_instruction(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            total +=  __builtin_ffs(nums[i]);
        }
    }

    return total;
}


int find_first_bits_branch_free_mask(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned value = nums[i];
            int i16 = !(value & 0xffff) << 4;
            value >>= i16;

            int i8 = !(value & 0xff) << 3;
            value >>= i8;

            int i4 = !(value & 0xf) << 2;
            value >>= i4;

            int i2 = !(value & 0x3) << 1;
            value >>= i2;

            int i1 = !(value & 0x1);

            int i0 = (value >> i1) & 1? 0 : -32;

            total += i16 + i8 + i4 + i2 + i1 + i0 + 1;
        }
    }

    return total;
}


int find_first_bits_double_hack(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned value = nums[i];
            double d = value ^ (value - !!value); 
            total += (((int*)&d)[1]>>20)-1022; 
        }
    }

    return total;
}


int main() {
    unsigned nums[ARRAY_SIZE];
    for (int i = 0; i < ARRAY_SIZE; i++) {
        nums[i] = rand() + (rand() << 15);
    }

    for (int i = 0; i < 256; i++) {
        lowestBitTable[i] = get_lowest_set_bit(i);
    }


    clock_t start_time, end_time;
    int result;

    start_time = clock();
    result = find_first_bits_naive_loop(nums);
    end_time = clock();
    printf("Naive loop.         Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_de_bruijn(nums);
    end_time = clock();
    printf("De Bruijn multiply. Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_lookup_table(nums);
    end_time = clock();
    printf("Lookup table.       Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_ffs_instruction(nums);
    end_time = clock();
    printf("FFS instruction.    Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_branch_free_mask(nums);
    end_time = clock();
    printf("Branch free mask.   Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_double_hack(nums);
    end_time = clock();
    printf("Double hack.        Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
}

OMG только что закрутил спираль.

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

в любое время у вас есть ветвь, процессор должен угадать, какая ветвь будет взята. Труба инструкций загружается с инструкциями, которые ведут вниз по предполагаемому пути. Если ЦП угадал неправильно, то труба инструкций сбрасывается, и другая ветвь должна быть загружена.

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

количество потерянных циклов процессора сильно варьируется от одного типа процессора к другому. Но вы можете ожидать от 20 до 150 потерянных циклов процессора.

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

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

мои извинения, если это уже было покрыто.

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

для компиляторов Microsoft используйте _BitScanForward & _BitScanReverse.
Для GCC использовать __строение_ФФС, __builtin_clz, __строение_ЧТЗ.

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

Извините, я совершенно забыл предоставить решение.. Это код, который я использую на IPAD, который не имеет инструкции уровня сборки для задачи:

unsigned BitScanLow_BranchFree(unsigned value)
{
    bool bwl = (value & 0x0000ffff) == 0;
    unsigned I1 = (bwl * 15);
    value = (value >> I1) & 0x0000ffff;

    bool bbl = (value & 0x00ff00ff) == 0;
    unsigned I2 = (bbl * 7);
    value = (value >> I2) & 0x00ff00ff;

    bool bnl = (value & 0x0f0f0f0f) == 0;
    unsigned I3 = (bnl * 3);
    value = (value >> I3) & 0x0f0f0f0f;

    bool bsl = (value & 0x33333333) == 0;
    unsigned I4 = (bsl * 1);
    value = (value >> I4) & 0x33333333;

    unsigned result = value + I1 + I2 + I3 + I4 - 1;

    return result;
}

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

Edit:

приведенный выше код полностью нарушена. Этот код работает и по-прежнему без ветвей (если оптимизирован):

int BitScanLow_BranchFree(ui value)
{
    int i16 = !(value & 0xffff) << 4;
    value >>= i16;

    int i8 = !(value & 0xff) << 3;
    value >>= i8;

    int i4 = !(value & 0xf) << 2;
    value >>= i4;

    int i2 = !(value & 0x3) << 1;
    value >>= i2;

    int i1 = !(value & 0x1);

    int i0 = (value >> i1) & 1? 0 : -32;

    return i16 + i8 + i4 + i2 + i1 + i0;
}

это возвращает -1, если задано 0. Если вы не заботитесь о 0 или рады получить 31 за 0, удалите расчет i0, экономя часть времени.

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

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

плюсы:

• петли
• нет ветвления
• работает в постоянном времени
• обрабатывает значение=0, возвращая в противном случае-out-of-bounds результат
• только две строки кода

плюсы:

• предполагает мало endianness как закодированный (может быть исправлено путем изменения константы)
• предполагает, что double является реальным * 8 IEEE float (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-битные ints с небольшим конечным хранилищем для всего (думаю, процессоры x86).

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

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

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

Так...
если вы проверяете 2 бита одновременно, у вас есть в худшем случае (Nbits/2) + 1 проверка всего.
если вы проверяете 3 бита одновременно, у вас есть в худшем случае (Nbits/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;
}

почему бы не использовать бинарный поиск? Это всегда будет завершено после 5 операций (при условии, что размер int составляет 4 байта):

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 { ...

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

модуль деления и поиска

 unsigned int v;  // find the number of trailing zeros in v
    int r;           // put the result in r
    static const int Mod37BitPosition[] = // map a bit value mod 37 to its position
    {
      32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4,
      7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5,
      20, 8, 19, 18
    };
    r = Mod37BitPosition[(-v & v) % 37];

метод деления по модулю и поиска возвращает различные значения для v=0x00000000 и v=FFFFFFFF, тогда как метод умножения и поиска DeBruijn возвращает ноль на обоих входах.

тест:-

unsigned int n1=0x00000000, n2=0xFFFFFFFF;

MultiplyDeBruijnBitPosition[((unsigned int )((n1 & -n1) * 0x077CB531U)) >> 27]); /* returns 0 */
MultiplyDeBruijnBitPosition[((unsigned int )((n2 & -n2) * 0x077CB531U)) >> 27]); /* returns 0 */
Mod37BitPosition[(((-(n1) & (n1))) % 37)]); /* returns 32 */
Mod37BitPosition[(((-(n2) & (n2))) % 37)]); /* returns 0 */

по словам шахматное Программирование BitScan page и мои собственные измерения, вычитание и xor быстрее, чем отрицание и маска.

(обратите внимание, что если вы собираетесь считать нули в 0, метод, как у меня он возвращает 63 в то время как отрицание и маска возвращает 0.)

вот 64-битное вычитание и xor:

unsigned long v;  // find the number of trailing zeros in 64-bit v 
int r;            // result goes here
static const int MultiplyDeBruijnBitPosition[64] = 
{
  0, 47, 1, 56, 48, 27, 2, 60, 57, 49, 41, 37, 28, 16, 3, 61,
  54, 58, 35, 52, 50, 42, 21, 44, 38, 32, 29, 23, 17, 11, 4, 62,
  46, 55, 26, 59, 40, 36, 15, 53, 34, 51, 20, 43, 31, 22, 10, 45,
  25, 39, 14, 33, 19, 30, 9, 24, 13, 18, 8, 12, 7, 6, 5, 63
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v ^ (v-1)) * 0x03F79D71B4CB0A89U)) >> 58];

для справки, вот 64-разрядная версия метода отрицания и маски:

unsigned long v;  // find the number of trailing zeros in 64-bit v 
int r;            // result goes here
static const int MultiplyDeBruijnBitPosition[64] = 
{
  0, 1, 48, 2, 57, 49, 28, 3, 61, 58, 50, 42, 38, 29, 17, 4,
  62, 55, 59, 36, 53, 51, 43, 22, 45, 39, 33, 30, 24, 18, 12, 5,
  63, 47, 56, 27, 60, 41, 37, 16, 54, 35, 52, 21, 44, 32, 23, 11,
  46, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x03F79D71B4CB0A89U)) >> 58];

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

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

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

по существу это двоичный поиск.

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

еще одно решение, не самое быстрое, возможно, но кажется довольно хорошим.
По крайней мере, у него нет ветвей. ;)

uint32 x = ...;  // 0x00000001  0x0405a0c0  0x00602000
x |= x <<  1;    // 0x00000003  0x0c0fe1c0  0x00e06000
x |= x <<  2;    // 0x0000000f  0x3c3fe7c0  0x03e1e000
x |= x <<  4;    // 0x000000ff  0xffffffc0  0x3fffe000
x |= x <<  8;    // 0x0000ffff  0xffffffc0  0xffffe000
x |= x << 16;    // 0xffffffff  0xffffffc0  0xffffe000

// now x is filled with '1' from the least significant '1' to bit 31

x = ~x;          // 0x00000000  0x0000003f  0x00001fff

// now we have 1's below the original least significant 1
// let's count them

x = x & 0x55555555 + (x >>  1) & 0x55555555;
                 // 0x00000000  0x0000002a  0x00001aaa

x = x & 0x33333333 + (x >>  2) & 0x33333333;
                 // 0x00000000  0x00000024  0x00001444

x = x & 0x0f0f0f0f + (x >>  4) & 0x0f0f0f0f;
                 // 0x00000000  0x00000006  0x00000508

x = x & 0x00ff00ff + (x >>  8) & 0x00ff00ff;
                 // 0x00000000  0x00000006  0x0000000d

x = x & 0x0000ffff + (x >> 16) & 0x0000ffff;
                 // 0x00000000  0x00000006  0x0000000d
// least sign.bit pos. was:  0           6          13

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 строк кода.

etc.

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

нашел этот умный трюк, используя " волшебные маски "в" искусстве программирования, часть 4", которая делает это в O(log(n)) время для n-разрядного числа. [с дополнительным пространством log(n)]. Типичные решения проверка для установленного бита либо O(n) или нужно O (n) дополнительное пространство для поиска таблицы, так что это хороший компромисс.

волшебные маски:

m0 = (...............01010101)  
m1 = (...............00110011)
m2 = (...............00001111)  
m3 = (.......0000000011111111)
....

ключевая идея: Нет конечных нулей в x = 1 * [(x & m0) = 0] + 2 * [(x & m1) = 0] + 4 * [(x & m2) = 0] + ...

int lastSetBitPos(const uint64_t x) {
    if (x == 0)  return -1;

    //For 64 bit number, log2(64)-1, ie; 5 masks needed
    int steps = log2(sizeof(x) * 8); assert(steps == 6);
    //magic masks
    uint64_t m[] = { 0x5555555555555555, //     .... 010101
                     0x3333333333333333, //     .....110011
                     0x0f0f0f0f0f0f0f0f, //     ...00001111
                     0x00ff00ff00ff00ff, //0000000011111111 
                     0x0000ffff0000ffff, 
                     0x00000000ffffffff };

    //Firstly extract only the last set bit
    uint64_t y = x & -x;

    int trailZeros = 0, i = 0 , factor = 0;
    while (i < steps) {
        factor = ((y & m[i]) == 0 ) ? 1 : 0;
        trailZeros += factor * pow(2,i);
        ++i;
    }
    return (trailZeros+1);
}

Если C++11 доступен для вас, компилятор иногда может выполнить эту задачу для вас:)

constexpr std::uint64_t lssb(const std::uint64_t value)
{
    return !value ? 0 : (value % 2 ? 1 : lssb(value >> 1) + 1);
}

результат-индекс на основе 1.

Это в отношении @Антон Тихого ответа

вот моя реализация C++11 constexpr, устраняющая приведения и удаляющая предупреждение на VC++17, усекая 64-битный результат до 32 бит:

constexpr uint32_t DeBruijnSequence[32] =
{
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
constexpr uint32_t ffs ( uint32_t value )
{
    return  DeBruijnSequence[ 
        (( ( value & ( -static_cast<int32_t>(value) ) ) * 0x077CB531ULL ) & 0xFFFFFFFF)
            >> 27];
}

чтобы обойти проблему 0x1 и 0x0, возвращающих 0, вы можете сделать:

constexpr uint32_t ffs ( uint32_t value )
{
    return (!value) ? 32 : DeBruijnSequence[ 
        (( ( value & ( -static_cast<int32_t>(value) ) ) * 0x077CB531ULL ) & 0xFFFFFFFF)
            >> 27];
}

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

наконец, если интересно, вот список статический утверждает, чтобы проверить, что код делает то, что предназначено для:

static_assert (ffs(0x1) == 0, "Find First Bit Set Failure.");
static_assert (ffs(0x2) == 1, "Find First Bit Set Failure.");
static_assert (ffs(0x4) == 2, "Find First Bit Set Failure.");
static_assert (ffs(0x8) == 3, "Find First Bit Set Failure.");
static_assert (ffs(0x10) == 4, "Find First Bit Set Failure.");
static_assert (ffs(0x20) == 5, "Find First Bit Set Failure.");
static_assert (ffs(0x40) == 6, "Find First Bit Set Failure.");
static_assert (ffs(0x80) == 7, "Find First Bit Set Failure.");
static_assert (ffs(0x100) == 8, "Find First Bit Set Failure.");
static_assert (ffs(0x200) == 9, "Find First Bit Set Failure.");
static_assert (ffs(0x400) == 10, "Find First Bit Set Failure.");
static_assert (ffs(0x800) == 11, "Find First Bit Set Failure.");
static_assert (ffs(0x1000) == 12, "Find First Bit Set Failure.");
static_assert (ffs(0x2000) == 13, "Find First Bit Set Failure.");
static_assert (ffs(0x4000) == 14, "Find First Bit Set Failure.");
static_assert (ffs(0x8000) == 15, "Find First Bit Set Failure.");
static_assert (ffs(0x10000) == 16, "Find First Bit Set Failure.");
static_assert (ffs(0x20000) == 17, "Find First Bit Set Failure.");
static_assert (ffs(0x40000) == 18, "Find First Bit Set Failure.");
static_assert (ffs(0x80000) == 19, "Find First Bit Set Failure.");
static_assert (ffs(0x100000) == 20, "Find First Bit Set Failure.");
static_assert (ffs(0x200000) == 21, "Find First Bit Set Failure.");
static_assert (ffs(0x400000) == 22, "Find First Bit Set Failure.");
static_assert (ffs(0x800000) == 23, "Find First Bit Set Failure.");
static_assert (ffs(0x1000000) == 24, "Find First Bit Set Failure.");
static_assert (ffs(0x2000000) == 25, "Find First Bit Set Failure.");
static_assert (ffs(0x4000000) == 26, "Find First Bit Set Failure.");
static_assert (ffs(0x8000000) == 27, "Find First Bit Set Failure.");
static_assert (ffs(0x10000000) == 28, "Find First Bit Set Failure.");
static_assert (ffs(0x20000000) == 29, "Find First Bit Set Failure.");
static_assert (ffs(0x40000000) == 30, "Find First Bit Set Failure.");
static_assert (ffs(0x80000000) == 31, "Find First Bit Set Failure.");

вот одна простая альтернатива, хотя поиск журналов немного затратен.

if(n == 0)
  return 0;
return log2(n & -n)+1;   //Assuming the bit index starts from 1

недавно я вижу, что премьер-министр Сингапура опубликовал программу, которую он написал на facebook, есть одна строка, чтобы упомянуть об этом..

логика просто "значение & - значение", предположим, что у вас есть 0x0FF0, то, 0FF0 & (F00F+1) , что равно 0x0010, что означает, что самый низкий 1 находится в 4-м бит.. :)

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

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 ГБ, если мы оставим возвращаемый тип как unsigned). Это пример торговли одним ограниченным ресурсом (ОЗУ) для другого (скорость выполнения).

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