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

Я сделал мини-ненаучный бенчмарк, просто измеряющий разницу в вызовах 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)
    ;
}

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

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

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

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

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

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

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

inline int len(uint32 val)
{
    if(val & 0xff000000) return 4;
    if(val & 0x00ff0000) return 3;
    if(val & 0x0000ff00) 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

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

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

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

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 любой компилятор, стоящий своей соли, будет генерировать код только для правильной конечности.

Просто чтобы проиллюстрировать, основываясь на ответе 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

(латентность, в циклах, должна быть прочитана как Прескотт / Нортвуд)

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

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

Edit: решение 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, вероятно, ничего не стоят для такой короткой функции.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Число байт равно:

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

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

[править] Я провел исследование; простой цикл из десяти миллионов итераций, описанных выше, занял 918 МС, в то время как принятое решение FredOverflow заняло всего 49 МС (VC++ 2010). Так что это не улучшение в терминах производительности, хотя может оставаться полезным, если это было количество битов, которые были необходимы, и дальнейшие оптимизации возможны.

Если я правильно помню 80x86 asm, я бы сделал что-то вроде:

  ; Assume value in EAX; count goes into ECX
  cmp eax,16777215 ; Carry set if less
  sbb ecx,ecx      ; Load -1 if less, 0 if greater
  cmp eax,65535
  sbb ecx,0        ; Subtract 1 if less; 0 if greater
  cmp eax,255
  sbb ecx,-4       ; Add 3 if less, 4 if greater

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