增加位大小的有效条件

Question

假设我有一个递增的无符号整数序列C[i]。随着它们的增加，它们可能会占用越来越多的位。我正在寻找一个有效的条件，纯粹基于序列 C[i] 和 C[i+1] 的两个连续元素（过去和未来的不是observable），每次所需位数增加时，都会精确或近似地评估为真。

一个明显（但缓慢）的条件选择是：

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

同样，任何使用特殊 cpu 操作码计算前导零位数的东西（好得多，但仍然不是很好）。

我怀疑可能有一个很好的解决方案，涉及仅使用按位或和按位以及值 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+1]) clz(C[i+1]) clz(C[i+1]) clz(C[i]) 其中 clz 是一个返回前导零数量的函数（“计数前导零”）。某些 CPU 系列具有用于此目的的指令（可以作为内在指令使用）。如果没有，那么您必须自己动手（通常只需要一些说明） - 请参阅 黑客的乐趣。

Answer 3

鉴于（我相信这来自 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);
}

您的条件只是 hibit(C[i] ) != hibit(C[i+1])。

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

Keith Randall 的解决方案很好，但是您可以通过使用以下代码来节省一条异或指令，该代码在 O(w + n) 条指令中处理整个序列，其中 w 是字中的位数，n 是元素的数量在序列中。如果序列很长，则大多数迭代将仅涉及一次比较，从而避免一条异或指令。

这是通过跟踪已达到的两个的最高功率来完成的，如下所示：

t = 1; // original setting

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

Answer 6

当值大约溢出 2 的幂时，位数会增加。那么一个简单的测试是，该值是否等于 2 的负 1 次方？这可以通过询问来完成：

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

Answer 7

当值即将溢出 2 的幂时，位数会增加。
一个简单的测试是：

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