- 论坛徽章:
- 0
|
我来说说加法吧
为了说明方便, 先考虑3个数字没有重复的情况, 那么最简单的就是用`mode bit'方式. 这里假设<<是类似C中的left shift operator, 那么映射关系是f(n)=1<<(n-1)=2^(n-1):
- #digit->bit
- 1 -> 1<<0=1
- 2 -> 1<<1=10
- 3 -> 1<<2=100
- 4 -> 1<<3=1000
- ...
- 9 -> 1<<8
复制代码
那么每个没有重复数字的组合, 都可以通过bit or操作实现叠加, 比如:
- 235 -> 1<<1|1<<2|1<<4 = 10110
复制代码
也就是说从右往左, 第2,3,5位是1, 其他是0
如果上面的你看明白了, 那么允许数字重复出现的映射也是很简单的. 以3个数字为例. 如果每个1都对应二进制的1, 那么三个1就对应1+1+1=3=11(base 2), 显然每个数字最多占用2个bit, 所以现在2不再对应10, 而是100, 3个2对应1100, 以此类推. 映射关系可以表示为 f(n)=1<<(2n-2)=2^(2n-2):
- 1 -> 1<<0=1
- 2 -> 1<<2=1,00
- 3 -> 1<<4=1,00,00
- 4 -> 1<<6=1,00,00,00
- ...
- 9 -> 1<<16
复制代码
比如332, 就被转化为1,00,00 + 1,00,00 + 1,00 = 11,01,00. 从右往左2bit一组, 那么第n组就代表了数字n的状态, 00, 01, 10, 11分别表示这个数字出现了0,1,2,3次
in general, 如果允许n个重复数字, 那么每个数字就需要b = 1+int[log_2(n)]个bit来表示, 比如n=4(100),5(101),6(110),7(111), b=3. f(n)=1<<(b*n-b)=2^(b*n-b), 而且很明显, 同一b周期内, 这种编码的效率在n=2^k-1, k=1,2,...时最高 (saturation), 在n=2^k时最低 |
|