Представьте два положительных целых числа A и B. Я хочу объединить эти два в одно целое число C.
Не может быть других целых чисел D и E, которые объединяются в C. Поэтому объединение их с помощью оператора сложения не работает. Например, 30 + 10 = 40 = 40 + 0 = 39 + 1 Не работает конкатенация. Например, «31» + «2» = 312 = «3» + «12»
Эта комбинированная операция также должна быть детерминированной (всегда давать один и тот же результат с одними и теми же входными данными) и всегда должна давать целое число с положительной или отрицательной стороны целых чисел.
10,001*A + B
?Ответы:
Вы ищете биективное
NxN -> N
отображение. Они используются, например, для ласточкиного хвоста . Посмотрите этот PDF для ознакомления с так называемыми функциями сопряжения . Википедия представляет особую функцию сопряжения, а именно функцию сопряжения Кантора :Три замечания:
ZxZ -> N
отображение. Функция Кантора работает только на неотрицательных числах. Однако это не проблема, потому что легко определить биекциюf : Z -> N
, например так:источник
Функция сопряжения Кантора действительно одна из лучших, учитывая ее простоту, скорость и эффективность использования пространства, но кое-что еще лучше опубликовано в Wolfram Мэтью Шудзиком, здесь . Ограничение функции сопряжения Кантора (относительно) состоит в том, что диапазон закодированных результатов не всегда остается в пределах
2N
битового целого числа, если входные данные являютсяN
двухбитными целыми числами. То есть, если мои входные данные представляют собой16
двухбитные целые числа в диапазоне от0 to 2^16 -1
, то2^16 * (2^16 -1)
возможны комбинации входных данных, поэтому, в соответствии с очевидным принципом Pigeonhole , нам нужен выход по крайней мере такого размера2^16 * (2^16 -1)
, который равен2^32 - 2^16
или, другими словами, карте32
битовые числа должны быть выполнимыми в идеале. Это не может иметь мало практического значения в мире программирования.Функция сопряжения Кантора :
Введите функцию Шудзика :
Теперь, учитывая тот факт, что мы обычно имеем дело со знаковыми реализациями чисел различных размеров в языках / инфраструктурах, давайте рассмотрим
signed 16
битовые целые числа, начиная от-(2^15) to 2^15 -1
(позже мы увидим, как расширить даже выходной поток, чтобы охватить диапазон со знаком). Так какa
иb
должны быть положительными, они варьируются от0 to 2^15 - 1
.Функция сопряжения Кантора :
Теперь функция Шудзика :
Давайте учтем отрицательные целые числа. Это выходит за рамки первоначального вопроса, который я знаю, но просто помогаю будущим посетителям.
Функция сопряжения Кантора :
Функция Шудзика :
Теперь все это пока результат всегда был положительным. В мире со знаком будет еще больше экономии места, если мы сможем перевести половину вывода на отрицательную ось . Вы можете сделать это так для Шудзика:
Что я делаю: применив вес
2
к входам и пройдя через функцию, затем разделю выходной сигнал на два и перенесу некоторые из них на отрицательную ось, умножив на-1
.См. Результаты, для любого ввода в диапазоне числа
16
битов со знаком, выход лежит в пределах32
целого числа битов со знаком, что здорово. Я не уверен, как сделать то же самое для функции сопряжения Кантора, но не пытался так сильно, как это не так эффективно. Кроме того, чем больше вычислений, связанных с функцией сопряжения Кантора, тем медленнее и ее .Вот реализация C #.
Поскольку промежуточные вычисления могут превышать пределы
2N
целого числа со знаком, я использовал4N
целочисленный тип (последнее деление на2
возвращает результат в2N
).Ссылка, которую я предоставил на альтернативное решение, хорошо изображает график функции, использующей каждую точку в пространстве. Удивительно видеть, что вы можете уникально закодировать пару координат в одно число обратимо! Волшебный мир чисел !!
источник
(0,0)
через(65535,65535)
к одному числу, тоa<<16 + b
лучше в основном во всех отношениях (быстрее, проще, легче понять, что более очевидно) . Если вы хотите ,(-32768,-32768)
чтобы(327687,327687)
вместо этого, только при условии 32768 первыми.Если A и B могут быть выражены 2 байтами, вы можете объединить их в 4 байта. Поместите A в самую значительную половину, а B в самую младшую.
В языке C это дает (при условии, что sizeof (short) = 2 и sizeof (int) = 4):
источник
combine()
следуетreturn (unsigned short)(A<<16) | (unsigned short)(B);
так , что отрицательные числа могут быть упакованы надлежащим образом .A<<16
выйдет за пределы. Это должно бытьreturn (unsigned int)(A<<16) | (unsigned short)(B);
Это вообще возможно?
Вы объединяете два целых числа. Оба имеют диапазон от -2 147 483 648 до 2 147 483 647, но вы будете принимать только положительные результаты. Это составляет 2147483647 ^ 2 = 461169E + 18 комбинаций. Поскольку каждая комбинация должна быть уникальной И приводить к целому числу, вам понадобится какое-то магическое целое число, которое может содержать это количество чисел.
Или моя логика ошибочна?
источник
Стандартный математический способ для натуральных чисел состоит в использовании уникальности простой факторизации.
Недостатком является то, что изображение имеет тенденцию охватывать довольно большой диапазон целых чисел, поэтому, когда дело доходит до выражения отображения в компьютерном алгоритме, у вас могут возникнуть проблемы с выбором подходящего типа для результата.
Вы можете изменить это, чтобы иметь дело с отрицательным
x
иy
кодируя флаги со степенями 5 и 7 членов.например
источник
Пусть число
a
будет первым,b
вторым. Позвольтеp
бытьa+1
-th простое число,q
будетb+1
-th простое числоТогда результат
pq
, еслиa<b,
или2pq
еслиa>b
. Еслиa=b
да, то будетp^2
.источник
Не так сложно построить отображение:
Выяснить, как получить значение для произвольного a, b немного сложнее.
источник
f(a, b) = s(a+b) + a
, гдеs(n) = n*(n+1)/2
s(a+b+1)-s(a+b) = a+b+1 < a
.Я не понял, что Вы подразумеваете под:
Как я могу написать (больше чем), (меньше чем) символы на этом форуме?
источник
backtick escapes
.Хотя ответ Stephan202 является единственным действительно общим, для целых чисел в ограниченном диапазоне вы можете добиться большего успеха. Например, если ваш диапазон составляет 0,10 000, то вы можете сделать:
Результаты могут помещаться в одно целое число в диапазоне до квадратного корня из числа целочисленных типов. Это упаковывает немного более эффективно, чем более общий метод Stephan202. Также значительно проще декодировать; не требующий квадратных корней, для начала :)
источник
Для положительных целых чисел в качестве аргументов и там, где порядок аргументов не имеет значения:
Вот неупорядоченная функция сопряжения :
Для x ≠ y вот уникальная неупорядоченная функция сопряжения :
источник
Проверьте это: http://en.wikipedia.org/wiki/Pigeonhole_principle . Если A, B и C одного типа, это невозможно сделать. Если A и B являются 16-разрядными целыми числами, а C - 32-разрядными, то вы можете просто использовать сдвиг.
Сама природа алгоритмов хеширования заключается в том, что они не могут предоставить уникальный хеш для каждого отдельного ввода.
источник
Вот расширение кода @DoctorJ на неограниченные целые числа, основанное на методе, заданном @nawfal. Он может кодировать и декодировать. Он работает с обычными массивами и массивами numpy.
источник
Как насчет чего-то гораздо более простого: учитывая два числа, A и B позволяют str быть конкатенацией: 'A' + ';' + «Б». Тогда пусть выводом будет хеш (str). Я знаю, что это не математический ответ, а простой скрипт на python (который имеет встроенную хэш-функцию) должен выполнить эту работу.
источник
То, что вы предлагаете, невозможно. У вас всегда будут столкновения.
Для сопоставления двух объектов другому отдельному набору сопоставленный набор должен иметь минимальный размер числа ожидаемых комбинаций:
Предполагая 32-разрядное целое число, у вас есть 2147483647 натуральных чисел. Выбор двух из них, где порядок не имеет значения, с повторением дает 2305843008139952128 комбинаций. Это не очень хорошо вписывается в набор 32-битных целых чисел.
Однако вы можете разместить это отображение в 61 бит. Использование 64-разрядного целого числа, вероятно, проще всего. Установите старшее слово на меньшее целое и младшее слово на большее.
источник
Скажем, у вас есть 32-разрядное целое число, почему бы просто не переместить A в первую 16-разрядную половину, а B в другую?
Кроме того, что он настолько компактен, насколько это возможно и дешев, чтобы вычислить, действительно классным побочным эффектом является то, что вы можете выполнять векторную математику для упакованного числа.
источник
давайте иметь два числа B и C, кодирующие их в одно число A
A = B + C * N
где
B = A% N = B
C = A / N = C
источник
Учитывая положительные целые числа A и B, пусть D = количество цифр A имеет, а E = количество цифр B имеет. Результатом может быть объединение D, 0, E, 0, A и B.
Пример: A = 300, B = 12. D = 3, E = 2, результат = 302030012. Это использует тот факт, что единственным числом, начинающимся с 0, является 0,
Pro: Легко кодировать, легко декодировать, удобочитаемый, сначала можно сравнить значимые цифры, возможность сравнения без вычислений, простая проверка ошибок.
Минусы: размер результатов является проблемой. Но это нормально, почему мы в любом случае храним неограниченные целые числа в компьютере.
источник
Если вы хотите больше контроля, например, выделите биты X для первого числа и биты Y для второго числа, вы можете использовать этот код:
Я использую всего 32 бита. Идея здесь в том, что если вы хотите, например, чтобы первое число было до 10 бит, а второе число до 12 бит, вы можете сделать это:
Теперь вы можете хранить в
num_a
максимальном количестве2^10 - 1 = 1023
и вnum_b
максимальном значении2^12 - 1 = 4095
.Чтобы установить значение для числа A и числа B:
Теперь
bnum
все биты (всего 32 бита. Вы можете изменить код, чтобы использовать 64 бита). Чтобы получить число:Чтобы получить число б:
РЕДАКТИРОВАТЬ:
bnum
может храниться в классе. Я этого не делал, потому что для собственных нужд я поделился кодом и надеюсь, что он будет полезен.Спасибо за источник: https://www.geeksforgeeks.org/extract-k-bits-given-position-number/ за функцию извлечения битов и спасибо также за
mouviciel
ответ в этом посте. Используя эти источники, я смог найти более продвинутое решение.источник