Эффективное условие для увеличения размера в битах

Question

Предположим, у меня есть возрастающая последовательность целых чисел без знака C[i].По мере их увеличения, вероятно, они будут занимать все больше и больше битов.Я ищу эффективное условное выражение, основанное исключительно на двух последовательных элементах последовательности C[i] и C[i+1] (прошлые и будущие не наблюдаемые), которые будут оценивать значение true либо точно, либо приблизительно один раз за каждый раз, когда числоколичество требуемых битов увеличивается.

Очевидный (но медленный) выбор условного выражения:

if (ceil(log(C[i+1])) > ceil(log(C[i]))) ...

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

Я подозреваю, что может быть хорошее решение, включающее выражение, использующее только побитовое или и побитовое значение значений C[i+1] и C[i].Есть мысли?

Answer 1

Предположим, что ваши два числа x и y. Если они имеют одинаковый бит старшего разряда, то x ^ y меньше, чем x и y. В противном случае он выше, чем один из двух.

Так

v = x^y
if (v > x || v > y) { ...one more bit... }

Answer 2

Я думаю, вам просто нужно clz(C[i+1]) < clz(C[i]), где clz - это функция, которая возвращает количество ведущих нулей («считать начальные нули»). В некоторых семействах процессоров есть инструкция для этого (которая может быть доступна как дополнительная). Если нет, то вы должны бросить свои собственные (обычно это занимает всего несколько инструкций) - см. Восторг хакера .

Answer 3

Решение Кейта Рэндалла хорошее, но вы можете сохранить одну инструкцию xor, используя следующий код, который обрабатывает всю последовательность в O (w + n) инструкциях, где w - количество битов в слове, а n - это числоколичество элементов в последовательности.Если последовательность длинная, большинство итераций будет включать только одно сравнение, избегая одной инструкции xor.

Это достигается путем отслеживания максимальной степени двух, достигнутой следующим образом:

t = 1; // original setting

if (c[i + 1] >= t) {
  do {
    t <<= 1;
  } while (c[i + 1] >= t); // watch for overflow
  ... // conditional code here
}

Answer 4

BSR - обратное сканирование битов (386 +)

    Usage:  BSR     dest,src
    Modifies flags: ZF

    Scans source operand for first bit set.  Sets ZF if a bit is found
    set and loads the destination with an index to first set bit.  Clears
    ZF is no bits are found set.  BSF scans forward across bit pattern
    (0-n) while BSR scans in reverse (n-0).

                             Clocks                 Size
    Operands         808x  286   386   486          Bytes

    reg,reg           -     -   10+3n  6-103          3
    reg,mem           -     -   10+3n  7-104         3-7
    reg32,reg32       -     -   10+3n  6-103         3-7
    reg32,mem32       -     -   10+3n  7-104         3-7

Вам нужно два из них (на C [i] и C [i] +1) и сравнение.

Answer 5

Учитывая (я полагаю, что это происходит от Восторг Хакера ):

int hibit(unsigned int n) {
    n |= (n >>  1);
    n |= (n >>  2);
    n |= (n >>  4);
    n |= (n >>  8);
    n |= (n >> 16);
    return n - (n >> 1);
}

Ваш условный просто hibit(C[i]) != hibit(C[i+1]).

Answer 6

Количество бит увеличивается, когда значение составляет около двух единиц. Таким образом, простой тест - это значение, равное степени два, минус 1? Это можно сделать, спросив:

if  ((C[i] & (C[i]+1))==0) ...

Answer 7

Количество бит увеличивается, когда значение собирается превысить степень двух. Простой тест:

 while (C[i] >= (1<<number_of_bits)) then number_of_bits++;

Если хотите еще быстрее:

int number_of_bits = 1;
int  two_to_number_of_bits = 1<<number_of_bits ;


... your code ....

while ( C[i]>=two_to_number_of_bits )
   { number_of_bits++; 
     two_to_number_of_bits = 1<<number_of_bits ;
   }