4

使用“timeval_subtract”函数来查找两个 struct timeval 类型之间经过的时间，有人可以解释用于“通过更新 y 执行后续减法的进位”和其他部分的目的和逐步数学吗？我了解该功能的用途以及如何在程序中实现它，但我想了解它在内部是如何工作的，并且在任何地方都找不到对此的任何解释，而且我似乎无法理解它。

int timeval_subtract (struct timeval *result, struct timeval *x,struct timeval  *y)  
{  
  /* Perform the carry for the later subtraction by updating y. */  
  if (x->tv_usec < y->tv_usec) {  
    int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1;  
    y->tv_usec -= 1000000 * nsec;  
    y->tv_sec += nsec;  
  }  
  if (x->tv_usec - y->tv_usec > 1000000) {  
    int nsec = (y->tv_usec - x->tv_usec) / 1000000;  
    y->tv_usec += 1000000 * nsec;  
    y->tv_sec -= nsec;  
  }  
  
  /* Compute the time remaining to wait.
     tv_usec is certainly positive. */  
  result->tv_sec = x->tv_sec - y->tv_sec;  
  result->tv_usec = x->tv_usec - y->tv_usec;  
  
  /* Return 1 if result is negative. */  
  return x->tv_sec < y->tv_sec;  
}

这是一个与 GNU C 库相关的函数，用于确定经过时间https://ftp.gnu.org/old-gnu/Manuals/glibc-2.2.5/html_node/Elapsed-Time.html 所以我不是在寻找改进，而只是解释为什么在其中进行除法加减乘法。这些特定的算术运算实现了什么？/为什么它们完成/没有完成？我已经完成了步骤，但仍然无法理解它。我将继续这样做，直到我这样做（甚至在有人向我解释之后），但我希望从已经理解它的人那里获得一些见解。该平台是 UNIX，我是新手，但我认为它不会改变函数内部发生的操作。这更多的是关于正在执行的算术而不是正在使用的算法的问题。

4

1 回答 1

15

乍一看，它似乎struct timeval包含一个分为两部分的时间：

  • tv_usec- 微秒，理想情况下应始终低于 1000000，但似乎允许更大的值，如代码所示
  • tv_sec- 秒（1000000 的倍数）

以微秒为单位的时间是tv_usec+ tv_sec* 1000000。

相反，人们会期望这是真的：

  • tv_sec= 以微秒为单位的时间 / 1000000
  • tv_usec= 以微秒为单位的时间 % 1000000。

该函数似乎计算*x和*y（逻辑上，*x- *y）之间的时间差并将其存储在另一个struct timeval, 中*result。

一个简单的测试程序给了我们一些提示：

#include <stdio.h>

struct timeval
{
  long tv_sec;
  long tv_usec;
};

int timeval_subtract(struct timeval *result, struct timeval *x, struct timeval *y)
{  
  // preserve *y
  struct timeval yy = *y;
  y = &yy;

  /* Perform the carry for the later subtraction by updating y. */  
  if (x->tv_usec < y->tv_usec) {  
    int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1;  
    y->tv_usec -= 1000000 * nsec;  
    y->tv_sec += nsec;  
  }  
  if (x->tv_usec - y->tv_usec > 1000000) {  
    int nsec = (y->tv_usec - x->tv_usec) / 1000000;  
    y->tv_usec += 1000000 * nsec;  
    y->tv_sec -= nsec;  
  }  

  /* Compute the time remaining to wait.
     tv_usec is certainly positive. */  
  result->tv_sec = x->tv_sec - y->tv_sec;  
  result->tv_usec = x->tv_usec - y->tv_usec;  

  /* Return 1 if result is negative. */  
  return x->tv_sec < y->tv_sec;  
}

struct timeval testData00 = { 0, 0 };
struct timeval testData01 = { 0, 1 };

int main(void)
{
  struct timeval diff;
  int res;

  res = timeval_subtract(&diff, &testData00, &testData00);
  printf("%d %ld:%ld\n", res, diff.tv_sec, diff.tv_usec);

  res = timeval_subtract(&diff, &testData01, &testData01);
  printf("%d %ld:%ld\n", res, diff.tv_sec, diff.tv_usec);

  res = timeval_subtract(&diff, &testData01, &testData00);
  printf("%d %ld:%ld\n", res, diff.tv_sec, diff.tv_usec);

  res = timeval_subtract(&diff, &testData00, &testData01);
  printf("%d %ld:%ld\n", res, diff.tv_sec, diff.tv_usec);

  return 0;
}

输出（ideone）：

0 0:0
0 0:0
0 0:1
1 -1:999999

从最后的测试结果看来，该函数返回 (-1):999999 而不是 -(0:1)。两个值都代表相同的负时间（或时间差），以微秒为单位：

  • -1 * 1000000 + 999999 = -1
  • -(0 * 1000000 + 1) = -1

那么，它是如何真正起作用的呢？

如果x->tv_usec>=y->tv_usec那么只有第二个if可能*执行：

  if (x->tv_usec - y->tv_usec > 1000000) {  
    int nsec = (y->tv_usec - x->tv_usec) / 1000000;  
    y->tv_usec += 1000000 * nsec;  
    y->tv_sec -= nsec;  
  }

这将if检查仅微秒部分的差异是否大于 1 秒。如果是，它会从y->tv_usec（以微秒计）中减去此差异的整个秒数并将其添加到y->tv_sec（以秒计）。这只是重新分配了时间，*y而没有真正改变它。您可以像这样等效地重写if它以更清楚地看到它：

  if (x->tv_usec - y->tv_usec > 1000000) {  
    int nsec = (x->tv_usec - y->tv_usec) / 1000000;  
    y->tv_usec -= 1000000 * nsec;  
    y->tv_sec += nsec;  
  }

这里要注意的一件重要的事情是，当输入*x和*y它们tv_usec的范围在 0 到 999999 之间时，它的主体不会执行if（因此，当> =和何时在 0 到999999）。x->tv_usecy->tv_usectv_usecs

其净影响if现在还不是很清楚。

但是，在这里可以看到一件有趣的事情。如果我们用*x= 0:1000001 和*y= 0:0 调用这个函数，结果将是错误的：差 = (-1):2000001（而不是 1:1）并且函数的返回值 = 1（而不是0)。这表明该函数并不真正适合tv_usec > 1000000，甚至不适合tv_usec > 999999. 由于这种行为，我将声称该函数也不适合tv_usec输入中的负数。面对这种行为，我将忽略这些情况。它看起来已经够错了。

让我们看第一个if。

  /* Perform the carry for the later subtraction by updating y. */  
  if (x->tv_usec < y->tv_usec) {  
    int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1;  
    y->tv_usec -= 1000000 * nsec;  
    y->tv_sec += nsec;  
  }

正如评论和代码所暗示的，当x->tv_usec<y->tv_usec我们需要处理“数字”之间的“进位”，就好像我们是在加法而不是减法一样。但没关系，我们会看到的。

让我们回学校一会儿。

37 - 12 你是怎么做的？

你这样做：

7 - 2 = 5
3 - 1 = 2

所以 37 - 12 = 25。

现在，你怎么做 57 - 38？

你这样做：

10/*because 7 < 8*/ + 7 - 8 = 9
5 - 3 - 1/*borrow, because of the above*/ = 1

所以 57 - 38 = 19。看到了吗？

和检查：

  if (x->tv_usec < y->tv_usec) {

检查我们是否需要处理这种借款。

那么，这里发生了什么？我们再看一遍：

  if (x->tv_usec < y->tv_usec) {  
    int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1;  
    y->tv_usec -= 1000000 * nsec;  
    y->tv_sec += nsec;  
  }

如果y->tv_usec> x->tv_usec，它以整秒为单位计算两者之间的差异，就像另一个一样，if它将这些整秒添加到y->tv_sec并从中减去它们y->tv_usec，只需重新分配 中的时间*y，而不更改它。

+ 1最终添加到此处的额外的 ( )y->tv_sec将从x->tv_sec函数 ( ) 的末尾减去result->tv_sec = x->tv_sec - y->tv_sec;，因此这 1 用作我刚刚在 57 - 38 = 19 示例中提醒您的借用。

除了借用本身和一些时间重新分配之外，这里还发生了什么？

就像我之前说的，我将忽略负数tv_usecs和大于 999999 的可能处理不当。

有了这个，我认为(y->tv_usec - x->tv_usec) / 1000000是 0，我只剩下真正有意义的值tv_usecs（0 到 999999 包括在内）。

所以，如果if's条件为真，我基本上减去 1000000y->tv_usec并将 1（借位）加到y->tv_sec.

这与我们在 57 - 38 = 19 中的情况相同：

10/*because 7 < 8*/ + 7 - 8 = 9
5 - 3 - 1/*borrow, because of the above*/ = 1

与这 10 类似，稍后将在此处添加 1000000：result->tv_usec = x->tv_usec - y->tv_usec;

这首先if是函数的核心。

如果我必须编写一个具有类似行为的函数，我会要求输入时间是非负的，并且微秒部分不大于 999999，我会写这个：

int timeval_subtract(struct timeval *result, struct timeval *x, struct timeval *y)
{
  result->tv_sec = x->tv_sec - y->tv_sec;

  if ((result->tv_usec = x->tv_usec - y->tv_usec) < 0)
  {
    result->tv_usec += 1000000;
    result->tv_sec--; // borrow
  }

  return result->tv_sec < 0;
}

如果出于某种奇怪的原因，我想tv_usec在输入中支持 > 999999，我首先将多余的从tv_usecto 移到tv_sec，然后执行上述操作，如下所示：

int timeval_subtract(struct timeval *result, struct timeval *x, struct timeval *y)
{
  struct timeval xx = *x;
  struct timeval yy = *y;
  x = &xx; y = &yy;

  if (x->tv_usec > 999999)
  {
    x->tv_sec += x->tv_usec / 1000000;
    x->tv_usec %= 1000000;
  }

  if (y->tv_usec > 999999)
  {
    y->tv_sec += y->tv_usec / 1000000;
    y->tv_usec %= 1000000;
  }

  result->tv_sec = x->tv_sec - y->tv_sec;

  if ((result->tv_usec = x->tv_usec - y->tv_usec) < 0)
  {
    result->tv_usec += 1000000;
    result->tv_sec--; // borrow
  }

  return result->tv_sec < 0;
}

在这里，意图很明确，代码也很容易理解。

于 2013-04-06T10:24:41.293 回答