Как отобразить длинное целое число на N-мерный вектор меньших целых чисел (и быстрое обратное)?

Question

Учитывая N-мерный вектор малых целых чисел, есть ли какой-нибудь простой способ сопоставить его с однозначным соответствием большому целому числу?

Скажем, у нас N = 3 векторного пространства. Можем ли мы представить вектор X = [(int16) x1, (int16) x2, (int16) x3], используя целое число (int48) y? Очевидный ответ: «Да, мы можем». Но вопрос таков: «Какой самый быстрый способ сделать это и его обратную операцию?»

Будет ли это новое одномерное пространство обладать какими-то особыми полезными свойствами?

Answer 1

Для приведенного выше примера у вас есть 3 * 32 = 96 бит информации, поэтому без каких-либо априорных знаний вам потребуется 96 бит для эквивалентного длинного целого числа.

Однако , если вы знаете, что ваши значения x1, x2, x3 всегда будут соответствовать, скажем, 16 битам, то вы можете упаковать их все в 48-битное целое число.

В любом случае техника очень проста, вы просто используете операции shift, mask и bitwise or для упаковки / распаковки значений.

Answer 2

Если у вас есть наборы Si, i=1..n размера Ci = |Si|, то декартово множество S = S1 x S2 x ... x Sn имеет размер C = C1 * C2 * ... * Cn.

Это мотивирует очевидный способ сделать упаковку один в один. Если у вас есть элементы e1,...,en из каждого набора, каждый в диапазоне от 0 до Ci-1, то вы присваиваете элементу e=(e1,...,en) значение e1+C1*(e2 + C2*(e3 + C3*(...Cn*en...))).

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

В конкретном случае трех 32-битных целых, если они могут принимать любое значение, вы должны рассматривать их как одно 96-битное целое.

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

(Например, можно сопоставить (n,m) с (max(n,m)-1)^2 + k, где k=n, если n<=m и k=n+m, если n>m - вы можете нарисовать это как изображение заполнения квадрата следующим образом:

1 2 5   | draw along the edge of the square this way
4 3 6   v
  8 7

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

Answer 3

Просто, чтобы сделать это конкретным, если у вас есть трехмерный вектор из 8-битных чисел, например:

uint8_t vector[3] = { 1, 2, 3 };

тогда вы можете объединить их в одно (24-битное число), например:

uint32_t all = (vector[0] << 16) | (vector[1] << 8) | vector[2];

Это число будет, если напечатано с использованием этого утверждения:

printf("the vector was packed into %06x", (unsigned int) all);

производит вывод

the vector was packed into 010203

Обратная операция будет выглядеть так:

uint8_t v2[3];

v2[0] = (all >> 16) & 0xff;
v2[1] = (all >> 8) & 0xff;
v2[2] = all & 0xff;

Конечно, все это зависит от размера отдельных чисел в векторе и длины вектора, не превышающих размер доступного целочисленного типа, иначе вы не можете представить «упакованный» вектор как одно число .

Answer 4

Чтобы расширить обобщенную форму Рекса Керра, в C вы можете упаковать числа следующим образом:

X = e[n];

X *= MAX_E[n-1] + 1;
X += e[n-1];

/* ... */

X *= MAX_E[0] + 1;
X += e[0];

И распакуйте их с:

e[0] = X % (MAX_E[0] + 1);
X /= (MAX_E[0] + 1);

e[1] = X % (MAX_E[1] + 1);
X /= (MAX_E[1] + 1);

/* ... */

e[n] = X;

(где MAX_E[n] - наибольшее значение, которое может иметь e[n]). Обратите внимание, что эти максимальные значения, вероятно, будут постоянными и могут быть одинаковыми для каждого e, что немного упростит ситуацию.

Реализации смещения / маскирования, приведенные в других ответах, являются обобщением этого для случаев, когда значения MAX_E + 1 являются степенями 2 (и, таким образом, умножение и деление могут быть выполнены со сдвигом, добавление с побитовым -или и модуль с побитовым-а).

Answer 5

Я пишу это, не имея времени для проверки деталей, но я подозреваю, что лучший способ - представить ваше длинное целое число с помощью модульной арифметики, используя k различных целых чисел, которые взаимно просты. Исходное целое число затем может быть восстановлено с использованием китайской теоремы об остатках. Извините, это немного отрывочно, но надеюсь, что это поможет.

Answer 6

#include <stdint.h> // for uint8_t
long x;
uint8_t * p = &x;

или

union X {
   long L;
   uint8_t A[sizeof(long)/sizeof(uint8_t)];
};

работает, если вы не заботитесь о порядке байтов. По моему опыту, компиляторы генерируют лучший код с помощью union, поскольку он не устанавливает их правила «вы взяли адрес этого, поэтому я должен держать его в оперативной памяти» как можно быстрее. Эти правила будут отключены, если вы попытаетесь проиндексировать массив такими вещами, которые компилятор не может оптимизировать.

Если вы заботитесь о порядке байтов, вам нужно замаскировать и сместить.

Answer 7

Я думаю, что вы хотите решить, используя многомерные кривые заполнения пространства . Ссылка дает много ссылок на это, которые, в свою очередь, дают различные методы и идеи. Вот конкретный пример обратимого отображения . Работает для любого измерения N.

Что касается полезных свойств, эти сопоставления связаны с кодами Грея .

Трудно сказать, было ли это то, что вы искали, или "пакет 3 16-битных целых в 48-битное целое" делает трюк для вас.

Answer 8

Есть несколько совершенно непереносимых способов сделать это очень быстро, используя упакованные союзы и прямой доступ к памяти. То, что вам действительно нужна такая скорость, подозрительно. Методы, использующие смены и маски, должны быть достаточно быстрыми для большинства целей. Если нет, рассмотрите возможность использования специализированных процессоров, таких как GPU, для оптимизации векторной поддержки (параллельно).

Это наивное хранилище не обладает каким-либо полезным свойством, чем я могу предвидеть, за исключением того, что вы можете выполнять некоторые вычисления (сложение, под логические, побитовые операторы) для трех координат одновременно, если вы используете только натуральные числа переполнение для add и sub.

Вам лучше быть уверенным, что вы не переполнитесь (или не перейдете в отрицательное значение для sub), иначе вектор станет мусором.