不用64位乘除法，求 uint64_t 对 10^9 的余数

gxqcn

前段日子，硬件部寻求帮助：需要快速求 uint64_t 对 10^9 的余数，且不能用到64位乘除法（当然也就不能对64位整数直接取余运算，因为硬件或编译器不支持）。
但他们的要求也比较特别，仅需知道该余数是位于 \(10^9\) 的前半段还是后半段即可。

问题现已解决，但历程比较有探讨意义。
如果是你，会怎么设计和优化算法？

gxqcn

这是个纳秒计时器，需要判定当前时间是1秒的前半部还是后半部，来决定一个LED灯的亮或灭。

wayne

硬件或编译器不支持 取余和除法。  那能支持的操作有哪些，

gxqcn

64位整数的移位、加减、比较运算；
32位整数的移位、加减乘除模余、比较运算等

liangbch

那只能使用 移位 比较 减 这些指令了

liangbch

sorry,能执行32位运算，那就好多了。

wayne

$10^9 = 111011100110101100101000000000_2$ ,总共占去30位， 所以只需根据10^9的二进制表达的模板，对该uint64_t数据的低30位做符号判断。即从uint64_t数据的第 30位，第29位，第28位，第27位，比对10^9的二进制表达对应位的值，依次是 1,1,1,0，....，发生符号变化就停止判断。如果有一位开始从0变成1，则是 纳秒的后半段时间，即大于半个纳秒，如果有一位开始从1变成0，则是纳秒的前半段，即小于半个纳秒

wayne

梳理一下应用场景和需求: 这个纳秒计时器的工作过程就是，从硬件传感器获取的是一个uint64_t的二进制存储的数据，其涵义应该就是从某个epoch time到现在所经过的时钟周期个的数吧？然后这个硬件计时器想做一点工作，展现给我们用户的是一个十进制的纳秒值，因为取整有误差，所以再用一个辅助的LED颜色变化显示这个纳秒值取是上半段还是下半段。
=========
再来梳理实现，前面提及的计时器所做的呈现纳秒的工作，大致这样，取uint64_t的第31位到第64位，即是纳米的二进制表达的整数部分，直接传给上位机应用，做二进制到十进制的转化，其分数部分截断扔掉，用上半段下半段的LED灯光显示。

只是呼吸

不能做除法，愁！除法固然慢点，但总比没有好。顶层设计人员应该设计一些代替除法的指令。

gxqcn

注意，是随机访问这个纳秒计时器。
可以关闭指示灯，也许几个小时都不调用它；但调用时，要确保精度。