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

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

103 голосов
/ 16 апреля 2009

Я ищу эффективный способ определения позиции младшего значащего бита, который установлен в целое число, например для 0x0FF0 это будет 4.

Тривиальная реализация такова: 

unsigned GetLowestBitPos(unsigned value)
{
   assert(value != 0); // handled separately

   unsigned pos = 0;
   while (!(value & 1))
   {
      value >>= 1;
      ++pos;
   }
   return pos;
}

Есть идеи, как выжать из него несколько циклов?

(Примечание: этот вопрос для людей, которым нравятся такие вещи, а не для людей, которые говорят мне, что ксизоптимизация - это зло.)

[редактировать] Спасибо всем за идеи! Я также узнал несколько других вещей. Круто!

Ответы [ 22 ]

160 голосов
/ 16 апреля 2009

Bit Twiddling Hacks предлагает отличную коллекцию бит-тиддлинг-хаков, с приложением обсуждения производительности / оптимизации. Мое любимое решение для вашей проблемы (с этого сайта) «умножение и поиск»: 

unsigned int v;  // find the number of trailing zeros in 32-bit v 
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[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
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

Полезные ссылки:

73 голосов
/ 17 апреля 2009

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

ffs (3) - справочная страница по Linux

Имя

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.3BSD, POSIX.1-2001.

Примечания

Системы

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

46 голосов
/ 16 апреля 2009

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

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

Примечание стороны:

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

36 голосов
/ 16 апреля 2009

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

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

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

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

17 голосов
/ 16 апреля 2009

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

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

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

1007 * Е.Г. * 

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;  
}
16 голосов
/ 08 февраля 2014

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

Моя машина - Intel i530 (2,9 ГГц), работающая под управлением 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);
}
12 голосов
/ 03 июня 2012

OMG только что завернул.

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

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

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

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

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

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

Очевидно, что самым быстрым решением с постоянным временем является решение, которое включает в себя детерминистическую математику. Чистое и элегантное решение.

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

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

Для компиляторов Microsoft используйте _BitScanForward & _BitScanReverse.
Для GCC используйте __builtin_ffs, __builtin_clz, __builtin_ctz.

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

Извините, я совершенно забыл предоставить решение. Это код, который я использую на 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, сэкономив часть времени.

7 голосов
/ 18 апреля 2009

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

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

4 голосов
/ 16 апреля 2009

Почему бы не использовать бинарный поиск ? Это всегда завершится после 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 { ...
4 голосов
/ 16 апреля 2009

Это может быть сделано в худшем случае менее 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;
}
Страница:
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...