Какой самый быстрый / самый эффективный способ найти старший бит (msb) в целом числе в C?

Question

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

Я знаю, что POSIX поддерживает метод ffs() в strings.h для поиска первого установленного бита, но, похоже, нет соответствующего метода fls().

Есть ли какой-то действительно очевидный способ сделать это, которого мне не хватает?

Что делать в случаях, когда вы не можете использовать функции POSIX для переносимости?

Редактировать: А как насчет решения, которое работает как на 32-, так и на 64-битных архитектурах (многие списки кода кажутся работающими только на 32-битных целых числах).

Answer 1

GCC имеет :

 -- Built-in Function: int __builtin_clz (unsigned int x)
     Returns the number of leading 0-bits in X, starting at the most
     significant bit position.  If X is 0, the result is undefined.

 -- Built-in Function: int __builtin_clzl (unsigned long)
     Similar to `__builtin_clz', except the argument type is `unsigned
     long'.

 -- Built-in Function: int __builtin_clzll (unsigned long long)
     Similar to `__builtin_clz', except the argument type is `unsigned
     long long'.

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

---

Полезный трюк, если ваш вход может быть нулем, равен __builtin_clz(x | 1): безусловная установка младшего бита без изменения других делает вывод 0 для x=0, без изменения выхода для любых других вход.

Чтобы избежать необходимости делать это, ваш другой вариант - это встроенные функции для платформы, такие как __clz ARM GCC (заголовок не требуется) или _lzcnt_u32 x86 для процессоров, которые поддерживают инструкцию lzcnt. (Помните, что lzcnt декодируется как bsr на старых процессорах вместо сбоя, что дает 31-lzcnt для ненулевых входов.)

К сожалению, нет никакого способа использовать преимущества различных команд CLZ на платформах, отличных от x86, которые определяют результат для input = 0 как 32 или 64 (в зависимости от ширины операнда). x86 lzcnt тоже делает это, в то время как bsr создает битовый индекс, который компилятор должен переворачивать, если вы не используете 31-__builtin_clz(x).

(«неопределенный результат» - это не неопределенное поведение C, а просто значение, которое не определено. Это фактически то, что было в регистре назначения при выполнении инструкции. AMD это документирует, Intel нет, но процессоры Intel делают реализовать это поведение. Но это , а не независимо от того, что было ранее в переменной C, которой вы присваиваете, обычно это не так, когда gcc превращает C. в asm. См. также Почему прерывается вывод зависимость "от LZCNT имеет значение? )

Answer 2

Если вы работаете на x86 и играете для небольшого встроенного ассемблера, Intel предоставляет инструкцию BSR («обратное сканирование битов»). Это быстро на некоторых x86 (микрокодируется на других). Из руководства:

Ищет в исходном операнде наиболее значимый набор бит (1 бит). Если наиболее значимым 1 бит найден, его битовый индекс сохранен в операнде назначения. Операндом-источником может быть регистр или ячейка памяти; целевой операнд является регистром. Битовый индекс - беззнаковое смещение от бит 0 исходного операнда. Если операндом источника контента является 0, содержание операнда назначения не определено.

(Если вы используете PowerPC, есть похожая инструкция cntlz ("считать начальные нули").)

Пример кода для gcc:

#include <iostream>

int main (int,char**)
{
  int n=1;
  for (;;++n) {
    int msb;
    asm("bsrl %1,%0" : "=r"(msb) : "r"(n));
    std::cout << n << " : " << msb << std::endl;
  }
  return 0;
}

См. Также этот учебник по встроенному ассемблеру , который показывает (раздел 9.4), что он значительно быстрее, чем зацикливание кода.

Answer 3

Так как 2 ^ N является целым числом только с установленным N-ным битом (1 << N), нахождение позиции (N) старшего установленного бита является целочисленной лог-базой 2 этого целого числа. </p>

http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

unsigned int v;
unsigned r = 0;

while (v >>= 1) {
    r++;
}

Этот «очевидный» алгоритм может быть не прозрачен для всех, но когда вы понимаете, что код смещается вправо на один бит до тех пор, пока самый левый бит не будет сдвинут (обратите внимание, что C рассматривает любое ненулевое значение как true) возвращает количество смен, это имеет смысл. Это также означает, что он работает, даже если установлено более одного бита - результат всегда для самого старшего бита.

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

ПРИМЕЧАНИЕ: При использовании 64-битных значений будьте предельно осторожны при использовании сверхчувственных алгоритмов; многие из них работают корректно только для 32-битных значений.

Answer 4

Это должно быть молниеносно:

int msb(unsigned int v) {
  static const int pos[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};
  v |= v >> 1;
  v |= v >> 2;
  v |= v >> 4;
  v |= v >> 8;
  v |= v >> 16;
  v = (v >> 1) + 1;
  return pos[(v * 0x077CB531UL) >> 27];
}

Answer 5

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

Я понимаю, что в CPU уже есть автоматический бит-детектор, используемый для преобразования целых чисел в плавающие! Так что используйте это.

double ff=(double)(v|1);
return ((*(1+(uint32_t *)&ff))>>20)-1023;  // assumes x86 endianness

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

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

---

Чтобы сделать это безопасно, без неопределенного поведения в C ++ или C, используйте memcpy вместо приведения указателя для определения типа. Компиляторы знают, как эффективно встроить его.

// static_assert(sizeof(double) == 2 * sizeof(uint32_t), "double isn't 8-byte IEEE binary64");
// and also static_assert something about FLT_ENDIAN?

double ff=(double)(v|1);

uint32_t tmp;
memcpy(&tmp, ((const char*)&ff)+sizeof(uint32_t), sizeof(uint32_t));
return (tmp>>20)-1023;

Или в C99 и позже, используйте union {double d; uint32_t u[2];};. Но обратите внимание, что в C ++ объединение типов объединения поддерживается только в некоторых компиляторах как расширение, но не в ISO C ++.

---

Это обычно будет медленнее, чем встроенная в платформу встроенная команда подсчета ведущих нулей, но переносимый ISO C не имеет такой функции. В некоторых процессорах также отсутствует инструкция подсчета с начальным нулем, но некоторые из них могут эффективно преобразовывать целые числа в double. Однако наложение типа на битовую комбинацию FP обратно в целое число может быть медленным (например, в PowerPC это требует сохранения / перезагрузки и, как правило, приводит к остановке загрузки при загрузке).

Этот алгоритм потенциально может быть полезен для реализаций SIMD, поскольку у меньшего количества процессоров SIMD lzcnt. x86 только получил такую ​​инструкцию с AVX512CD

Answer 6

Каз Кылхеку здесь

Я протестировал два подхода для этого над 63-битными числами (тип long long в gcc x86_64), избегая знака бита.

(мне случается, что мне нужен этот "найди старший бит", понимаешь).

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

Дерево решений (наибольший_бит_unrolled) было протестировано на 69% быстрее, за исключением случая n = 0, для которого бинарный поиск имеет явный тест.

Специальный тест двоичного поиска для случая 0 только на 48% быстрее, чем дерево решений, которое не имеет специального теста.

Компилятор, машина: (GCC 4.5.2, -O3, x86-64, 2867 МГц Intel Core i5).

int highest_bit_unrolled(long long n)
{
  if (n & 0x7FFFFFFF00000000) {
    if (n & 0x7FFF000000000000) {
      if (n & 0x7F00000000000000) {
        if (n & 0x7000000000000000) {
          if (n & 0x4000000000000000)
            return 63;
          else
            return (n & 0x2000000000000000) ? 62 : 61;
        } else {
          if (n & 0x0C00000000000000)
            return (n & 0x0800000000000000) ? 60 : 59;
          else
            return (n & 0x0200000000000000) ? 58 : 57;
        }
      } else {
        if (n & 0x00F0000000000000) {
          if (n & 0x00C0000000000000)
            return (n & 0x0080000000000000) ? 56 : 55;
          else
            return (n & 0x0020000000000000) ? 54 : 53;
        } else {
          if (n & 0x000C000000000000)
            return (n & 0x0008000000000000) ? 52 : 51;
          else
            return (n & 0x0002000000000000) ? 50 : 49;
        }
      }
    } else {
      if (n & 0x0000FF0000000000) {
        if (n & 0x0000F00000000000) {
          if (n & 0x0000C00000000000)
            return (n & 0x0000800000000000) ? 48 : 47;
          else
            return (n & 0x0000200000000000) ? 46 : 45;
        } else {
          if (n & 0x00000C0000000000)
            return (n & 0x0000080000000000) ? 44 : 43;
          else
            return (n & 0x0000020000000000) ? 42 : 41;
        }
      } else {
        if (n & 0x000000F000000000) {
          if (n & 0x000000C000000000)
            return (n & 0x0000008000000000) ? 40 : 39;
          else
            return (n & 0x0000002000000000) ? 38 : 37;
        } else {
          if (n & 0x0000000C00000000)
            return (n & 0x0000000800000000) ? 36 : 35;
          else
            return (n & 0x0000000200000000) ? 34 : 33;
        }
      }
    }
  } else {
    if (n & 0x00000000FFFF0000) {
      if (n & 0x00000000FF000000) {
        if (n & 0x00000000F0000000) {
          if (n & 0x00000000C0000000)
            return (n & 0x0000000080000000) ? 32 : 31;
          else
            return (n & 0x0000000020000000) ? 30 : 29;
        } else {
          if (n & 0x000000000C000000)
            return (n & 0x0000000008000000) ? 28 : 27;
          else
            return (n & 0x0000000002000000) ? 26 : 25;
        }
      } else {
        if (n & 0x0000000000F00000) {
          if (n & 0x0000000000C00000)
            return (n & 0x0000000000800000) ? 24 : 23;
          else
            return (n & 0x0000000000200000) ? 22 : 21;
        } else {
          if (n & 0x00000000000C0000)
            return (n & 0x0000000000080000) ? 20 : 19;
          else
            return (n & 0x0000000000020000) ? 18 : 17;
        }
      }
    } else {
      if (n & 0x000000000000FF00) {
        if (n & 0x000000000000F000) {
          if (n & 0x000000000000C000)
            return (n & 0x0000000000008000) ? 16 : 15;
          else
            return (n & 0x0000000000002000) ? 14 : 13;
        } else {
          if (n & 0x0000000000000C00)
            return (n & 0x0000000000000800) ? 12 : 11;
          else
            return (n & 0x0000000000000200) ? 10 : 9;
        }
      } else {
        if (n & 0x00000000000000F0) {
          if (n & 0x00000000000000C0)
            return (n & 0x0000000000000080) ? 8 : 7;
          else
            return (n & 0x0000000000000020) ? 6 : 5;
        } else {
          if (n & 0x000000000000000C)
            return (n & 0x0000000000000008) ? 4 : 3;
          else
            return (n & 0x0000000000000002) ? 2 : (n ? 1 : 0);
        }
      }
    }
  }
}

int highest_bit(long long n)
{
  const long long mask[] = {
    0x000000007FFFFFFF,
    0x000000000000FFFF,
    0x00000000000000FF,
    0x000000000000000F,
    0x0000000000000003,
    0x0000000000000001
  };
  int hi = 64;
  int lo = 0;
  int i = 0;

  if (n == 0)
    return 0;

  for (i = 0; i < sizeof mask / sizeof mask[0]; i++) {
    int mi = lo + (hi - lo) / 2;

    if ((n >> mi) != 0)
      lo = mi;
    else if ((n & (mask[i] << lo)) != 0)
      hi = mi;
  }

  return lo + 1;
}

Программа быстрого и грязного теста:

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

int highest_bit_unrolled(long long n);
int highest_bit(long long n);

main(int argc, char **argv)
{
  long long n = strtoull(argv[1], NULL, 0);
  int b1, b2;
  long i;
  clock_t start = clock(), mid, end;

  for (i = 0; i < 1000000000; i++)
    b1 = highest_bit_unrolled(n);

  mid = clock();

  for (i = 0; i < 1000000000; i++)
    b2 = highest_bit(n);

  end = clock();

  printf("highest bit of 0x%llx/%lld = %d, %d\n", n, n, b1, b2);

  printf("time1 = %d\n", (int) (mid - start));
  printf("time2 = %d\n", (int) (end - mid));
  return 0;
}

При использовании только -O2 разница становится больше. Дерево решений почти в четыре раза быстрее.

Я также сравнил с наивным кодом сдвига битов:

int highest_bit_shift(long long n)
{
  int i = 0;
  for (; n; n >>= 1, i++)
    ; /* empty */
  return i;
}

Это быстро только для небольших чисел, как и следовало ожидать. Определяя, что старший бит равен 1 для n == 1, он показал более 80% скорости. Однако для половины случайно выбранных чисел в 63-битном пространстве установлен 63-й бит!

На входе 0x3FFFFFFFFFFFFFFF версия дерева решений немного быстрее, чем на 1, и показывает, что она на 1120% быстрее (в 12,2 раза), чем битрейтер.

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

Answer 7

А как же

int highest_bit(unsigned int a) {
    int count;
    std::frexp(a, &count);
    return count - 1;
}

Answer 8

Хотя я, вероятно, использовал бы этот метод только в том случае, если бы мне абсолютно требовалась максимальная производительность (например, для написания какого-либо ИИ настольной игры с использованием битбордов), наиболее эффективным решением является использование встроенного ASM. См. Раздел «Оптимизация» в этом блоге , где приведен код с объяснением.

[...], инструкция по сборке bsrl вычисляет позицию старшего значащего бита. Таким образом, мы могли бы использовать это asm утверждение:

asm ("bsrl %1, %0" 
     : "=r" (position) 
     : "r" (number));

Answer 9

unsigned int
msb32(register unsigned int x)
{
        x |= (x >> 1);
        x |= (x >> 2);
        x |= (x >> 4);
        x |= (x >> 8);
        x |= (x >> 16);
        return(x & ~(x >> 1));
}

1 регистр, 13 инструкций. Хотите верьте, хотите нет, но обычно это быстрее, чем указанная выше инструкция BSR, которая работает за линейное время. Это логарифмическое время.

С http://aggregate.org/MAGIC/#Most%20Significant%201%20Bit

Answer 10

Вот некоторые (простые) тесты алгоритмов, которые в настоящее время приведены на этой странице ...

Алгоритмы не были проверены на всех входах unsigned int; так что сначала проверьте это, прежде чем вслепую что-то использовать;)

На моей машине лучше всего работают clz (__builtin_clz) и asm. Asm кажется даже быстрее, чем CLZ ... но это может быть из-за простого теста ...

//////// go.c ///////////////////////////////
// compile with:  gcc go.c -o go -lm
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/***************** math ********************/

#define POS_OF_HIGHESTBITmath(a) /* 0th position is the Least-Signif-Bit */    \
  ((unsigned) log2(a))         /* thus: do not use if a <= 0 */  

#define NUM_OF_HIGHESTBITmath(a) ((a)               \
                  ? (1U << POS_OF_HIGHESTBITmath(a))    \
                  : 0)



/***************** clz ********************/

unsigned NUM_BITS_U = ((sizeof(unsigned) << 3) - 1);
#define POS_OF_HIGHESTBITclz(a) (NUM_BITS_U - __builtin_clz(a)) /* only works for a != 0 */

#define NUM_OF_HIGHESTBITclz(a) ((a)                    \
                 ? (1U << POS_OF_HIGHESTBITclz(a))  \
                 : 0)


/***************** i2f ********************/

double FF;
#define POS_OF_HIGHESTBITi2f(a) (FF = (double)(ui|1), ((*(1+(unsigned*)&FF))>>20)-1023)


#define NUM_OF_HIGHESTBITi2f(a) ((a)                    \
                 ? (1U << POS_OF_HIGHESTBITi2f(a))  \
                 : 0)




/***************** asm ********************/

unsigned OUT;
#define POS_OF_HIGHESTBITasm(a) (({asm("bsrl %1,%0" : "=r"(OUT) : "r"(a));}), OUT)

#define NUM_OF_HIGHESTBITasm(a) ((a)                    \
                 ? (1U << POS_OF_HIGHESTBITasm(a))  \
                 : 0)




/***************** bitshift1 ********************/

#define NUM_OF_HIGHESTBITbitshift1(a) (({   \
  OUT = a;                  \
  OUT |= (OUT >> 1);                \
  OUT |= (OUT >> 2);                \
  OUT |= (OUT >> 4);                \
  OUT |= (OUT >> 8);                \
  OUT |= (OUT >> 16);               \
      }), (OUT & ~(OUT >> 1)))          \



/***************** bitshift2 ********************/
int POS[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};

#define POS_OF_HIGHESTBITbitshift2(a) (({   \
  OUT = a;                  \
  OUT |= OUT >> 1;              \
  OUT |= OUT >> 2;              \
  OUT |= OUT >> 4;              \
  OUT |= OUT >> 8;              \
  OUT |= OUT >> 16;             \
  OUT = (OUT >> 1) + 1;             \
      }), POS[(OUT * 0x077CB531UL) >> 27])

#define NUM_OF_HIGHESTBITbitshift2(a) ((a)              \
                       ? (1U << POS_OF_HIGHESTBITbitshift2(a)) \
                       : 0)



#define LOOPS 100000000U

int main()
{
  time_t start, end;
  unsigned ui;
  unsigned n;

  /********* Checking the first few unsigned values (you'll need to check all if you want to use an algorithm here) **************/
  printf("math\n");
  for (ui = 0U; ui < 18; ++ui)
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITmath(ui));

  printf("\n\n");

  printf("clz\n");
  for (ui = 0U; ui < 18U; ++ui)
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITclz(ui));

  printf("\n\n");

  printf("i2f\n");
  for (ui = 0U; ui < 18U; ++ui)
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITi2f(ui));

  printf("\n\n");

  printf("asm\n");
  for (ui = 0U; ui < 18U; ++ui) {
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITasm(ui));
  }

  printf("\n\n");

  printf("bitshift1\n");
  for (ui = 0U; ui < 18U; ++ui) {
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITbitshift1(ui));
  }

  printf("\n\n");

  printf("bitshift2\n");
  for (ui = 0U; ui < 18U; ++ui) {
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITbitshift2(ui));
  }

  printf("\n\nPlease wait...\n\n");


  /************************* Simple clock() benchmark ******************/
  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITmath(ui);
  end = clock();
  printf("math:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITclz(ui);
  end = clock();
  printf("clz:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITi2f(ui);
  end = clock();
  printf("i2f:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITasm(ui);
  end = clock();
  printf("asm:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITbitshift1(ui);
  end = clock();
  printf("bitshift1:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITbitshift2(ui);
  end = clock();
  printf("bitshift2\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  printf("\nThe lower, the better. Take note that a negative exponent is good! ;)\n");

  return EXIT_SUCCESS;
}