埃及乘法代码实现
2019-08-16 07:54:32来源:博客园 阅读 ()
埃及乘法代码实现
什么是埃及乘法
埃及乘法的思路是:反复地将n减半,并将a加倍,同时求出a的各种倍数,这些倍数与a的比值都是2的整数次幂。n的值为奇数部分的a之和即为所求值
举个栗子:41 x 59
1 41 59 √
2 20 118
4 10 236
8 5 472 √
16 2 944
32 1 1888 √
41 x 59 = (1 x 59) + (8 x 59) + (32 x 49)
递归实现
1 bool odd(int n) { return n & 0x01; } // n是否为奇数 2 int half(int n) { return n >> 1; } // n / 2 3 int doubling(int n) { return n << 1; } // n * 2 4 int multiply1(int n, int a) 5 { 6 if (n == 1) return a; 7 int ret = multiply1(half(n), double(a)) 8 if (odd(n)) ret += a; 9 return ret; 10 }
循环实现
bool odd(int n) { return n & 0x01; } // n是否为奇数 int half(int n) { return n >> 1; } // n / 2 int doubling(int n) { return n << 1; } // n * 2 int multiply1(int n, int a) { int ret = 0; while (true) { if (odd(n)) { ret += a; if(n==1) break; } a = doubling(a); n = half(n); } return ret; }
以上是阅读《数学与泛型编程:高效编程的奥秘》所做的笔记,书上还提有更优化的方法,但本人觉得有点多余,这样就很简洁高效了。
原文链接:https://www.cnblogs.com/HuangWj/p/11248411.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- opencv-12-高斯滤波-双边滤波(附C++代码实现) 2020-05-10
- C++ 存储持续性 2020-05-10
- Android P HIDL demo代码编写 (原创) 2020-05-07
- 前缀和 2020-05-04
- 纯虚函数与基类指针数组的运用 代码参考 2020-04-30
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash