1

Тема: Цікава задача: число довільної довжини

Задача: розробити формат представлення чисел довільної довжини, який би надавав можливість отримувати довжину числа без дослідження всього числа (VLQ, наприклад, не дозволяє).

Числа, для простоти, цілі беззнакові. Бажано, щоб число було щільним, без зайвих нулів на початку (чи принаймні допускало таке ущільнення)

Подякували: Betterthanyou, leofun012

2

Re: Цікава задача: число довільної довжини

Хм, цікаво чим перетворення числа у текст не підходить?

3

Re: Цікава задача: число довільної довжини

Моя пропозиція формату довгого числа (ДЧ): перший байт 1..10X (N одиничок) - довжина числа 8*(N+1)-(N+1) біт, починаючи з X. Наприклад, 0111 1111 - 7 біт, число 127, 1000 0001 0000 0000 14 біт, 256. Перший байт 0xFF (всі одинички) - ДЧ, що йде після нього, містить довжину числа в байтах. Наприклад, нестиснене число
0xFF 0xFF 0x01 0x01 0x01 дорівнює 1 ("число, довжина якого дорівнює ДЧ 0xFF 0x01 0x01 з вмістом 0x01", де 0xFF 0x01 0x01 - "число, довжина якого дорівнює 1, з вмістом 1", тобто 1).

4

Re: Цікава задача: число довільної довжини

Хоча я зовсім не в темі низькорівневого програмування, але все ж, для чого потрібен додатковий формат числа, якщо "кінцевий споживач" (програміст) може перетворити його у текст й підрахувати кількість символів... в тому кодуванні, яке дозволить прирівняти довжину числа до довжини тексту.

5

Re: Цікава задача: число довільної довжини

ktretyak написав:

Хм, цікаво чим перетворення числа у текст не підходить?

1. Довжина.
2. Дуже розріджене.

Порівняйте свою пропозицію із VLQ.

6

Re: Цікава задача: число довільної довжини

Може треба ще знати довжину числа довжини числа?

Подякували: P.Y.1

7

Re: Цікава задача: число довільної довжини

koala написав:

Моя пропозиція формату довгого числа (ДЧ): перший байт 1..10X (N одиничок) - довжина числа 8*(N+1)-(N+1) біт, починаючи з X. Наприклад, 0111 1111 - 7 біт, число 127, 1000 0001 0000 0000 14 біт, 256. Перший байт 0xFF (всі одинички) - ДЧ, що йде після нього, містить довжину числа в байтах. Наприклад, нестиснене число
0xFF 0xFF 0x01 0x01 0x01 дорівнює 1 ("число, довжина якого дорівнює ДЧ 0xFF 0x01 0x01 з вмістом 0x01", де 0xFF 0x01 0x01 - "число, довжина якого дорівнює 1, з вмістом 1", тобто 1).

Щось в мене голова не варить, ніяк не дійму як та довжина визначається

А що робити з 255? 0xFF не буде плутатись?

8

Re: Цікава задача: число довільної довжини

Master_Sergius написав:

Може треба ще знати довжину числа довжини числа?

Ще раз прочитайте - довжина у мене рекурсивна.

0x9111A написав:

А що робити з 255? 0xFF не буде плутатись?

Залежить від місця, де воно розташоване. 0x80 0xFF - це 255.

9

Re: Цікава задача: число довільної довжини

Тикаєш 2 направляючих. І рахуєш кількість перетинів.  І все . Дальше обробка євристикою.

10 Востаннє редагувалося Alchimic (03.02.2018 09:30:39)

Re: Цікава задача: число довільної довжини

це масив бітів. в форматі 16(для того щоб множити можна було легко в 32 розрядному регістрі) розрядних порцій. клас такий. рахувати просто з перенесенням. не стрінговий.