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

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

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

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

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

Изменить: как насчет решения, которое работает как на 32-разрядных, так и на 64-разрядных архитектурах (многие листинги кода кажутся такими, как будто они работают только на 32-разрядных int).

GCC имеет :

 - Встроенная функция: int __builtin_clz (unsigned int x)
     Возвращает количество ведущих 0-битов в X, начиная не более
     значимая битовая позиция. Если X равен 0, результат не определен.

 - Встроенная функция: int __builtin_clzl (беззнаковое длинное)
     Подобно `__builtin_clz ', за исключением того, что тип аргумента -` беззнаковый
     длинный'.

 - Встроенная функция: int __builtin_clzll (unsigned long long)
     Подобно `__builtin_clz ', за исключением того, что тип аргумента -` беззнаковый
     долго долго'.

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

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

Чтобы избежать этого, вы можете использовать другой вариант - встроенные функции для конкретной платформы, такие как ARM GCC __clz(заголовок не требуется) или x86 _lzcnt_u32на процессорах, поддерживающих 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 имеет значение? )

Предполагая, что вы работаете на 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), что он значительно быстрее, чем код цикла.

Поскольку 2 ^ N является целым числом с установленным только N-м битом (1 << N), поиск позиции (N) самого высокого установленного бита является целым числом с основанием 2 этого целого числа.

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

unsigned int v;
unsigned r = 0;

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

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

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

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

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

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

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

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

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 ++ каламбур типа union поддерживается только некоторыми компиляторами в качестве расширения, но не в ISO C ++.

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

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

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

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

(Видите ли, мне для чего-то нужен этот "самый высокий бит".)

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

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

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

Компилятор, машина: (GCC 4.5.2, -O3, x86-64, 2867 Mhz 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, а также попробую сочетание входных данных, а не повторение с одним и тем же числом. Могут быть некоторые предсказания залипания ветвления и, возможно, некоторые нереалистичные сценарии кеширования, которые делают его искусственно быстрее при повторениях.

Что о

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

?

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

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

Алгоритмы не тестировались на всех входах 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;
}

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

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

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

Мне нужна была процедура для этого, и перед поиском в Интернете (и нахождением этой страницы) я придумал собственное решение, основанное на бинарном поиске. Хотя уверен, что кто-то делал это раньше! Он работает в постоянное время и может быть быстрее, чем опубликованное "очевидное" решение, хотя я не делаю никаких серьезных заявлений, просто публикую его для интереса.

int highest_bit(unsigned int a) {
  static const unsigned int maskv[] = { 0xffff, 0xff, 0xf, 0x3, 0x1 };
  const unsigned int *mask = maskv;
  int l, h;

  if (a == 0) return -1;

  l = 0;
  h = 32;

  do {
    int m = l + (h - l) / 2;

    if ((a >> m) != 0) l = m;
    else if ((a & (*mask << l)) != 0) h = m;

    mask++;
  } while (l < h - 1);

  return l;
}

это своего рода бинарный поиск, он работает со всеми (беззнаковыми!) целыми типами

#include <climits>
#define UINT (unsigned int)
#define UINT_BIT (CHAR_BIT*sizeof(UINT))

int msb(UINT x)
{
    if(0 == x)
        return -1;

    int c = 0;

    for(UINT i=UINT_BIT>>1; 0<i; i>>=1)
    if(static_cast<UINT>(x >> i))
    {
        x >>= i;
        c |= i;
    }

    return c;
}

сделать завершенным:

#include <climits>
#define UINT unsigned int
#define UINT_BIT (CHAR_BIT*sizeof(UINT))

int lsb(UINT x)
{
    if(0 == x)
        return -1;

    int c = UINT_BIT-1;

    for(UINT i=UINT_BIT>>1; 0<i; i>>=1)
    if(static_cast<UINT>(x << i))
    {
        x <<= i;
        c ^= i;
    }

    return c;
}

Здесь есть слишком сложные ответы. Технику Debruin следует использовать только тогда, когда вход уже является степенью двойки, иначе есть способ лучше. При мощности двух входов Debruin является самым быстрым, даже быстрее, чем _BitScanReverseна любом процессоре, который я тестировал. Однако в общем случае _BitScanReverse(или независимо от того, что внутреннее свойство вызывается в вашем компиляторе) является самым быстрым (хотя на некоторых процессорах он может быть микрокодирован).

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

u8  inline log2 (u32 val)  {
    u8  k = 0;
    if (val > 0x0000FFFFu) { val >>= 16; k  = 16; }
    if (val > 0x000000FFu) { val >>= 8;  k |= 8;  }
    if (val > 0x0000000Fu) { val >>= 4;  k |= 4;  }
    if (val > 0x00000003u) { val >>= 2;  k |= 2;  }
    k |= (val & 2) >> 1;
    return k;
}

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

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

u8 kTableLog2[256] = {
0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
};

u8 log2_table(u32 val)  {
    u8  k = 0;
    if (val > 0x0000FFFFuL) { val >>= 16; k  = 16; }
    if (val > 0x000000FFuL) { val >>=  8; k |=  8; }
    k |= kTableLog2[val]; // precompute the Log2 of the low byte

    return k;
}

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

Как указано в приведенных выше ответах, существует несколько способов определить наиболее значимый бит. Однако, как также указывалось, методы, вероятно, будут уникальными для 32-битных или 64-битных регистров. На странице битхаков stanford.edu представлены решения, которые работают как для 32-битных, так и для 64-битных вычислений. Немного поработав, их можно объединить, чтобы обеспечить надежный кросс-архитектурный подход к получению MSB. Решение, к которому я пришел, скомпилированное / работающее на 64- и 32-битных компьютерах, было:

#if defined(__LP64__) || defined(_LP64)
# define BUILD_64   1
#endif

#include <stdio.h>
#include <stdint.h>  /* for uint32_t */

/* CHAR_BIT  (or include limits.h) */
#ifndef CHAR_BIT
#define CHAR_BIT  8
#endif  /* CHAR_BIT */

/* 
 * Find the log base 2 of an integer with the MSB N set in O(N)
 * operations. (on 64bit & 32bit architectures)
 */
int
getmsb (uint32_t word)
{
    int r = 0;
    if (word < 1)
        return 0;
#ifdef BUILD_64
    union { uint32_t u[2]; double d; } t;  // temp
    t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
    t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = word;
    t.d -= 4503599627370496.0;
    r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF;
#else
    while (word >>= 1)
    {
        r++;
    }
#endif  /* BUILD_64 */
    return r;
}

Версия на C с использованием последовательного приближения:

unsigned int getMsb(unsigned int n)
{
  unsigned int msb  = sizeof(n) * 4;
  unsigned int step = msb;
  while (step > 1)
 {
    step /=2;
    if (n>>msb)
     msb += step;
   else
     msb -= step;
 }
  if (n>>msb)
    msb++;
  return (msb - 1);
}

Преимущество: время работы постоянно, независимо от предоставленного числа, поскольку количество петель всегда одинаково. (4 цикла при использовании "unsigned int")

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

Большинство решений (особенно те, которые используют какую-то схему двоичного поиска или наивный подход, который выполняет линейное сканирование справа налево), похоже, игнорируют тот факт, что для произвольных двоичных чисел не так много, которые начинаются с очень длинной последовательности нули. Фактически, для любой разрядности половина всех целых чисел начинается с 1, а четверть из них - с 01 . Видишь, к чему я клоню? Мой аргумент состоит в том, что линейное сканирование, начиная с позиции наиболее значимого бита до наименее значимого (слева направо), не является таким «линейным», как могло бы показаться на первый взгляд.

Можно показать ¹ , что для любой разрядности среднее количество битов, которые необходимо протестировать, не превышает 2. Это переводится в амортизированную временную сложность O (1) по отношению к количеству бит (!) ,

Конечно, наихудший случай по-прежнему O (n) , хуже, чем O (log (n)), который вы получаете с подходами, подобными двоичному поиску, но поскольку наихудших случаев так мало, они незначительны для большинства приложений ( Обновить : not very: Их может быть немного, но они могут возникать с большой вероятностью - см. Обновление ниже).

Вот "наивный" подход, который я придумал, который, по крайней мере, на моей машине превосходит большинство других подходов (схемы двоичного поиска для 32-битных целых чисел всегда требуют log ₂ (32) = 5 шагов, тогда как этот глупый алгоритм требует меньше чем 2 в среднем) - извините, что это C ++, а не чистый C:

template <typename T>
auto msb(T n) -> int
{
    static_assert(std::is_integral<T>::value && !std::is_signed<T>::value,
        "msb<T>(): T must be an unsigned integral type.");

    for (T i = std::numeric_limits<T>::digits - 1, mask = 1 << i; i >= 0; --i, mask >>= 1)
    {
        if ((n & mask) != 0)
            return i;
    }

    return 0;
}

Обновление : в то время как то, что я написал здесь, совершенно верно для произвольных целых чисел, где каждая комбинация битов одинаково вероятна (мой тест скорости просто измерял, сколько времени потребовалось для определения MSB для всех 32-битных целых чисел), реальных целых чисел для Какая такая функция будет вызываться, обычно следуют другому шаблону: в моем коде, например, эта функция используется для определения того, является ли размер объекта степенью 2, или для нахождения следующей степени 2, большей или равной размер объекта . Я предполагаю, что большинство приложений, использующих MSB, используют числа, которые намного меньше максимального числа, которое может представлять целое число (размеры объектов редко используют все биты в size_t). В этом случае мое решение фактически будет работать хуже, чем подход бинарного поиска, поэтому последний, вероятно, следует предпочесть, хотя мое решение будет быстрее перебирать все целые числа.
TL; DR: Реальные целые числа, вероятно, будут иметь тенденцию к худшему случаю этого простого алгоритма, что в конечном итоге ухудшит его работу - несмотря на то, что он амортизирует O (1) для действительно произвольных целых чисел.

¹ Аргумент выглядит следующим образом (черновик): пусть n будет количеством бит (разрядность). Всего имеется 2 ⁿ целых чисел, которые могут быть представлены n битами. Есть 2 ^{n - 1} целых чисел, начинающихся с 1 (первая фиксированная 1 , оставшиеся n - 1 бит могут быть любыми). Эти целые числа требуют только одного взаимодействия цикла для определения MSB. Кроме того, есть 2 ^{n - 2} целых числа, начинающихся с 01 , требующих 2 итераций, 2 ^{n - 3} целых чисел, начинающихся с 001 , требующих 3 итераций, и так далее.

Если мы просуммируем все необходимые итерации для всех возможных целых чисел и разделим их на 2 ⁿ , общее количество целых чисел, мы получим среднее количество итераций, необходимых для определения MSB для n- битных целых чисел:

(1 * 2 ^{п - 1} + 2 * 2 ^{п - 2} + 3 * 2 ^{п - 3} + ... + п) / 2 ^п

Эта серия средних итераций фактически сходится и имеет предел 2 для n в сторону бесконечности.

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

c99дал нам log2. Это устраняет необходимость во всех специальных log2реализациях соуса, которые вы видите на этой странице. Вы можете использовать стандартную log2реализацию следующим образом:

const auto n = 13UL;
const auto Index = (unsigned long)log2(n);

printf("MSB is: %u\n", Index); // Prints 3 (zero offset)

nИз 0ULпотребностей, остерегаться , а также, потому что:

-∞ возвращается и FE_DIVBYZERO поднимается

Я написал пример с этой проверкой , что произвольно устанавливает Indexдля ULONG_MAXздесь: https://ideone.com/u26vsi

зрительно-студияследствие единственного ответа ephemient gcc :

const auto n = 13UL;
unsigned long Index;

_BitScanReverse(&Index, n);
printf("MSB is: %u\n", Index); // Prints 3 (zero offset)

В документации_BitScanReverse указано, что Indexэто:

Загружен с битовой позицией первого установленного бита (1), найденного

На практике я обнаружил, что if nis 0ULthat Indexимеет значение0UL , как и для nof 1UL. Но единственное , что гарантировано в документации в случае nиз 0ULчто возвращение:

0, если набор битов не найден

Таким образом, аналогично предпочтительной log2реализации, описанной выше, Indexв этом случае должен быть проверен возврат, установленный на отмеченное значение. Я снова написал пример использования ULONG_MAXэтого значения флага здесь: http://rextester.com/GCU61409

Подумайте о побитовых операторах.

Я неправильно понял вопрос в первый раз. Вы должны создать int с установленным крайним левым битом (остальные равны нулю). Предполагая, что для cmp установлено это значение:

position = sizeof(int)*8
while(!(n & cmp)){ 
   n <<=1;
   position--;
}

Расширяя тест Джоша ... можно улучшить clz следующим образом

/***************** clz2 ********************/

#define NUM_OF_HIGHESTBITclz2(a) ((a)                              \
                  ? (((1U) << (sizeof(unsigned)*8-1)) >> __builtin_clz(a)) \
                  : 0)

По поводу asm: обратите внимание, что есть bsr и bsrl (это "длинная" версия). нормальный может быть немного быстрее.

Обратите внимание, что вы пытаетесь вычислить целое число log2 целого числа,

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

unsigned int
Log2(unsigned long x)
{
    unsigned long n = x;
    int bits = sizeof(x)*8;
    int step = 1; int k=0;
    for( step = 1; step < bits; ) {
        n |= (n >> step);
        step *= 2; ++k;
    }
    //printf("%ld %ld\n",x, (x - (n >> 1)) );
    return(x - (n >> 1));
}

Обратите внимание, что вы можете пытаться искать более 1 бита за раз.

unsigned int
Log2_a(unsigned long x)
{
    unsigned long n = x;
    int bits = sizeof(x)*8;
    int step = 1;
    int step2 = 0;
    //observe that you can move 8 bits at a time, and there is a pattern...
    //if( x>1<<step2+8 ) { step2+=8;
        //if( x>1<<step2+8 ) { step2+=8;
            //if( x>1<<step2+8 ) { step2+=8;
            //}
        //}
    //}
    for( step2=0; x>1L<<step2+8; ) {
        step2+=8;
    }
    //printf("step2 %d\n",step2);
    for( step = 0; x>1L<<(step+step2); ) {
        step+=1;
        //printf("step %d\n",step+step2);
    }
    printf("log2(%ld) %d\n",x,step+step2);
    return(step+step2);
}

Этот подход использует двоичный поиск

unsigned int
Log2_b(unsigned long x)
{
    unsigned long n = x;
    unsigned int bits = sizeof(x)*8;
    unsigned int hbit = bits-1;
    unsigned int lbit = 0;
    unsigned long guess = bits/2;
    int found = 0;

    while ( hbit-lbit>1 ) {
        //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        //when value between guess..lbit
        if( (x<=(1L<<guess)) ) {
           //printf("%ld < 1<<%d %ld\n",x,guess,1L<<guess);
            hbit=guess;
            guess=(hbit+lbit)/2;
            //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        }
        //when value between hbit..guess
        //else
        if( (x>(1L<<guess)) ) {
            //printf("%ld > 1<<%d %ld\n",x,guess,1L<<guess);
            lbit=guess;
            guess=(hbit+lbit)/2;
            //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        }
    }
    if( (x>(1L<<guess)) ) ++guess;
    printf("log2(x%ld)=r%d\n",x,guess);
    return(guess);
}

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

unsigned int
Log2_c(unsigned long x)
{
    unsigned long v = x;
    unsigned int bits = sizeof(x)*8;
    unsigned int step = bits;
    unsigned int res = 0;
    for( step = bits/2; step>0; )
    {
        //printf("log2(%ld) v %d >> step %d = %ld\n",x,v,step,v>>step);
        while ( v>>step ) {
            v>>=step;
            res+=step;
            //printf("log2(%ld) step %d res %d v>>step %ld\n",x,step,res,v);
        }
        step /= 2;
    }
    if( (x>(1L<<res)) ) ++res;
    printf("log2(x%ld)=r%ld\n",x,res);
    return(res);
}

И поскольку вы захотите проверить это,

int main()
{
    unsigned long int x = 3;
    for( x=2; x<1000000000; x*=2 ) {
        //printf("x %ld, x+1 %ld, log2(x+1) %d\n",x,x+1,Log2(x+1));
        printf("x %ld, x+1 %ld, log2_a(x+1) %d\n",x,x+1,Log2_a(x+1));
        printf("x %ld, x+1 %ld, log2_b(x+1) %d\n",x,x+1,Log2_b(x+1));
        printf("x %ld, x+1 %ld, log2_c(x+1) %d\n",x,x+1,Log2_c(x+1));
    }
    return(0);
}

Ввод этого, поскольку это «еще один» подход, кажется, отличается от других, уже приведенных.

возвращается, -1если x==0, в противном случаеfloor( log2(x)) (максимальный результат 31)

Уменьшите проблему с 32 до 4 бит, затем используйте таблицу. Возможно, неэлегантно, но прагматично.

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

Чтобы сделать его более компактным, вместо этого можно было бы использовать цикл для уменьшения, добавляя каждый раз 4 к r, максимум 7 итераций. Или какой-нибудь гибрид, например (для 64 бит): цикл уменьшить до 8, тест уменьшить до 4.

int log2floor( unsigned x ){
   static const signed char wtab[16] = {-1,0,1,1, 2,2,2,2, 3,3,3,3,3,3,3,3};
   int r = 0;
   unsigned xk = x >> 16;
   if( xk != 0 ){
       r = 16;
       x = xk;
   }
   // x is 0 .. 0xFFFF
   xk = x >> 8;
   if( xk != 0){
       r += 8;
       x = xk;
   }
   // x is 0 .. 0xFF
   xk = x >> 4;
   if( xk != 0){
       r += 4;
       x = xk;
   }
   // now x is 0..15; x=0 only if originally zero.
   return r + wtab[x];
}

Ого, это было много ответов. Я не сожалею, что отвечу на старый вопрос.

int result = 0;//could be a char or int8_t instead
if(value){//this assumes the value is 64bit
    if(0xFFFFFFFF00000000&value){  value>>=(1<<5); result|=(1<<5);  }//if it is 32bit then remove this line
    if(0x00000000FFFF0000&value){  value>>=(1<<4); result|=(1<<4);  }//and remove the 32msb
    if(0x000000000000FF00&value){  value>>=(1<<3); result|=(1<<3);  }
    if(0x00000000000000F0&value){  value>>=(1<<2); result|=(1<<2);  }
    if(0x000000000000000C&value){  value>>=(1<<1); result|=(1<<1);  }
    if(0x0000000000000002&value){  result|=(1<<0);  }
}else{
  result=-1;
}

Этот ответ очень похож на другой ... да ладно.

Код:

    // x>=1;
    unsigned func(unsigned x) {
    double d = x ;
    int p= (*reinterpret_cast<long long*>(&d) >> 52) - 1023;
    printf( "The left-most non zero bit of %d is bit %d\n", x, p);
    }

Или получите целую часть инструкции FPU FYL2X (Y * Log2 X), установив Y = 1

Другой плакат предоставил поисковую таблицу с использованием байтового поиска. Если вы хотите немного повысить производительность (за счет 32 КБ памяти вместо 256 записей поиска), вот решение, использующее 15-битную таблицу поиска на C # 7 для .NET. .

Самое интересное - это инициализация таблицы. Поскольку это относительно небольшой блок, который нам нужен на время жизни процесса, я выделяю для этого неуправляемую память, используя Marshal.AllocHGlobal. Как видите, для максимальной производительности весь пример написан как нативный:

readonly static byte[] msb_tab_15;

// Initialize a table of 32768 bytes with the bit position (counting from LSB=0)
// of the highest 'set' (non-zero) bit of its corresponding 16-bit index value.
// The table is compressed by half, so use (value >> 1) for indexing.
static MyStaticInit()
{
    var p = new byte[0x8000];

    for (byte n = 0; n < 16; n++)
        for (int c = (1 << n) >> 1, i = 0; i < c; i++)
            p[c + i] = n;

    msb_tab_15 = p;
}

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

Обратите внимание, что записи таблицы для 0единственного целого числа, для которого понятие «самый высокий установленный бит» не определено, присваивается значение -1. Это различие необходимо для правильной обработки 0-значных верхних слов в приведенном ниже коде. Без лишних слов, вот код для каждого из различных целочисленных примитивов:

ulong (64-битная) версия

/// <summary> Index of the highest set bit in 'v', or -1 for value '0' </summary>
public static int HighestOne(this ulong v)
{
    if ((long)v <= 0)
        return (int)((v >> 57) & 0x40) - 1;      // handles cases v==0 and MSB==63

    int j = /**/ (int)((0xFFFFFFFFU - v /****/) >> 58) & 0x20;
    j |= /*****/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 0x10;
    return j + msb_tab_15[v >> (j + 1)];
}

uint (32-битная) версия

/// <summary> Index of the highest set bit in 'v', or -1 for value '0' </summary>
public static int HighestOne(uint v)
{
    if ((int)v <= 0)
        return (int)((v >> 26) & 0x20) - 1;     // handles cases v==0 and MSB==31

    int j = (int)((0x0000FFFFU - v) >> 27) & 0x10;
    return j + msb_tab_15[v >> (j + 1)];
}

Различные перегрузки для вышеперечисленных

public static int HighestOne(long v) => HighestOne((ulong)v);
public static int HighestOne(int v) => HighestOne((uint)v);
public static int HighestOne(ushort v) => msb_tab_15[v >> 1];
public static int HighestOne(short v) => msb_tab_15[(ushort)v >> 1];
public static int HighestOne(char ch) => msb_tab_15[ch >> 1];
public static int HighestOne(sbyte v) => msb_tab_15[(byte)v >> 1];
public static int HighestOne(byte v) => msb_tab_15[v >> 1];

Это законченное рабочее решение, которое обеспечивает лучшую производительность в .NET 4.7.2 для множества альтернатив, которые я сравнивал со специализированной системой тестирования производительности. Некоторые из них упомянуты ниже. Параметры теста были равномерной плотностью всех 65-битных позиций, то есть 0 ... 31/63 плюс значение 0(которое дает результат -1). Биты ниже позиции целевого индекса заполнялись случайным образом. Тесты проводились только для x64 , в режиме выпуска, с включенной JIT-оптимизацией.

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

Представленная выше версия с кодом Tab16A неизменно выигрывала во многих тестах. Этих различных кандидатов в активной рабочей / временной форме можно найти здесь , здесь и здесь .

 1 кандидат .HighestOne_Tab16A 622,496
 2 кандидата .HighestOne_Tab16C 628,234
 3 кандидата .HighestOne_Tab8A 649146
 4 кандидата .HighestOne_Tab8B 656847
 5 кандидатов. HighestOne_Tab16B 657 147
 6 кандидатов. HighestOne_Tab16D 659,650
 7 _highest_one_bit_UNMANAGED.HighestOne_U 702 900
 8 de_Bruijn.IndexOfMSB 709 672
 9 _old_2.HighestOne_Old2 715,810
10 _test_A.HighestOne8 757 188
11 _old_1.HighestOne_Old1 757,925
12 _test_A.HighestOne5 (небезопасно) 760,387
13 _test_B.HighestOne8 (небезопасно) 763 904
14 _test_A.HighestOne3 (небезопасно) 766 433
15 _test_A.HighestOne1 (небезопасно) 767 321
16 _test_A.HighestOne4 (небезопасно) 771 702
17 _test_B.HighestOne2 (небезопасно) 772,136
18 _test_B.HighestOne1 (небезопасно) 772,527
19 _test_B.HighestOne3 (небезопасно) 774,140
20 _test_A.HighestOne7 (небезопасно) 774,581
21 _test_B.HighestOne7 (небезопасно) 775 463
22 _test_A.HighestOne2 (небезопасно) 776865
23 кандидата.HighestOne_NoTab 777 698
24 _test_B.HighestOne6 (небезопасно) 779 481
25 _test_A.HighestOne6 (небезопасно) 781,553
26 _test_B.HighestOne4 (небезопасно) 785 504
27 _test_B.HighestOne5 (небезопасно) 789,797
28 _test_A.HighestOne0 (небезопасно) 809,566
29 _test_B.HighestOne0 (небезопасно) 814,990
30 _highest_one_bit.HighestOne 824,345
30 _bitarray_ext.RtlFindMostSignificantBit 894069
31 кандидат.HighestOne_Naive 898,865

Примечательно то, что ужасная производительность ntdll.dll!RtlFindMostSignificantBitvia P / Invoke:

[DllImport("ntdll.dll"), SuppressUnmanagedCodeSecurity, SecuritySafeCritical]
public static extern int RtlFindMostSignificantBit(ulong ul);

Это действительно очень плохо, потому что вот настоящая функция:

    RtlFindMostSignificantBit:
        bsr rdx, rcx  
        mov eax,0FFFFFFFFh  
        movzx ecx, dl  
        cmovne      eax,ecx  
        ret

Я не могу себе представить, насколько низкая производительность связана с этими пятью строками, поэтому виноваты штрафы за управляемый / собственный переход. Я также был удивлен тем, что при тестировании действительно предпочтение отдавалось shortтаблицам прямого поиска размером 32 КБ (и 64 КБ) (16-бит), а не 128-байтовым (и 256-байтовым) byte(8-битным) таблицам поиска. Я думал, что следующее будет более конкурентоспособным с 16-битным поиском, но последний последовательно превосходит это:

public static int HighestOne_Tab8A(ulong v)
{
    if ((long)v <= 0)
        return (int)((v >> 57) & 64) - 1;

    int j;
    j =  /**/ (int)((0xFFFFFFFFU - v) >> 58) & 32;
    j += /**/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 16;
    j += /**/ (int)((0x000000FFU - (v >> j)) >> 60) & 8;
    return j + msb_tab_8[v >> j];
}

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

const ulong N_bsf64 = 0x07EDD5E59A4E28C2,
            N_bsr64 = 0x03F79D71B4CB0A89;

readonly public static sbyte[]
bsf64 =
{
    63,  0, 58,  1, 59, 47, 53,  2, 60, 39, 48, 27, 54, 33, 42,  3,
    61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22,  4,
    62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21,
    56, 45, 25, 31, 35, 16,  9, 12, 44, 24, 15,  8, 23,  7,  6,  5,
},
bsr64 =
{
     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,
};

public static int IndexOfLSB(ulong v) =>
    v != 0 ? bsf64[((v & (ulong)-(long)v) * N_bsf64) >> 58] : -1;

public static int IndexOfMSB(ulong v)
{
    if ((long)v <= 0)
        return (int)((v >> 57) & 64) - 1;

    v |= v >> 1; v |= v >> 2;  v |= v >> 4;   // does anybody know a better
    v |= v >> 8; v |= v >> 16; v |= v >> 32;  // way than these 12 ops?
    return bsr64[(v * N_bsr64) >> 58];
}