不用除法怎么求A/3

发仔很忙

今天看到一个题目，说的是一个32位整数A，要求不用除法，怎么求A/3？

这让我想到从朋友那里听到的一个问题，写一个函数，实现除法和乘法，但是不能用乘法和除法运算符，乘法还知道怎么实现，

但是除法就百思不得其解，但是今天就出现了这个类似的问题，没弄出来，伤心死了

folklore

论坛上有人发过，就是x*2^32/3 MS

__BlueGuy__

pmerofc 发表于 2012-10-21 21:32
用减法

赞， 循环减...

Ager

比较bt的算法：

1. int DividedBy3(int A) {
   
2.         int Q2_3 = 0, Q3_4 = 0, P = 0;
   
3.         do {
   
4.                 Q3_4 += A >> P++;
   
5.                 Q2_3 += A >> P;
   
6.         } while (P++,P < 31);
   
7.         return (Q3_4 - Q2_3) >> 1;
   
8. }
   

复制代码

以上，仅供参考，呵呵 ——：）

P.S. 这个是为了保险，有点复杂。楼下的那个，更清爽：）

Ager

经过优化，还可以有一个超级简单的，更加清爽。同上面那个一样，也是用到了一些数学知识，呵呵……

1. int DividedBy3(int A) {
   
2.         int p = 0;
   
3.         for (int i = 2; i <= 32; i += 2)
   
4.                 p += A << i;
   
5.         return (-p);
   
6. }

复制代码

经过32-bit整数（包括负整数）测试，OK的。

以上，仅供参考，呵呵 ——：）

fallening_cu

其实这样也行：

1. #include <cstddef>
   
2. 
   
3. template<std::size_t N>
   
4. struct div3
   
5. {
   
6.     static const std::size_t value = 1 + div3<N-3>::value;
   
7. };
   
8. 
   
9. template<>
   
10. struct div3<0>
    
11. {
    
12.     static const std::size_t value = 0;
    
13. };
    
14. 
    
15. template<>
    
16. struct div3<1>
    
17. {
    
18.     static const std::size_t value = 0;
    
19. };
    
20. 
    
21. template<>
    
22. struct div3<2>
    
23. {
    
24.     static const std::size_t value = 0;
    
25. };
    
26. 
    
27. #include <iostream>
    
28. 
    
29. int main()
    
30. {
    
31.     std::cout << div3<1763>::value << std::endl;
    
32.     std::cout << 1763/3 << std::endl;
    
33.     return 0;
    
34. }

复制代码

captivated

ok. 留个名.

fallening_cu

或者这样

1. std::int32_t div3( const std::int32_t n )
   
2. {
   
3.    if ( n < 0 ) return -div3(-n)-1;
   
4.    const std::int64_t magic = 1431655766;
   
5.    const std::int64_t nagic = magic * n;
   
6.    return nagic >> 32;
   
7. }

复制代码

P.S:
弱弱地问下，大家做有负整数的除法的时候，都是上往上舍入还是往下舍入？

Ager

fallening_cu 发表于 2012-10-22 00:02
或者这样
const std::int64_t nagic = magic * n;
P.S:

发仔很忙 发表于 2012-10-21 20:57
写一个函数，实现除法和乘法，但是不能用乘法和除法运算符，乘法还知道怎么实现，……

友情提醒