Jump to content
彼岸论坛
欢迎抵达彼岸 彼岸花开 此处谁在 -彼岸论坛

[程序员] 分享一个空间利用率超高的 Base36 算法


Recommended Posts

Posted

很久以前学习 C 语言时写的一个练手项目,在常规的进制转换上做了些改进。

https://github.com/EtherDream/base36_914

进制转换一般分两种。一种将整个输入数据当做一个大数,然后不断模 N 和除 N ,将大数分解成一堆 N 以内的数据,从而实现 BaseN 。这种方案空间效率最高,借助大数库实现也不难,只是大数运算非常耗性能。

另一种方案则是每次取 4 或 8 字节到寄存器中,然后不断模 N 和除 N 进行分解。这种方案性能高,实现简单,但空间利用率可能不高。

本方案 Base36 编码时每次读取 9 字节到一个 u8 和 u64 中,利用除法和取模上小技巧,只需少数计算即可将其分解成 14 个字符。空间利用率为 64.2%,相比 Base36 的理论效率 64.6% 只差 0.5%。(不考虑尾块填充的情况下)

在线演示: https://etherdream.com/base36/

如果存在 BUG 或者有更好的改进方案,欢迎提出建议。

  • 游客注册

    游客注册

  • Members

    No members to show

  • Recent Status Updates

    No Recent Status Updates
  • Recently Browsing

    • No registered users viewing this page.
×
×
  • Create New...