忘记密码   免费注册 查看新帖 | 论坛精华区

ChinaUnix.net

  平台论坛 博客 认证专区 大话IT 文库 沙龙 自测 下载 频道自动化运维 虚拟化 服务器 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
最近访问板块 发新帖
查看: 5171 | 回复: 25

[算法] 不用除法怎么求A/3 [复制链接]

帖子
26
主题
13
精华
0
可用积分
39
专家积分
0
在线时间
52 小时
注册时间
2012-10-20
最后登录
2014-02-13
论坛徽章:
0
发表于 2012-10-21 20:57:47 |显示全部楼层
今天看到一个题目,说的是一个32位整数A,要求不用除法,怎么求A/3?

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

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

Rank: 7Rank: 7Rank: 7

帖子
3995
主题
218
精华
0
可用积分
18905
专家积分
11
在线时间
5570 小时
注册时间
2004-03-05
最后登录
2014-11-01
论坛徽章:
52
子鼠
日期:2014-10-25 14:41:132014世界杯徽章
日期:2014-07-08 17:59:432014世界杯徽章
日期:2014-07-08 17:36:012014世界杯徽章
日期:2014-07-08 17:34:352014世界杯徽章
日期:2014-07-08 17:28:282014世界杯徽章
日期:2014-07-08 17:25:352014世界杯徽章
日期:2014-07-03 18:23:072014世界杯徽章
日期:2014-07-01 17:56:202014世界杯徽章
日期:2014-06-30 17:36:282014世界杯徽章
日期:2014-06-30 17:34:34金牛座
日期:2014-09-03 09:54:542014世界杯徽章
日期:2014-06-30 17:32:582014世界杯徽章
日期:2014-07-11 17:18:302014世界杯徽章
日期:2014-07-11 17:20:22天秤座
日期:2014-08-10 14:04:01
发表于 2012-10-21 21:05:20 |显示全部楼层
论坛上有人发过,就是x*2^32/3 MS
薛非

Rank: 9Rank: 9Rank: 9

帖子
10934
主题
118
精华
0
可用积分
45909
专家积分
0
在线时间
6869 小时
注册时间
2009-12-09
最后登录
2014-09-22
论坛徽章:
0
发表于 2012-10-21 21:32:37 |显示全部楼层
用减法         

Rank: 3Rank: 3

帖子
1010
主题
111
精华
0
可用积分
2392
专家积分
0
在线时间
1342 小时
注册时间
2011-07-09
最后登录
2014-07-16
论坛徽章:
5
技术图书徽章
日期:2013-08-17 07:26:49双子座
日期:2013-09-15 16:46:29双子座
日期:2013-09-25 08:17:09技术图书徽章
日期:2013-09-25 09:11:42天秤座
日期:2013-10-01 16:25:34
发表于 2012-10-21 21:39:10 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽

Rank: 7Rank: 7Rank: 7

帖子
1795
主题
223
精华
0
可用积分
11399
专家积分
0
在线时间
1444 小时
注册时间
2004-07-29
最后登录
2014-10-08
论坛徽章:
9
摩羯座
日期:2013-09-16 11:10:27午马
日期:2013-09-27 17:40:42处女座
日期:2013-10-17 18:15:43亥猪
日期:2013-10-23 10:55:49双鱼座
日期:2013-11-21 14:43:56亥猪
日期:2013-11-28 12:03:13申猴
日期:2013-12-06 22:07:00亥猪
日期:2014-03-02 23:46:35午马
日期:2014-04-15 11:08:53
发表于 2012-10-21 22:05:37 |显示全部楼层
本帖最后由 Ager 于 2012-10-21 22:49 编辑

比较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. 这个是为了保险,有点复杂。楼下的那个,更清爽:)




„Zu den Sachen selbst!“

Rank: 7Rank: 7Rank: 7

帖子
1795
主题
223
精华
0
可用积分
11399
专家积分
0
在线时间
1444 小时
注册时间
2004-07-29
最后登录
2014-10-08
论坛徽章:
9
摩羯座
日期:2013-09-16 11:10:27午马
日期:2013-09-27 17:40:42处女座
日期:2013-10-17 18:15:43亥猪
日期:2013-10-23 10:55:49双鱼座
日期:2013-11-21 14:43:56亥猪
日期:2013-11-28 12:03:13申猴
日期:2013-12-06 22:07:00亥猪
日期:2014-03-02 23:46:35午马
日期:2014-04-15 11:08:53
发表于 2012-10-21 22:48:16 |显示全部楼层
本帖最后由 Ager 于 2012-10-22 02:01 编辑

经过优化,还可以有一个超级简单的,更加清爽。同上面那个一样,也是用到了一些数学知识,呵呵……
  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的。

以上,仅供参考,呵呵 ——:)

„Zu den Sachen selbst!“

Rank: 1

帖子
170
主题
6
精华
0
可用积分
344
专家积分
0
在线时间
289 小时
注册时间
2012-01-14
最后登录
2013-02-25
论坛徽章:
0
发表于 2012-10-21 23:47:54 |显示全部楼层
其实这样也行:
  1. #include <cstddef>

  2. template<std::size_t N>
  3. struct div3
  4. {
  5.     static const std::size_t value = 1 + div3<N-3>::value;
  6. };

  7. template<>
  8. struct div3<0>
  9. {
  10.     static const std::size_t value = 0;
  11. };

  12. template<>
  13. struct div3<1>
  14. {
  15.     static const std::size_t value = 0;
  16. };

  17. template<>
  18. struct div3<2>
  19. {
  20.     static const std::size_t value = 0;
  21. };

  22. #include <iostream>

  23. int main()
  24. {
  25.     std::cout << div3<1763>::value << std::endl;
  26.     std::cout << 1763/3 << std::endl;
  27.     return 0;
  28. }
复制代码
怪叔叔

Rank: 3Rank: 3

帖子
1040
主题
22
精华
0
可用积分
2386
专家积分
0
在线时间
1700 小时
注册时间
2011-03-11
最后登录
2014-10-29
论坛徽章:
0
发表于 2012-10-21 23:52:07 |显示全部楼层
ok. 留个名.
========> 纵一苇之所如,凌万倾之茫然 <========

Rank: 1

帖子
170
主题
6
精华
0
可用积分
344
专家积分
0
在线时间
289 小时
注册时间
2012-01-14
最后登录
2013-02-25
论坛徽章:
0
发表于 2012-10-22 00:02:53 |显示全部楼层
本帖最后由 fallening_cu 于 2012-10-22 00:07 编辑

或者这样
  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:
弱弱地问下,大家做有负整数的除法的时候,都是上往上舍入还是往下舍入?

Rank: 7Rank: 7Rank: 7

帖子
1795
主题
223
精华
0
可用积分
11399
专家积分
0
在线时间
1444 小时
注册时间
2004-07-29
最后登录
2014-10-08
论坛徽章:
9
摩羯座
日期:2013-09-16 11:10:27午马
日期:2013-09-27 17:40:42处女座
日期:2013-10-17 18:15:43亥猪
日期:2013-10-23 10:55:49双鱼座
日期:2013-11-21 14:43:56亥猪
日期:2013-11-28 12:03:13申猴
日期:2013-12-06 22:07:00亥猪
日期:2014-03-02 23:46:35午马
日期:2014-04-15 11:08:53
发表于 2012-10-22 02:03:23 |显示全部楼层
本帖最后由 Ager 于 2012-10-22 02:04 编辑
fallening_cu 发表于 2012-10-22 00:02
或者这样
const std::int64_t nagic = magic * n;
P.S:

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


友情提醒

„Zu den Sachen selbst!“

您需要登录后才可以回帖 登录 | 注册

北京皓辰网域网络信息技术有限公司. 版权所有 京ICP证:060528号 北京市公安局海淀分局网监中心备案编号:1101082001
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP