Efficient conditional for increasing size in bits

Question

Suppose I have an increasing sequence of unsigned integers C[i]. As they increase, it's likely that they will occupy increasingly many bits. I'm looking for an efficient conditional, based purely on two consecutive elements of the sequence C[i] and C[i+1] (past and future ones are not observable), that will evaluate to true either exactly or approximately once for every time the number of bits required increases.

An obvious (but slow) choice of conditional is:

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

and likewise anything that computes the number of leading zero bits using special cpu opcodes (much better but still not great).

I suspect there may be a nice solution involving an expression using just bitwise or and bitwise and on the values C[i+1] and 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 both x and y. Otherwise, it is higher than one of the two.

So

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

Answer 2

I think you just need clz(C[i+1]) < clz(C[i]) where clz is a function which returns the number of leading zeroes ("count leading zeroes"). Some CPU families have an instruction for this (which may be available as an instrinsic). If not then you have to roll your own (it typically only takes a few instructions) - see Hacker's Delight.

Answer 3

The number of bits goes up when the value is about overflow a power of two. A simple test is then, is the value equal to a power of two, minus 1? This can be accomplished by asking:

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

Answer 4

Given (I believe this comes from Hacker's 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);
}

Your conditional is simply hibit(C[i]) != hibit(C[i+1]).

Answer 5

BSR - Bit Scan Reverse (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

You need two of these (on C[i] and C[i]+1) and a compare.

Answer 6

Keith Randall's solution is good, but you can save one xor instruction by using the following code which processes the entire sequence in O(w + n) instructions, where w is the number of bits in a word, and n is the number of elements in the sequence. If the sequence is long, most iterations will only involve one comparison, avoiding one xor instruction.

This is accomplished by tracking the highest power of two that has been reached as follows:

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

The number of bits goes up when the value is about to overflow a power of two. A simple test is then:

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

If you want it even faster:

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