朋友给了个题:
对1-500000000(别数了,5亿)的整数,实现一个encode编码方法,要求编码后的字符串只包含数字和字母,然后对应实现一个decode方法,可以将该字符串还原回去。
比如:
- encode(123) => ‘jh52a2’
- decode(‘jh52a2’) => 123
[要求]
- 编码后的字符串尽可能的短
- 不能明显看出连续的两个数字编码后的字符也是连续的:
- 123=>’jh52a2′ 124=>’jh52a3′ 就不符合要求
- 123=>’jh52a2′ 124=>’jh58iu’ 勉强符合
- 123=>’jh52a2′ 125=>’iu92s1′ 这就很好了
编码的方式我们其实接触过许多,最常见的莫过于:Base64了。编码与加密的区别在于,在知道算法的前提下,可以很容易得出编码前的值,而加密则需要密钥方可解密。所以决定了编码与加密的应用场景不一样,在算法公开的情况下,加密用于数据安全,而编码用于数据传输与存储。而在算法不公开的情况下,编码在一定情况下也可以当加密使用。
言归正传,分析下上面的题:
- 使用数字、字母作为编码因子,意味着我们可以使用的因子数有62个:[0-9a-zA-Z],而涉及到数值的话,我们考虑使用62进制
- 5位62进制容量为 62x62x62x62x62 = 916132832,所以我们用5位编码即可表示1-5亿的整数
- 两个连续数字的二进制如:
100110
与100111
需要通过何种变换让其结果不明显连续?考虑位运算:- 异或运算:c=a^b;a=b^c;b=a^c;
- 自定义移位运算:
1101001
右移三位:0011101
当然,自己一开始在做的过程中并不是一次性这么想的,经过了多次坎坷的调整。
首先,实现62进制与10进制互转的方法:
const radix62 = (function radix62() {
// 打乱基本单位,不按常规的0-9a-zA-Z
const code = 'tkI8oWKbxh0VcpuZO7yq3QwrRHPT9evsjlFzSGYXCm1AigUBd4LMJN6n2af5DE';
return {
encode(dec) {
let str = ''
do {
let quotient = Math.floor(dec / 62)
let remainer = dec - quotient * 62
str = code[remainer] + str
dec = quotient
} while (dec)
return str
},
decode(str) {
return [...str].reduce((acc, cur, index) => {
let pos = code.indexOf(cur)
if (pos === -1) throw new TypeError(`字符串:“${str}”中含有非62进制字符:“${cur}”`)
return acc += pos * 62 ** (str.length - index - 1)
}, 0)
}
}
})()
实现方式很简单,参考10进制如何转2进制、如何转16进制的方法,依葫芦画瓢。
然后再来实现自定义的位运算,这里对题目要求扩展下,虽然我们计算了表示5亿只需5位62进制,我们可以设计传入任意位表示:
class BitHanler {
static getBitHanle(bitCount) {
return new this(bitCount)
}
// 在str前补零,直至长度达到 bitCount
static pad0(str, bitCount) {
return ('0'.repeat(bitCount) + str).slice(-bitCount)
}
constructor(bitCount) {
this.bitCount = bitCount
this.isOdd = bitCount % 2 !== 0
this.cls = this.constructor
}
// 十进制整数dec转二进制,并补零至bitCount位
toBitCountBinary(dec) {
return this.cls.pad0(dec.toString(2), this.bitCount)
}
// 移动二进制位,不同于 <<、>>运算,此运算挪出的位置会补到头或尾
bitMov(dec, x, toRight = false) {
let str = this.toBitCountBinary(dec)
const pos = toRight ? -x : x;
str = str.slice(pos) + str.slice(0, pos)
return parseInt(str, 2)
}
rightMov(dec, x) {
return this.bitMov(dec, x, true)
}
leftMov(dec, x) {
return this.bitMov(dec, x)
}
/**
* 核心方法,dec转成bitCount位的二进制后,均匀划分为两段 a,b
* a,b异或运算得到c: c = a ^ b
* 拼接得到新的二进制形式: ca
* 解码的时候同样的操作流程不过需要进行两遍:
* b = c ^ a 得到 bc
* a = b ^ c 得到 ab
* @param {Number} dec
*/
bitXorAndSwap(dec) {
const bin = this.toBitCountBinary(dec)
const splitPoint = Math.floor(this.bitCount / 2)
const left = bin.slice(0, splitPoint)
const right = bin.slice(this.isOdd ? splitPoint + 1 : splitPoint)
const middle = this.isOdd ? bin[splitPoint] : '';
const newLeft = (parseInt(left, 2) ^ parseInt(right, 2)).toString(2)
return parseInt(newLeft + middle + left, 2)
}
}
有了62进制转换方式和位运算操作方法,我们就可以来实现encode
和decode
了:
class MyEncoder {
static getEncoder(targetLen, salt) {
return new this(targetLen, salt)
}
// 计算targetLen长度的62进制最多用多少位二进制表示
static getBitCount(targetLen) {
// targetLen长度的62进制数字容量
let volume = 62 ** targetLen
let bitCount = volume.toString(2).length
// bitCount位的二进制不能溢出
if (2 ** bitCount >= volume) bitCount--
return bitCount
}
constructor(targetLen, salt) {
this.targetLen = targetLen
this.bitCount = this.constructor.getBitCount(targetLen)
this.bitHanler = BitHanler.getBitHanle(this.bitCount)
this.max = 2 ** this.bitCount // 能处理的最大数值
this.moveBits = 3
this.loops = 6
//TODO 根据 salt 计算 moveBits 与 loops
}
encode(dec) {
if (dec < 0 || dec >= this.max)
throw new RangeError(`待编码的数值超出范围:[0, ${this.max})`)
let i = 0
while (i++ < this.loops) {
dec = this.bitHanler.rightMov(this.bitHanler.bitXorAndSwap(dec), this.moveBits)
}
return radix62.encode(dec)
}
decode(str) {
if (str.length < 1 || str.length > this.targetLen)
throw new RangeError(`待解码的字符长度超出了设定的长度: 0 < len < ${this.targetLen + 1}`)
let dec = radix62.decode(str)
if (dec >= this.max) throw new RangeError(`待解码字符解码过程中溢出了,请确认该字符是否正确:${str}`)
let i = 0
while (i++ < this.loops) {
dec = this.bitHanler.bitXorAndSwap(
this.bitHanler.bitXorAndSwap(
this.bitHanler.leftMov(dec, this.moveBits)
)
)
}
return dec
}
}
验证:
const encoder = MyEncoder.getEncoder(5)
const str0 = encoder.encode(965432)
const str1 = encoder.encode(965433)
const dec0 = encoder.decode(str0)
const dec1 = encoder.decode(str1)
console.log(str0, dec0)
console.log(str1, dec1)
// p4Eoy 965432
// hOrac 965433