c - 可以存储时间戳的最小字节数是多少？

Question

我想在 C 中创建自己的时间戳数据结构。

天 (0 - 30), 小时 (0 - 23), 分钟 (0 - 59)

可能的最小数据结构是什么？

Answer 1

好吧，您可以将它们全部打包unsigned short（即2 个字节，5 位代表日，5 位代表小时，6 位代表分钟）......并使用一些移位和掩码来获取值。

unsigned short timestamp = <some value>; // Bits: DDDDDHHHHHMMMMMM

int day = (timestamp >> 11) & 0x1F;
int hour = (timestamp >> 6) & 0x1F;
int min = (timestamp) & 0x3F;

unsigned short dup_timestamp = (short)((day << 11) | (hour << 6) | min); 

或使用宏

#define DAY(x)    (((x) >> 11) & 0x1F)
#define HOUR(x)   (((x) >> 6)  & 0x1F)
#define MINUTE(x) ((x)         & 0x3F)
#define TIMESTAMP(d, h, m) ((((d) & 0x1F) << 11) | (((h) & 0x1F) << 6) | ((m) & 0x3F)

（您在当前版本的问题中没有提到月/年，所以我省略了它们）。

[编辑：使用unsigned short-未签名short。]

Answer 2

您是指 HOUR 0-23 和 MINUTE 0-59 吗？我听说过闰秒，但不是闰分钟或闰小时。

(log (* 31 60 24) 2)
=> 15.446

因此，您可以将这些值设置为 16 位或 2 个字节。这是否是一个好主意是一个完全不同的问题。

Answer 3

• 月份：范围 1 - 12 => 4 位
• 日期：范围 1 - 31 => 5 位
• 小时：范围 0 - 24 => 5 位
• 分钟：范围 0 - 60 => 6 位

---

• 总计：20 位

您可以使用位域并使用编译器/平台特定的编译指示来保持它的紧密：

typedef struct packed_time_t {
    unsigned int month  : 4;
    unsigned int date   : 5;
    unsigned int hour   : 5;
    unsigned int minute : 6;
} packed_time_t; 

但是你真的需要这个吗？标准时间函数还不够吗？位域因架构、填充等而异……不是可移植的构造。

Answer 4

time()为什么不直接使用 C函数的（4 字节？）输出withNULL作为参数。这只是 Unix 纪元时间（即自 1970 年 1 月 1 日以来的秒数）。就像乔的答案一样，它比任何试图将数月、数天和数年打包成小块的答案为您提供了更大的成长空间。这是标准的。将time_t变量转换为实际时间在标准 C 中是微不足道的（至少在 Unix 上），并且大多数情况下，如果您有一个旨在保存 3 字节变量的数据结构，它可能会被四舍五入到 4 字节。

我知道您正在尝试对大小进行大量优化，但是 4 字节非常小。即使您截断最高字节，您仍然可以从中获得 194 天的不同时间。

time(NULL)通过在存储之前将时间从 60 除以 60，将其截断为一分钟并存储它，您可以从中获得更多收益。如上所示，其中 3 个字节为您提供 388 个月，而 2 个字节您可以存储 45 天。

我会选择 4 字节版本，只是因为我认为 2、3 和 4 字节之间的区别对于任何程序运行与否都不重要或至关重要（除非它是引导加载程序）。它更容易获得，也更容易处理，最终可能会为你省去很多麻烦。

编辑：我发布的代码不起作用。我已经睡了 3 个小时，我最终会弄清楚如何正确地旋转比特。在那之前，您可以自己实现它。

Answer 5

注意：原始问题已被编辑，不再需要月份。原始计算如下：

这只是您想要进行多少计算的问题。最紧凑的打包方法是，如果您可以创建自己的类型，并使用以下数学从和转换为相应的整数：

有效范围是：

月份：1-12 -> (0-11)+1
日：1-31 -> (0-30)+1
小时：0-24
分钟：0-60

您可以选择存储值的顺序（我将按上述顺序保存）。

月-1 天-1 小时分钟
(0-11) (0-30) (0-23) (0-59)

使用以下公式作为指导，进行一些乘法/除法以转换值：

值 = (((月 - 1) * 31 + (日 - 1)) * 24 + 小时) * 60 + 分钟

因此，您有最小值 0 和最大值((11*31+30)*24+23)*60+59535,679。因此，您至少需要 20 位才能将此值存储为无符号整数 ( 2^20-1 = 1,048,575; 2^19-1 = 524,287)。

如果你想让事情变得复杂但节省一个字节，你可以使用 3 个字节并自己操作它们。或者您可以使用 int（32 位）并使用简单的数学运算符正常使用它。

但是那里有一些空间可以玩，所以让我们看看我们是否可以让这更容易：

有效范围再次是：

月份：1-12 -> (0-11)+1 --- 4 位（你甚至不需要 -1）
日：1-31 -> (0-30)+1 --- 5 位（您再次不需要 -1）
小时：0-24 --- 5 位
分钟：0-60 --- 6 位

总共有 20 位，而且非常容易操作。因此，除了使用简单的位移之外，进一步压缩不会获得任何收益，并且可以像这样存储值：

19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
---月--- ----日------- ---小时--- --分钟---

---

如果你不关心月份，你能得到的最紧的是：

值 = ((Day - 1) * 24 + Hour) * 60 + Minute

为您留下 0 到 44,639 的范围，可以整齐地放入 16 位short.

不过那里有一些空间可以玩，所以让我们看看我们是否可以让这更容易：

有效范围再次是：

Day: 1-31 -> (0-30)+1 --- 5 位（你甚至不需要 -1）
小时：0-24 --- 5 位
分钟：0-60 --- 6 位

总共有 16 位，而且非常容易操作。所以....存储这样的值：

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
----天------- ---小时--- --分钟---

Answer 6

对于您描述的用例（31 天范围内的时间分钟分辨率），我只使用 16 位分钟计数器。如果您正在序列化这些数据（到磁盘、网络），那么您可以使用一些可变长度整数编码来保存小值的字节。

Answer 7

一般来说，您可以按如下方式计算此答案（其中 log2 是以 2 为底的对数，即位数）：

• 如果要使用移位和掩码来输入和输出数据，请取每个字段的可能值数量的 log2()，向上取整（以获取位），将结果相加（以获取总位），除以八（总字节，w.小数字节），然后再次四舍五入（总字节）。

  log2(60) + log2(60) + log2(24) + log2(31) + log2(12) = 6+6+5+5+4 = 26 位 = 4 字节

• 如果您想通过乘法和加法/除法和取模来输入和输出字段，请将每个字段的可能值的数量相乘，然后取 log2()，除以 8，然后四舍五入。

  log2(60*60*24*31*12) = 24.9379 位 = 4 字节

• 您可以通过组合非异构字段（例如，存储一年中的某天而不是月份和月份的某天）节省一点额外的空间，但这并不值得。

  log2(60*60*24*366) = 24.91444 位 = 4 字节

——MarkusQ《教人钓鱼》

Answer 8

只是提供一个替代方案：

• 如果你只需要分钟级别的分辨率，
• 而且您不会跨越日期边界（月/年）
• 并且您的消息是连续的，并且有保证的交付

然后您可以将时间戳存储为与最后一条消息的时间戳的偏移量。

在这种情况下，您只需要足够的位来保存消息之间的最大分钟数。例如，如果您最多间隔 255 分钟发出消息，那么一个字节就足够了。

但是请注意，第一条消息可能需要在其有效负载中包含绝对时间戳，以进行同步。

[我并不是说这是一个很好的解决方案——它相当脆弱并且做出了很多假设——只是一个替代方案]

Answer 9

60 分钟/小时意味着您至少需要 6 位来存储分钟（因为第 59 分钟 == 111011b），而 24 小时/天意味着另外 5 位（第 23 小时 == 10111b）。如果要考虑（可能）366 天/年中的任何一个，则需要多 9 位（第 366 天（第 1 天 == 0 时为 365）== 101101101b）。因此，如果您想以完全可访问的格式存储所有内容，则需要 20 位 == 3 字节。或者，添加一个 Month 字段将使总可能的 Days 值从 366 变为 31 - 减少到 5 位，该月再增加 4 位。这也将为您提供 20 位或 3 个字节，其中 4 位备用。

相反，如果您从某个开始日期开始按分钟跟踪日期，则 3 个字节将为您提供 16,777,215 分钟的分辨率，然后您再次翻转到 0 - 大约 279,620 小时、11,650 天和大约 388 个月，并且那是使用所有 24 位。如果您不关心秒数并且不介意花一点执行时间来解释小时、日和月，那么这可能是一个更好的方法。 这将更容易增加！

Answer 10

一天的 5 位加上小时的 5 位加上分钟的 6 位等于无符号短整数。任何进一步的打包都不会减少所需的存储空间，并且会增加代码复杂性和 CPU 使用率。

Answer 11

好吧，忽略多余的 HOUR 24 和 MINUTE 60，我们有 31 x 24 x 60 = 44,640 个可能的唯一时间值。2^15 = 32,768 < 44,640 < 65,536 = 2^16 所以我们需要至少 16 位（2 个字节）来表示这些值。

如果我们不想每次都进行模运算来访问值，我们需要确保将每个值存储在自己的位字段中。我们需要 5 位来存储 DAY，5 位来存储 HOUR，6 位来存储 MINUTE，它仍然适合 2 个字节：

struct day_hour_minute {
  unsigned char DAY:5; 
  unsigned char HOUR:5;
  unsigned char MINUTE:6;
};

包括 MONTH 将使我们的唯一时间值增加 12 倍，给出 535,680 个唯一值，这将需要至少 20 位来存储 (2^19 = 524,288 < 535,680 < 1,048,576 = 2^20)，这需要至少 3字节。

同样，为了避免模运算，我们需要一个单独的 MONTH 位字段，它应该只需要 4 位：

struct month_day_hour_minute {
  unsigned char MONTH:4;
  unsigned char DAY:5;
  unsigned char HOUR:5;
  unsigned char MINUTE:6;
  unsigned char unused: 4;
};

但是，在这两个示例中，请注意 C 更喜欢将其数据结构切入 - 也就是说，它们是 4 或 8 字节的倍数（通常），因此它可能会填充您的数据结构超出最低限度的必要条件。

例如，在我的机器上，

#include <stdio.h>

struct day_hour_minute {
  unsigned int DAY:5;
  unsigned int HOUR:5;
  unsigned int MINUTE:6;
};
struct month_day_hour_minute {
  unsigned int MONTH:4;
  unsigned int DAY:5;
  unsigned int HOUR:5;
  unsigned int MINUTE:6;
  unsigned int unused: 4;
};

#define DI( i ) printf( #i " = %d\n", i )
int main(void) {
  DI( sizeof(struct day_hour_minute) );
  DI( sizeof(struct month_day_hour_minute) );
  return 0;
}

印刷：

sizeof(struct day_hour_minute) = 4
sizeof(struct month_day_hour_minute) = 4

Answer 12

为了在不失一般性的情况下简化这一点，

日 (0 - 30)、小时 (0 - 23)、分钟 (0 - 59)

encoding = Day + (Hour + (Minute)*24)*31

Day = encoding %31
Hour = (encoding / 31) % 24
Minute = (encoding / 31) / 24

编码的最大值为 44639，略小于 16 位。

编辑：rampion 说的基本相同。这为您提供了最小表示，它小于按位交错表示。