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

Думайте побитовые операторы.

я неправильно понял вопрос в первый раз. Необходимо произвести интервал с крайним левым набором битов (другие обнуляют). Принятие cmp установлено на то значение:

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

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

Хотя я, вероятно, только использовал бы этот метод, если бы я абсолютно потребовал самой лучшей производительности (например, для записи своего рода AI настольной игры, включающего bitboards), то наиболее эффективное решение состоит в том, чтобы использовать встроенный ASM. Посмотрите раздел Optimisations это сообщение в блоге для кода с объяснением.

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

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

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

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

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

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

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

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

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

Принятие Вы находитесь на x86 и игре некоторое время встроенного ассемблера, Intel, обеспечивает BSR инструкция ("разрядный реверс сканирования"). Это быстро на приблизительно x86s (микрокодированный на других). Из руководства:

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

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, не изменяя вывод ни для какого другого входа.

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

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

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