Какое наименьшее количество байтов может хранить метку времени?

Question

Я хочу создать свою собственную структуру данных меток времени в C.

ДЕНЬ (0–31), ЧАС (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

Вы имеете в виду ЧАС 0-23 и МИНУТУ 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

Почему бы просто не использовать (4-байтовый?) Вывод функции C time() с NULL в качестве аргумента. Это просто время эпохи Unix (т.е. количество секунд с 1 января 1970 года). Как и ответ Джо, он дает вам намного больше возможностей для роста, чем любой ответ, который пытается сложить в месяцы, дни и годы в биты. Это стандартно. Преобразование переменной time_t в фактическое время тривиально в стандарте C (по крайней мере в Unix), и большую часть времени, если у вас есть структура данных, предназначенная для хранения 3-байтовой переменной, она может быть округлена до 4 байтов. в любом случае.

Я знаю, что вы пытаетесь сильно оптимизировать размер, но 4 байта чертовски мало. Даже если вы урежете верхний байт, вы все равно получите 194 дня различного времени.

Вы можете получить еще больше от этого, взяв время от time(NULL) и разделив его на 60, прежде чем сохранить, урезать до минуты и сохранить. 3 байта этого дают вам, как показано выше, 388 месяцев, а для 2 байтов вы можете хранить 45 дней.

Я бы выбрал 4-байтовую версию просто потому, что не вижу разницы между 2, 3 и 4 байтами как существенной или существенной для любой программы, запущенной или нет (если это не загрузчик). Проще получить и проще в обращении, и, возможно, в итоге вы избавите вас от многих головных болей.

РЕДАКТИРОВАТЬ: Код, который я разместил, не работал. У меня было 3 часа сна, и я со временем разберусь, как правильно делать переворот. До этого вы можете реализовать это самостоятельно.

Answer 5

Примечание: исходный вопрос был отредактирован, и месяц больше не нужен. Первоначальные расчеты были ниже:

Это просто вопрос того, сколько вычислений вы хотите сделать. Самый надежный способ упаковать это, если вы можете сделать свой собственный тип и использовать следующую математику для преобразования из и в соответствующее ему целое число:

Допустимые диапазоны:

Month: 1-12 -> (0-11)+1
Day: 1-31 -> (0-30)+1
Hour: 0-24
Minute: 0-60

Вы можете выбрать порядок хранения значений (я сохраню его в указанном выше порядке).

Month-1 Day-1  Hour   Minute
(0-11)  (0-30) (0-23) (0-59)

Выполните немного умножения / деления, чтобы преобразовать значения, используя следующую формулу:

value = (((Month - 1) * 31 + (Day - 1)) * 24 + Hour) * 60 + Minute

Итак, у вас есть минимальное значение 0 и максимальное значение ((11*31+30)*24+23)*60+59, которое составляет 535 679. Таким образом, вам нужно минимум 20 бит, чтобы сохранить это значение как целое число без знака (2^20-1 = 1,048,575; 2^19-1 = 524,287).

Если вы хотите сделать вещи сложными, но сохранить байт, вы можете использовать 3 байта и манипулировать ими самостоятельно. Или вы можете использовать int (32-бит) и работать с ним, как правило, используя простые математические операторы.

НО там есть место для игры, поэтому давайте посмотрим, сможем ли мы сделать это проще:

Допустимые диапазоны, опять же:

Month: 1-12 -> (0-11)+1 --- 4 bits (you don't even need the -1)
Day: 1-31 -> (0-30)+1   --- 5 bits (you again don't need the -1) 
Hour: 0-24              --- 5 bits
Minute: 0-60            --- 6 bits

Это всего 20 бит, и им действительно легко манипулировать. Таким образом, вы ничего не получите, сжимаясь дальше, чем с помощью простого сдвига битов, и вы можете сохранить значение следующим образом:

19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
---Month--- ----Day------- ---Hour--- --Minute---

---

Если вам наплевать на месяц, самое короткое, что вы можете получить:

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

оставляя вас с диапазоном от 0 до 44 639, который может уместиться в 16-битном short.

Там есть место для игры, поэтому давайте посмотрим, сможем ли мы сделать это проще:

Допустимые диапазоны, опять же:

Day: 1-31 -> (0-30)+1 --- 5 bits (you don't even need the -1) 
Hour: 0-24            --- 5 bits
Minute: 0-60          --- 6 bits

Это всего 16 бит, и опять-таки очень легко манипулировать. Так что .... сохраните значение следующим образом:

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
----Day------- ---Hour--- --Minute---

Answer 6

В общем случае вы можете вычислить этот ответ следующим образом (где log2 - это логарифм по основанию 2, то есть количество бит):

• Если вы хотите использовать сдвиги и маски для ввода и вывода данных, возьмите log2 () из числа возможных значений для каждого поля, округлите (чтобы получить биты), добавьте результаты (чтобы получить общее количество бит), разделите на восемь (общее количество байтов, w. дробных байтов) и округлите снова (общее количество байтов).

  log2 (60) + log2 (60) + log2 (24) + log2 (31) + log2 (12) = 6 + 6 + 5 + 5 + 4 = 26 бит = 4 байта

• Если вы хотите, чтобы поля входили и выходили путем умножения, сложения, деления и модуляции, умножьте количество возможных значений для каждого поля и возьмите log2 () для этого, разделите на восьмое и округлите .

  log2 (60 * 60 * 24 * 31 * 12) = 24,9379 бит = 4 байта

• Вы можете сэкономить крошечный дополнительный объем пространства, комбинируя неизоформные поля (например, сохраняя день года, а не месяц и день месяца), но это редко стоит.

  log2 (60 * 60 * 24 * 366) = 24,91444 бит = 4 байта

- MarkusQ "научить человека ловить рыбу"

Answer 7

Для описанного вами варианта использования (минутное разрешение раз в диапазоне 31 день) я бы просто использовал 16-битный счетчик минут. Если вы сериализуете эти данные (на диск, в сеть), вы можете использовать целочисленное кодирование переменной длины, чтобы сохранить байты для небольших значений.

Answer 8

60 минут / час означает, что вам потребуется не менее 6 бит для хранения минуты (с 59-й минуты == 111011b), а 24 часа / день - еще 5 бит (23-й час == 10111b). Если вы хотите учесть какой-либо из (возможно) 366 дней в году, вам потребуется еще 9 бит (366-й день (365, когда день 1 == 0) == 101101101b). Поэтому, если вы хотите хранить все в чисто доступном формате, вам потребуется 20 бит == 3 байта. В качестве альтернативы, добавление поля «Месяц» приведет к тому, что общее возможное значение «Дни» изменится с 366 до 31 - до 5 битов, а за месяц будет еще 4 бита. Это также даст вам 20 бит или 3 байта с 4 битами для запаса.

И наоборот, если вы отслеживали дату всего по минутам от некоторой начальной даты, 3 байта дадут вам разрешение в 16 777 215 минут, прежде чем вы снова перейдете к 0 - это примерно 279 620 часов, 11 650 дней и около 388 месяцев, и это использует все 24 бита. Вероятно, так будет лучше, если вам не нужны секунды и если вы не возражаете потратить немного времени на выполнение, чтобы интерпретировать час, день и месяц. И это было бы намного проще увеличить!

Answer 9

просто чтобы предложить альтернативу:

• если вам нужно только разрешение на минутном уровне,
• и вы не пересекаете границы дат (месяц / год)
• и ваши сообщения последовательны с гарантированной доставкой

затем вы можете сохранить метку времени как смещение от метки времени последнего сообщения.

В этом случае вам нужно только достаточное количество бит для хранения максимального количества минут между сообщениями. Например, если вы посылаете сообщения с интервалом не более 255 минут, то достаточно одного байта.

Обратите внимание, однако, что в самом первом сообщении может потребоваться включить абсолютную метку времени в свою полезную нагрузку для синхронизации.

[Я не говорю, что это хорошее решение - оно довольно хрупкое и делает много предположений - просто альтернативное]

Answer 10

Чтобы упростить это без потери общности,

день (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 бит.

Edit: rampion сказал в основном то же самое. И это дает вам минимальное представление, которое меньше, чем представление побитового перемежения.