3

谁能解释一下（（~（preRtcInseconds <<1）+1）>>1）

unsigned long preInseconds;
unsigned long curInSeconds;
unsigned long elapsedInSeconds;

if(curInSeconds>=preInseconds)
{
   elapsedInSeconds = curInSeconds - preInseconds;//does easy thing. no needs roll over
}
else{ //rollover
  preInseconds = ((~(preInseconds <<1)+1)>>1);
  elapsedInSeconds = curInSeconds + preInseconds;
}
4

3 回答 3

4

设 为 的unsigned long宽度w。unsigned long那么一个可以容纳的最大值是

ULONG_MAX = 2^w - 1

让preInseconds = a + b, 在哪里

a = preInseconds & (1ul << (w-1))
b = preInseconds & ((1ul << (w-1)) - 1)

a是 0 还是2^(w-1)，取决于 是否preInseconds >= 2^(w-1)。然后最初的左移消失了a，所以

preInseconds << 1

给出b << 1或2*b。

然后取按位补码，

~(b << 1)

给ULONG_MAX - (b << 1).

如果b == 0, 加 1ULONG_MAX - (b << 1)结果为 0, 否则

~(b << 1) + 1

给

2^w - (b << 1)

然后右移一位产生 0 如果b == 0并且

2^(w-1) - b

除此以外。因此

preInseconds = ((~(preInseconds <<1)+1)>>1);

设置preInseconds为

2^(w-1) - b

如果b != 0，则为 0 b == 0。

最后，

elapsedInSeconds = curInSeconds + preInseconds;

因此设置elapsedInSeconds为curInSecondsifpreInseconds的值2^(w-1)[如果else分支被采用, preInseconds > curInSeconds, 所以它不是 0] 并且

curInSeconds - (preInseconds & (ULONG_MAX >> 1)) + 2^(w-1)

除此以外。

我不确定该操作的目的是什么。对于preInseconds > curInSeconds, 计算

curInSeconds - preInseconds

会导致

(2^w - preInseconds) + curInSeconds

这与（数学上）相同

(2^w + curInSeconds) - preInseconds

如果计数器自上次使用后curInSeconds翻转一次，这将是经过的时间preInseconds，如果当前计数器值小于前一个值，这可能会发生。这是有道理的。

在else分支完成体操，

  • 如果preInseconds <= 2^(w-1),elapsedInSeconds变为curInSeconds - preInseconds + 2^(w-1), 翻转的当前计数器与前一个计数器之间的差减去2^(w-1)
  • 如果preInseconds > 2^(w-1)，因为x - 2^(w-1) == x + 2^(w-1)在无符号算术中，我们得到与 相同的结果curInSeconds - preInSeconds。

因此，假设curInSeconds翻转一次，它会计算前一个事件和当前事件之间经过的秒数，除非翻转发生2^(w-1)在前一个事件之后或更长时间之后，在这种情况下，2^(w-1)从实际经过的时间中减去秒数。

于 2012-12-19T20:37:10.250 回答
2

它看起来像是由不理解 C 无符号算术是 mod 2^n （或不理解 mod 2^n 算术）的人编写的错误翻转代码。它实际上完全等同于：

elapsedInSeconds = curInSeconds - preInseconds;
if (curInSeconds < UNLONG_MAX/2 && preInseconds < ULONG_MAX/2)
    elapsedInSeconds &= ULONG_MAX/2;

也就是说，它做了一个 mod 2^n 减法，但在少数情况下（可能从未在任何测试用例中命中），它会出错（清除而不是设置）。

这很可能是故意的，因为这里发生的情况是，如果两个数字都 <2^n-1，它会进行 mod 2^n-1 减法，如果任一数字 >=，它会进行 mod 2^n 减法2^n-1（其中n是无符号长整数的大小，以位为单位）。如果时间来自某些可能总是清除最高位或可能不清除的硬件设备，这可能是有道理的。

于 2012-12-19T22:51:35.350 回答
1

首先，我在下面讨论的所有内容都假设您的unsigned long类型是 32 位宽。如果不是，那没关系；它有多宽并不重要，但我所有的例子都假设它是 32 位宽。我只是uint32用来表示，知道这uint32实际上不是标准类型uint32_t，请不要告诉我。

Daniel Fischer 已经很好地详细解释了每个低级操作，这里不再赘述。但是我认为您感兴趣的不是每个低级操作的含义，而是所有这些操作作为一个组应用的必要性。正如我将在下面解释的那样，无论如何都没有必要。事实上，他们有点错误，但只是在“当前”计数器读数比“先前”读数绕圆圈返回一半以上的情况下。

在我了解您的实现数学背后的“意义”之前，让我们首先看一个简单的例子，它如何在可能的最小翻转情况下计算 elapsedInSeconds：

如果 preInseconds = 0xffffffff 和 curInSeconds = 0x00000000，则 elapsedInSeconds 应为 1。

preInseconds = preInseconds<<1;     // 0xfffffffe
preInseconds = ~preInseconds;       // 0x00000001
preInseconds = preInseconds+1       // 0x00000002
preInseconds = preInseconds>>1;     // 0x00000001
elapsedInSeconds = curInSeconds + preInseconds;
             ... =  0x00000000  +  0x00000001    = 1

...这正是我们所期望的。伟大的。

然而，有趣的是，不需要任何翻转处理逻辑。完全没有。每次我看到有人试图计算“当前”和“以前”计数器值之间的差异时，我总是看到他们跳过箍来处理翻车情况，而且他们往往做错了。这种情况的耻辱是用特殊情况处理翻转永远不会对于 2 次幂大小的计数器是必需的。如果计数器的满量程（翻转点）小于您的数据类型的大小，您需要将结果屏蔽回计数器中的位数，但这是您真正做过的唯一翻转处理需要，在这种情况下，您只需每次都进行屏蔽，而不必担心它是否翻转（这也避免了分支指令，因此速度更快）。由于您的翻转点是 uint32 的满量程值，因此您甚至不需要屏蔽结果。

原因如下：

如上所述，假设 preInseconds=0xffffffff 和 curInSeconds=0。同样，结果应该是 1。如果您不担心翻转，您只需将 curInSeconds-preInseconds 作为结果。但是在翻转的情况下，减法运算会产生下溢。这意味着什么？这意味着，如果您有更多要处理的位（即另一个 uint32 被用作 64 位复合计数器的高位字），那么您需要从高位字中借 1（就像小学用十进制数减法）。但在你的情况下，没有更高的词可以借用。没关系。真的。反正你也不在乎这些。您仍然可以获得您正在寻找的差异值：

elapsedInSeconds = curInSeconds - preInseconds;
             ... =  0x00000000  -  0xffffffff     = 1

...这完全没有任何特殊的翻转处理逻辑就给出了预期的结果。

所以你可能会想，“当然，这适用于你的小例子，但是如果翻转很大怎么办？” 好吧，让我们探索一下这种可能性。然后假设 preInseconds=0xffffffff 和 curInSeconds=0xffffffffe。在这个例子中，我们几乎完全从前面的例子中恢复过来；事实上，我们离它只有一步之遥。在这种情况下，我们的结果应该是 0xffffffff（即比 uint32 可以表示的值的数量少一个）：

elapsedInSeconds = curInSeconds - preInseconds;
             ... =  0xfffffffe  -  0xffffffff     = 0xffffffff

不相信我？试试这个：

#include <stdio.h>
typedef unsigned long uint32;
int main()
{
    uint32 prev = 0xffffffff;
    uint32 cur  = 0xfffffffe;
    uint32 result = cur - prev;
    printf("0x%08x - 0x%08x = 0x%08x\n", cur, prev, result);
}

现在，让我们回到实现背后的数学：

该计算“有点”计算 preInseconds 的二进制补码并将结果分配回 preInseconds。如果您对数字的计算机表示和二进制补码加减法有所了解，您就会知道计算差 AB 与计算 A 和 B 的二进制补码之和相同，即 A+(-B)。如果您以前从未研究过它，请查看 Wikipedia 或任何地方，了解二进制补码如何使计算机的 ALU 能够重新使用其加法电路进行减法。

现在看看您显示的代码实际上“错误”的是什么：

要计算一个数字的二进制补码，请将该数字取反（将其所有 0 位更改为 1，将其所有 1 位更改为 0），然后加一。就是这么简单。这就是你的代码正在做的“有点”，但不完全是。

preInseconds = preInseconds<<1;     // oops, here we lose the top bit
preInseconds = ~preInseconds;       // do the 2's complement inversion step*
preInseconds = preInseconds+1       // do the 2's complement addition step*
preInseconds = preInseconds>>1;     // shift back to where it ought to be,
                                    // but without that top bit we wish we kept

*NOTE: The +1 above only works here because the low bit is
 guaranteed to be 1 after the ~ operation, which carries a 1
 up into the 2nd bit, where it matters.

所以我们在这里看到，本质上数学所做的是通过对其执行“几乎”二进制补码转换来手动否定 preInseconds 的值。不幸的是，它也在这个过程中丢失了最高位，这使得翻转逻辑只能在 elapsedInSeconds = 0x7fffffff 的最大值下工作，而不是它的满量程限制 0xffffffff。

您可以将其转换为以下内容，并消除最高位的丢失：

preInseconds = ~preInseconds;       // do the 2's complement inversion step
preInseconds = preInseconds+1       // do the 2's complement addition step

所以现在你已经直接计算了二进制补码，你可以计算结果：

elapsedInSeconds = curInSeconds + preInseconds; // (preInseconds is the 2's compl of its original value)

但愚蠢的是，这在计算上等同于简单地这样做......

elapsedInSeconds = curInSeconds - preInseconds; // (preInseconds is its unconverted original value)

一旦你意识到这一点，你的代码示例就变成了：

if(curInSeconds>=preInseconds)
{
    elapsedInSeconds = curInSeconds - preInseconds;
}
else // rollover
{
    elapsedInSeconds = curInSeconds - preInseconds;
}

...这应该清楚地表明，首先不需要将翻转作为特殊情况处理。

于 2012-12-19T22:25:42.877 回答