Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → Алгоритми та структури даних, технології → Цікава задача: число довільної довжини
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися
Задача: розробити формат представлення чисел довільної довжини, який би надавав можливість отримувати довжину числа без дослідження всього числа (VLQ, наприклад, не дозволяє).
Числа, для простоти, цілі беззнакові. Бажано, щоб число було щільним, без зайвих нулів на початку (чи принаймні допускало таке ущільнення)
Хм, цікаво чим перетворення числа у текст не підходить?
Моя пропозиція формату довгого числа (ДЧ): перший байт 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).
Хоча я зовсім не в темі низькорівневого програмування, але все ж, для чого потрібен додатковий формат числа, якщо "кінцевий споживач" (програміст) може перетворити його у текст й підрахувати кількість символів... в тому кодуванні, яке дозволить прирівняти довжину числа до довжини тексту.
Хм, цікаво чим перетворення числа у текст не підходить?
1. Довжина.
2. Дуже розріджене.
Порівняйте свою пропозицію із VLQ.
Може треба ще знати довжину числа довжини числа?
Моя пропозиція формату довгого числа (ДЧ): перший байт 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 не буде плутатись?
Може треба ще знати довжину числа довжини числа?
Ще раз прочитайте - довжина у мене рекурсивна.
А що робити з 255? 0xFF не буде плутатись?
Залежить від місця, де воно розташоване. 0x80 0xFF - це 255.
Тикаєш 2 направляючих. І рахуєш кількість перетинів. І все . Дальше обробка євристикою.
це масив бітів. в форматі 16(для того щоб множити можна було легко в 32 розрядному регістрі) розрядних порцій. клас такий. рахувати просто з перенесенням. не стрінговий.
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися
