Effective Conditional Bit Sizing

Question

Suppose I have an increasing sequence of unsigned integers C[i]. As they grow, they will probably occupy more and more bits. I am looking for an efficient conditional system based solely on two consecutive elements of a sequence C[i]and C[i+1](past and future are not observed) that will be evaluated as true or approximately once every time the number of bits required.

The obvious (but slow) choice of the conditional is:

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

as well as anything that calculates the number of leading zero bits using special cpu opcodes (much better, but still not very).

I suspect there might be a good solution involving an expression using only the bitwise and / or bitwise value, as well as the C[i+1]and values C[i]. Any thoughts?

Answer 1

Suppose your two numbers are x and y. If they have the same high order bit, then x ^ y is less than x and y. Otherwise, it is higher than one of two.

So,

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

Answer 2

, clz(C[i+1]) < clz(C[i]), clz - , ( "count leading zeroes" ). ( instrinsic). , ( ) - . Hacker Delight.

Answer 3

, , . - , , 1? , :

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

Answer 4

( , Hacker Delight):

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 5

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 6

Keith Randall , 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 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 ;
   }