作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我需要什么
我需要一个产生双射输出的算法。我有一个 31 位输入,需要一个伪随机 31 位输出。
我考虑过的
CRC 在其位宽内是双射的。
我查看了 Google 并找到了多项式,但找不到表格或算法。
谁能指出我正确的方向?
我需要一个使用多项式的 CRC-31 算法,比如说 0x737e312b,或者任何可以满足我需要的双射函数。
注意
我找到了下面的代码,但不幸的是我没有编译和运行它的工具。
最佳答案
对于任何哈希函数hash
,你可以这样做:
function bijectiveHash31(int val) {
val &= 0x7FFFFFFF; //make sure it's 31 bits
for (int i=0; i<5; ++i) {
// the high bits affect the low bits
val ^= hash(val>>15) & 32767;
// rotate bits
val = ((val&32767)<<16) | ((val>>15)&65535);
}
return val;
}
这是一个 Feistel 结构,它构成了许多密码的基础:https://en.wikipedia.org/wiki/Feistel_cipher
如果您需要它的速度快而不需要它非常好,那么这很好用:
function bijectiveHash31(int val) {
val = ((val*RANDOM_ODD_NUMBER) + RANDOM_NUMBER) & 0x7FFFFFFF;
val ^= (val>>15);
val ^= (val>>8);
return val;
}
在这两种情况下,弄清楚如何撤消每个基本操作并不太,这表明整个散列是双射的。如果您需要帮助建立乘法,请参阅 https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
关于algorithm - 31 位双射(完美)哈希算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55957869/
这是一个我正在尝试为其创建最佳解决方案的问题。我在 [0...N] 范围内有一组有限的非负整数。我需要能够将此集合中的每个数字表示为一个字符串,并能够将此类字符串向后转换为原始数字。所以这应该是一个双
我是一名优秀的程序员,十分优秀!