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

liangbch

64比特的数除以\(10^9\)的商最多35比特
若硬件不支持64位数，只能做两个32位数的乘积且乘积也最多保留最低32位，那么就只能表示为\(2^{16}\)进制数再做除法了，具体做法

1.将被乘数看成4位(\(2^{16}\)进制）数，并在高位补零，变成5位数
2.将乘数看成2位(\(2^{16}\)进制）数，这样就将原问题转化为一个5位数除以2位数的问题。
3.在这里，5位数除以2位数的商为3位数，故需要做3次“3位数除以2位数”的运算。下面我们重点分析一下这个“3位数除以2位数”的子运算
  
3.1  我们能够证明，这个3位数(48比特）最高2个比特为总是0。因为在运算过程中，余数总是小于除数，故被除数总是小于\({10}^9*2^{16}<2^{46}\)
3.2 \( a/{10^9}\)= \((a * 2^{45} / 10^9) / 2^{45}\)= \( (a * 35184.372088832)/2^{45}\)
3.3 将48位被除数记为a，除数\({10^9}\)记为d，被除数最高18位记为a0，因为最高2位为0，故a0不超过16比特，做下列运算
    1. a0=a>>30,    即取a的最高18位。
    2. q=a0*35184  
    3. q=(q>>15)   
    4. a -= d *q
    5. 若a>d, 则q++, a-=d
    6. 若a>d, 则q++, a-=d

注： 步骤1到步骤3，相当于 \(q = (a/2^{30})*35184/2^{15}= a * 35184/2^{45} \)

happysxyf

uint64_t a, q;
q= a-((a>>30)<<30)

BBP算法是计算16进制的派，我觉得可以先弄成16进制的，在转化为10进制。

liangbch

说明：
1。若被除数的范围更小，小于\(2^{32}*{10}^9\), 则只需2次除法。
2. 由于第一次除法中，被除数远小于\2^46\), 故可将试商步骤改为如下序列，减少一次调整商步骤。
    1. a0=a>>16,    即取a的中16位。
    2. q=a0*35184  
    3. q=(q>>29)   
    4. a -= d *q
    5. 若a>d, 则q++, a-=d

gxqcn

需要注意对方需求的特别之处，仅需返回一个布尔值即可。

happysxyf

基本实现，只要允许使用while循环和数组，下面代码就成立。不知题目中的纳秒是什么数量级，是C#中的纳秒，还是10的-9次方秒。我只能做到0.0000001秒出结果。并且全程没用任何乘除。

1. /*COPYRIGHT@2016~2018 BY HAPPY*/
   
2. 
   
3. #include <stdio.h>
   
4. 
   
5. typedef unsigned long long uint64_t;
   
6. static const int mang[64]={1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 73741824, 147483648, 294967296, 589934592, 179869184, 359738368, 719476736, 438953472, 877906944, 755813888, 511627776, 23255552, 46511104, 93022208, 186044416, 372088832, 744177664, 488355328, 976710656, 953421312, 906842624, 813685248, 627370496, 254740992, 509481984, 18963968, 37927936, 75855872, 151711744, 303423488, 606846976, 213693952, 427387904, 854775808};
   
7. 
   
8. //uint64_t取余函数
   
9. int Uint64ModBillion(uint64_t a)
   
10. {
    
11.         int S=0, *p=(int*)mang;
    
12.         while(a){
    
13.                 if(a-((a>>1)<<1)){
    
14.                         S+=*p, S=(S>=1000000000)?S-=1000000000:S;
    
15.                 }
    
16.                 a>>=1, p++;
    
17.         }
    
18.         return S;
    
19. }
    
20. 
    
21. //主函数入口
    
22. int main()
    
23. {
    
24.         uint64_t a=8446744073709551616;
    
25.         printf("%d\n", Uint64ModBillion(a));
    
26.         return 0;
    
27. }
    

复制代码

下面是返回bool类型的函数

1. 
   
2. /*COPYRIGHT@2016~2018 BY HAPPY*/
   
3. 
   
4. #include <stdio.h>
   
5. #include <stdbool.h>
   
6. typedef unsigned long long   uint64_t;
   
7. typedef unsigned long        uint32_t;
   
8. static const uint32_t mang[64]={1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 73741824, 147483648, 294967296, 589934592, 179869184, 359738368, 719476736, 438953472, 877906944, 755813888, 511627776, 23255552, 46511104, 93022208, 186044416, 372088832, 744177664, 488355328, 976710656, 953421312, 906842624, 813685248, 627370496, 254740992, 509481984, 18963968, 37927936, 75855872, 151711744, 303423488, 606846976, 213693952, 427387904, 854775808};
   
9. 
   
10. //uint64_t取余函数
    
11. bool Uint64ModBillion(uint64_t a)
    
12. {
    
13.         uint32_t S=0, *p=(uint32_t*)mang;
    
14.         while(a){
    
15.                 if(a-((a>>1)<<1)){
    
16.                         S+=*p, S=(S>=1000000000)?S-=1000000000:S;
    
17.                 };
    
18.                 a>>=1, p++;
    
19.         }
    
20.         return (S<500000000)?true:false;
    
21. }
    
22. 
    
23. //主函数入口
    
24. void main()
    
25. {
    
26.         uint64_t a=8073709551616;
    
27.         Uint64ModBillion(a)?fputs("TRUE\n", stdout):fputs("FALSE\n", stdout);
    
28. }
    

复制代码

liangbch

楼上的代码可以进一步优化，实际上a最低的29bit是无需查表计算的，跳过最低的29比特，最大循环次数可从64减少到36.

1. static const uint32_t mang[]=
   
2. {
   
3.         536870912, 73741824, 147483648,
   
4.         294967296,         589934592, 179869184, 359738368, 719476736, 438953472, 877906944, 755813888,
   
5.         511627776,         23255552, 46511104, 93022208, 186044416, 372088832, 744177664, 488355328,
   
6.         976710656,        953421312, 906842624, 813685248, 627370496, 254740992, 509481984, 18963968,
   
7.         37927936,         75855872, 151711744, 303423488, 606846976, 213693952, 427387904, 854775808
   
8. };
   
9. 
   
10. 
    
11. //uint64_t取余函数
    
12. bool Uint64ModBillion2(uint64_t a)
    
13. {
    
14.         uint32_t S;
    
15.         uint32_t *p=(uint32_t*)mang;
    
16.        
    
17.         S= a & ( (1<<29)-1);
    
18.         a>>=29;
    
19. 
    
20.         while (a)
    
21.         {
    
22.                 if (a & 1)
    
23.                 {
    
24.                         S+=*p, S=(S>=1000000000)?S-=1000000000:S;
    
25.                 };
    
26.                 a>>=1, p++;
    
27.         }
    
28. 
    
29.         return (S<500000000)?true:false;
    
30. 
    
31. }
    

复制代码

liangbch

还有， 我把 ”if(a-((a>>1)<<1))“ 改成了 “if (a & 1）”

mathe

应该考虑一下将除以常数转化为乘以常数的算法，而且最终我们只需要取其中一个比特的信息

liangbch

mathe 发表于 2017-1-15 11:12
应该考虑一下将除以常数转化为乘以常数的算法，而且最终我们只需要取其中一个比特的信息

11楼就是这个方法呀，我想不出更快的算法。

只是呼吸

基本实现，只要允许使用while循环和数组，下面代码就成立。不知题目中的纳秒是什么数量级，是C#中的纳秒，还是10的-9次方秒。我只能做到0.0000001秒出结果。并且全程没用任何乘除。

happysxyf写的这个程序，我试了几个数，结果是对的。你们都厉害啊，乘法、除法都不用，就把除法做出来了。看来除法指令是给我们初学者安排的。

我猜测 liangbch 对这类问题有研究，会更好些。