Найдите старший значащий бит (крайним левым), который установлен в небольшом массиве

Хм, ваш тег указывает на 32-битный, но похоже, что вы используете 16-битные значения. Если вы имели в виду 32 бита, то я думаю, что ответ для 0x00a1 должен быть 24, а не 8.

Предполагая, что вы ищете индекс битов MSB с левой стороны и знаете, что будете иметь дело только с uint32_t, вот очевидный и простой алгоритм:

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

int main()
{
    uint32_t test_value = 0x00a1;
    int i;

    for (i=0; i<32; ++i)
    {
        if (test_value & (0x80000000 >> i))
        {
            printf("i = %d\n", i);
            exit(0);
        }
    }

    return 0;
}

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

int msb( unsigned char x);  // prototype for function that returns 
                            //  most significant bit set

unsigned char* p;

for (p = arr + num_elements; p != arr;) {
    --p;
    if (*p != 0) break;
}

// p is with pointing to the last byte that has a bit set, or
//  it's pointing to the first byte in the array

if (*p) {
    return ((p - arr) * 8) + msb( *p);
}

// what do you want to return if no bits are set?
return -1;

Я оставлю читателю возможность придумать подходящую функцию msb(), а также оптимизацию для работы с массивами данных размером int или long long.

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

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

Ознакомьтесь с некоторыми реализациями здесь (в разделе «Целочисленный журнал с основанием 2»). Если вы используете GCC, ознакомьтесь с функциями __ builtin_clz и __ builtin_clzl (которые делают это для ненулевых целых чисел без знака и длинных чисел без знака, соответственно). «Clz» означает «подсчитывать ведущие нули», что является еще одним способом описания той же проблемы.

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

Найдите в инструкции x86 asm BSR (битовое сканирование в обратном направлении) как можно быстрее это сделать. Из документа Intel: Ищет в исходном операнде (второй операнд) старший значащий бит набора (1 бит). Если найден старший значащий 1 бит, его битовый индекс сохраняется в операнде назначения (первый операнд).

Два лучших известных мне способа сделать это на чистом C:

Сначала линейный поиск в массиве байтов/слов, чтобы найти первый ненулевой байт/слово, затем развёрнутый бинарный поиск найденного байта/слова.

if (b>=0x10)
  if (b>=0x40)
    if (b>=0x80) return 0;
    else return 1;
  else
    if (b>=0x20) return 2;
    else return 3;
else
  if (b>=0x4)
    if (b>=0x8) return 4;
    else return 5;
  else
    if (b>=0x2) return 6;
    else return 7;

3 (BTW это log2(8)) условных перехода для получения ответа. На современных машинах x86 последний будет оптимизирован до условного mov.

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

Смежная тема, которую вы, возможно, захотите изучить, - целочисленные функции log2. Насколько я помню, в ffmpeg есть хорошая реализация.

Edit: Вы можете превратить приведенный выше двоичный поиск в двоичный поиск без ветвления, но я не уверен, будет ли это более эффективно в данном случае...