Есть ли более эффективный способ получить длину 32-битного целого числа в байтах?

Минимальное количество бит, необходимое для хранения целого числа, составляет:

int minbits = (int)ceil( log10(n) / log10(2) ) ;

Количество байт составляет:

int minbytes = (int)ceil( log10(n) / log10(2) / 8 ) ;

может быть не лучше, чем условный тест, но, возможно, заслуживает изучения.

[РЕДАКТИРОВАТЬ] Я провел расследование; простой цикл из десяти миллионов итераций вышеперечисленного занял 918 мс, тогда как принятое решение FredOverflow заняло всего 49 мс (VC++ 2010). Таким образом, это не улучшение с точки зрения производительности, хотя может оставаться полезным, если требуется количество битов, и возможна дальнейшая оптимизация.

Паскалю Куоку и 35 другим людям, проголосовавшим за его комментарий:

"Вау! Более 10 миллионов раз... Вы имеете в виду, что если вы выжать три цикла из этого функции, вы сэкономите аж 0,03 с?»

Такой язвительный комментарий в лучшем случае груб и оскорбителен.

Оптимизация часто является совокупным результатом 3% здесь, 2% там. 3% от общей емкости — это ничего чихать. Предположим, это был почти насыщенный и непараллелизуемый этап в трубе. Предположим, что загрузка процессора увеличилась с 99% до 96%. Простая теория очередей говорит, что такое снижение загрузки ЦП сократит среднюю длину очереди более чем на 75%. [качественная (нагрузка, деленная на 1-нагрузку)]

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

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

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

Паскаль Куок должен принести извинения оригинальному плакату.

Просто чтобы проиллюстрировать, основываясь на ответе FredOverflow (отличная работа, респект и +1), распространенную ловушку, связанную с ветками на x86. Вот сборка FredOverflow, выводимая gcc:

movl    8(%ebp), %edx   #1/.5
movl    %edx, %eax      #1/.5
andl    $-16777216, %eax#1/.5
cmpl    $1, %eax        #1/.5
sbbl    %eax, %eax      #8/6
addl    $4, %eax        #1/.5
xorl    %ecx, %ecx      #1/.5
testl   $-65536, %edx   #1/.5
sete    %cl             #5
subl    %ecx, %eax      #1/.5
andl    $-256, %edx     #1/.5
sete    %dl             #5
movzbl  %dl, %edx       #1/.5
subl    %edx, %eax      #1/.5
# sum total: 29/21.5 cycles

(задержка в циклах следует читать как Prescott/Northwood)

Оптимизированная вручную сборка Паскаля Куока (также похвально):

cmpl    $255, %edi      #1/.5
setg    %al             #5
addb    $3, %al         #1/.5
cmpl    $65535, %edi    #1/.5
setle   %dl             #5
subb    %dl, %al        #1/.5
cmpl    $16777215, %edi #1/.5
setle   %dl             #5
subb    %dl, %al        #1/.5
movzbl  %al, %eax       #1/.5
# sum total: 22/18.5 cycles

Редактировать: решение FredOverflow с использованием __builtin_clz():

movl 8(%ebp), %eax   #1/.5
popl %ebp            #1.5
orb  $-1, %al        #1/.5
bsrl %eax, %eax      #16/8
sarl $3, %eax        #1/4
addl $1, %eax        #1/.5
ret
# sum total: 20/13.5 cycles

и сборка gcc для вашего кода:

movl $1, %eax        #1/.5
movl %esp, %ebp      #1/.5
movl 8(%ebp), %edx   #1/.5
cmpl $255, %edx      #1/.5
jbe  .L3             #up to 9 cycles
cmpl $65535, %edx    #1/.5
movb $2, %al         #1/.5
jbe  .L3             #up to 9 cycles
cmpl $16777216, %edx #1/.5
sbbl %eax, %eax      #8/6
addl $4, %eax        #1/.5
.L3:
ret
# sum total: 16/10 cycles - 34/28 cycles

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

Разветвления могут быть разумным выбором, в зависимости от входного распределения.

Редактировать: добавлено решение FredOverflow, использующее __builtin_clz().

Хорошо, еще одна версия. Аналогичен Фреду, но с меньшим количеством операций.

inline int len(uint32 val)
{
    return 1
        + (val > 0x000000ff)
        + (val > 0x0000ffff)
        + (val > 0x00ffffff)
    ;
}

Если битовые операции быстрее, чем сравнение на вашей целевой машине, вы можете сделать это:

inline int len(uint32 val)
{
    if(val & 0xff000000) return 4;
    if(val & 0x00ff0000) return 3;
    if(val & 0x0000ff00) return 2;
    return 1;
} 

Двоичный поиск МОЖЕТ сэкономить несколько циклов, в зависимости от архитектуры процессора.

inline int len(uint32 val)
{
    if (val & 0xffff0000) return (val & 0xff000000)? 4: 3;
    return (val & 0x0000ff00)? 2: 1;
}

Или выяснение наиболее распространенного случая может снизить среднее количество циклов, если большинство входных данных представляют собой один байт (например, при построении кодировок UTF-8, но тогда ваши точки останова не будут 32/24/). 16/8):

inline int len(uint32 val)
{
    if (val & 0xffffff00) {
       if (val & 0xffff0000) {
           if (val & 0xff000000) return 4;
           return 3;
       }
       return 2;
    }
    return 1;
}

Теперь короткий случай выполняет наименьшее количество условных тестов.

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

return 4 - (val <= 0x000000ff) - (val <= 0x0000ffff) - (val <= 0x00ffffff);

Изменение <= на & на современном процессоре ничего особо не изменит. Какая у вас целевая платформа?

Вот сгенерированный код для x86-64 с gcc -O:

    cmpl    $255, %edi
    setg    %al
    movzbl  %al, %eax
    addl    $3, %eax
    cmpl    $65535, %edi
    setle   %dl
    movzbl  %dl, %edx
    subl    %edx, %eax
    cmpl    $16777215, %edi
    setle   %dl
    movzbl  %dl, %edx
    subl    %edx, %eax

Конечно, есть инструкции по сравнению cmpl, но они выполняются с помощью setg или setle вместо условных переходов (как обычно). На современном конвейерном процессоре дорога условная ветвь, а не сравнение. Таким образом, эта версия сохраняет дорогостоящие условные ветки.

Моя попытка вручную оптимизировать сборку gcc:

    cmpl    $255, %edi
    setg    %al
    addb    $3, %al
    cmpl    $65535, %edi
    setle   %dl
    subb    %dl, %al
    cmpl    $16777215, %edi
    setle   %dl
    subb    %dl, %al
    movzbl  %al, %eax

Действительно ли у вас есть доказательства профиля того, что это серьезное узкое место в вашем приложении? Просто сделайте это наиболее очевидным способом, и только если профилирование покажет, что это проблема (в чем я сомневаюсь), попробуйте улучшить ситуацию. Скорее всего, вы получите лучшее улучшение, сократив количество вызовов этой функции, чем изменив что-то в ней.

Я провел небольшой ненаучный тест, просто измерив разницу в вызовах GetTickCount() при вызове функции в цикле от 0 до MAX_LONG раз в компиляторе VS 2010.

Вот что я увидел:

Это заняло 11497 тиков

inline int len(uint32 val)
{
    if(val <= 0x000000ff) return 1;
    if(val <= 0x0000ffff) return 2;
    if(val <= 0x00ffffff) return 3;
    return 4;
} 

В то время как это заняло 14399 тиков

inline int len(uint32 val)
{
    return 4
        - ((val & 0xff000000) == 0)
        - ((val & 0xffff0000) == 0)
        - ((val & 0xffffff00) == 0)
    ;
}

редактировать: моя идея о том, почему один был быстрее, неверна, потому что:

inline int len(uint32 val)
{
    return 1
        + (val > 0x000000ff)
        + (val > 0x0000ffff)
        + (val > 0x00ffffff)
        ;
}

Эта версия использовала только 11107 тиков. Так как + быстрее, чем - возможно? Я не уверен.

Еще быстрее был бинарный поиск с 7161 тактом

inline int len(uint32 val)
{
    if (val & 0xffff0000) return (val & 0xff000000)? 4: 3;
    return (val & 0x0000ff00)? 2: 1;
}

И самым быстрым на данный момент является использование встроенной функции MS, с 4399 тактами

#pragma intrinsic(_BitScanReverse)

inline int len2(uint32 val)
{
    DWORD index;
    _BitScanReverse(&index, val);

    return (index>>3)+1;

}

Для справки — вот код, который я использовал для профилирования:

int _tmain(int argc, _TCHAR* argv[])
{
    int j = 0;
    DWORD t1,t2;

    t1 = GetTickCount();

    for(ULONG i=0; i<-1; i++)
        j=len(i);

    t2 = GetTickCount();

    _tprintf(_T("%ld ticks %ld\n"), t2-t1, j);


    t1 = GetTickCount();

    for(ULONG i=0; i<-1; i++)
        j=len2(i);

    t2 = GetTickCount();

    _tprintf(_T("%ld ticks %ld\n"), t2-t1, j);
}

Пришлось распечатать j, чтобы предотвратить оптимизацию циклов.

В зависимости от вашей архитектуры у вас может быть более эффективное решение.

MIPS имеет инструкцию «CLZ», которая подсчитывает количество начальных нулевых битов числа. Здесь вы ищете по существу 4 - (CLZ(x)/8) (где / — целочисленное деление). PowerPC имеет эквивалентную инструкцию cntlz , а x86 имеет BSR . Это решение должно упроститься до 3-4 инструкций (не считая накладных расходов на вызовы функций) и нуля ветвлений.

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

int precalc[1<<16];
int precalchigh[1<<16];
void doprecalc()
{
    for(int i = 0; i < 1<<16; i++) {
        precalc[i] = (i < (1<<8) ? 1 : 2);
        precalchigh[i] = precalc[i] + 2;
    }
}
inline int len(uint32 val)
{
    return (val & 0xffff0000 ? precalchigh[val >> 16] : precalc[val]);
}

В некоторых системах это может быть быстрее для некоторых архитектур:

inline int len(uint32_t val) {
   return (int)( log(val) / log(256) );  // this is the log base 256 of val
}

Это также может быть немного быстрее (если сравнение занимает больше времени, чем побитовое и):

inline int len(uint32_t val) {
    if (val & ~0x00FFffFF) {
        return 4;
    if (val & ~0x0000ffFF) {
        return 3;
    }
    if (val & ~0x000000FF) {
        return 2;
    }
    return 1;

}

Если вы используете 8-битный микроконтроллер (например, 8051 или AVR), то это будет работать лучше всего:

inline int len(uint32_t val) {
    union int_char { 
          uint32_t u;
          uint8_t a[4];
    } x;
    x.u = val; // doing it this way rather than taking the address of val often prevents
               // the compiler from doing dumb things.
    if (x.a[0]) {
        return 4;
    } else if (x.a[1]) {
       return 3;
    ...

РЕДАКТИРОВАТЬ по tristopia: версия последнего варианта с учетом порядка следования байтов

int len(uint32_t val)
{
  union int_char {
        uint32_t u;
        uint8_t a[4];
  } x;
  const uint16_t w = 1;

  x.u = val;
  if( ((uint8_t *)&w)[1]) {   // BIG ENDIAN (Sparc, m68k, ARM, Power)
     if(x.a[0]) return 4;
     if(x.a[1]) return 3;
     if(x.a[2]) return 2;
  }
  else {                      // LITTLE ENDIAN (x86, 8051, ARM)
    if(x.a[3]) return 4;
    if(x.a[2]) return 3;
    if(x.a[1]) return 2;
  }
  return 1;
}

Из-за const любой достойный компилятор будет генерировать код только для правильного порядка следования байтов.