Как математически определить уникальное число для любых двух in64?

Question

[anatoly60]

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

Answer 1

[bobrovskyserg]

Ну как тебе сказать, Незнайка...
Вот нахрена нам тратиться на 2 произвольных числа int64, когда бы их можно было впихнуть в одно int64.
Вот и думай...
1 бит содержит 1 бит информации.
2*64бита содержит 2*64 бита информации.
О, Шенон, на кого ты нас покинул!

Comments

[anatoly60]

5 xor 10 = 15
10 xor 5 = 15

есть ли еще числа для которых xor = 15 ?

[anatoly60]

anatoly60: сам спрашиваю, сам отвечаю :) 12 xor 3 = 15. Все равно неужели нет хэш функции или математического приема для решения подобной задачи?

[bobrovskyserg]

Дружище, вернёмся к корням.
Можно ли зашифровать 2 бита в одном? Подумай.
Случай этот хорош тем, что несложно расписать таблицу состояний.
Валяй, шифруй одним битом:
00
01
10
11

[localghost]

anatoly60: Извините, попробую встрять и с другой точки зрения объяснить.
Сколько всего бывает int64? Сколько тогда всего бывает уникальных пар (int64, int64)?

[bobrovskyserg]

localghost:
Смотри:
Если 2 числа не одинаковые, то они разные.
Как это понять?
Ну, например, можно вычесть одно из другого - если разность не ноль - точняк, разные.
Можно еще их сравнить побитово.
Всего бывает 2^64 чисел типа int64.
Я сам не проверял, но инфа 100%.
А пар, стало быть, 2^64*2^64 = 2^128

[localghost]

bobrovskyserg: Зачем вы мне-то это объясняете? :)

[bobrovskyserg]

localghost:
Пардон, зарапортовался :)

Answer 2

[Mercury13]

Нельзя, простая комбинаторика.
Одно число — 2⁶⁴ варианта, два числа — 2¹²⁸ вариантов.
Принцип Дирихле говорит, что в одной из клеток будут даже не два кролика, а как минимум ceil(2¹²⁸/2⁶⁴) = 2⁶⁴ кролика — то есть для какого-то ответа будут как минимум 2⁶⁴ пары аргументов, которые его дают.

Comments

[bobrovskyserg]

Знание принципа Дирихле заслуживает всяческого поощрения, коллега.

[Mrrl]

С другой стороны, вероятность того, что для каких-то двух пар эти числа совпадут, равна 2^(-64). И даже для миллиарда пар шансы получить одинаковый код хотя бы у двух будут меньше 1%. С практической точки зрения, этим можно пренебречь. Так что a+b*3141592653 будет вполне подходящим вариантом. Посчитать его с помощью битовых операций трудно, но можно.

[Mercury13]

Mrrl: Ну что сказать? GUID был придуман именно как распределённая система, дающая в основном разные значения. Но и она даёт сбои. Наиболее известный случай совпадения GUID’ов — PIF-ярлык в Win98 и ZipMagic 2000. При установке второго перестают работать ярлыки на DOS-программы.