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

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

15 голосов
/ 30 августа 2010

Я бы хотел ярлык для следующей маленькой функции, где производительность очень важна (функция вызывается более 10.000.000 раз): 

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

Кто-нибудь имеет идеи ...классный трюк с битооперацией?Заранее спасибо за помощь!

Ответы [ 14 ]

1 голос
/ 30 августа 2010

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

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

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

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

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

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

1 голос
/ 30 августа 2010

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

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]);
}
1 голос
/ 30 августа 2010

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

inline int len(uint32 val)
{
    return 1
        + (val > 0x000000ff)
        + (val > 0x0000ffff)
        + (val > 0x00ffffff)
    ;
}
0 голосов
/ 16 октября 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

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

Страница:
...