| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2193 人关注过本帖
标题:看到一道有意思的题:累加求和,不能用乘除、if,for,while,case,等及条件语 ...
只看楼主 加入收藏
wfoo
Rank: 3Rank: 3
等 级:论坛游侠
威 望:7
帖 子:120
专家分:134
注 册:2011-8-6
收藏
得分:0 
不需要终止条件,等差数列求和公式,因为整数的位数确定,实现乘法除法用32或者64次展开的循环,位运算加减法可以实现。c语言还有个知识点可能有用,a>b的值为0或1,减1就为,-1或0,这样的表达式既可以做数组下标,又可以做位与的掩码,但这个表达式是不需要if的
2015-10-30 00:32
wfoo
Rank: 3Rank: 3
等 级:论坛游侠
威 望:7
帖 子:120
专家分:134
注 册:2011-8-6
收藏
得分:0 
还有一种方法,如果使用gcc编译器,不用if我照样可以用goto完全实现if的功能
2015-10-30 00:43
pycansi
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:5
帖 子:418
专家分:1060
注 册:2012-7-26
收藏
得分:0 
回复 21楼 wfoo
不太清楚兄台 “整数位数确定” 具体指什么。
不过 a>b 这个表达式暗含 if


莫问前尘有愧,但求今生无悔
2015-10-30 06:21
wfoo
Rank: 3Rank: 3
等 级:论坛游侠
威 望:7
帖 子:120
专家分:134
注 册:2011-8-6
收藏
得分:0 
整数位数是说int为32位,long为64位,这样的乘法用32次或者64次循环是可以实现乘法的,把这的循环展开就不需要if了。a<b是不需要if的,它只要比较,和条件分支不一样。平常的if属于条件加跳转,这个有条件没跳转。还有一点,编译器优化够强,我上面给出的递归也可以不要条件跳转的,相当于也可以不要if
2015-10-30 06:40
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
这是知乎上另一位高手实现的,原为c++,我改为c。完全使用左右位移方法完成32位乘法,我当初也是想用位移实现,只是没找到算法,这个代码看的有点晦涩,但确实达到了目的,并且比递归更能符合题意(递归的短路算法在汇编级肯定有条件判断跳转的)。
#include <stdio.h>
int mul(int n,int m)
{
    int c[2] = { 0, n };
#define BITMUL(i) (c[ 1 & ((m) >> (i))]<<(i)) //m第i位乘n
#define BYTEMUL(i) (BITMUL((i<<3))+BITMUL((i<<3)+1)+BITMUL((i<<3)+2)+BITMUL((i<<3)+3)+BITMUL((i<<3)+4)+BITMUL((i<<3)+5)+BITMUL((i<<3)+6)+BITMUL((i<<3)+7))//m第i字节乘n
#define INTMUL()  (BYTEMUL(0)+BYTEMUL(1)+BYTEMUL(2)+BYTEMUL(3)) //m乘n
    return INTMUL();
#undef BITMUL
#undef BYTEMUL
#undef INTMUL
}

int f(int n)
{
    return mul(n, n + 1) >> 1;
}

void main()
{
    printf("%d\n",f(100));
}

能编个毛线衣吗?
2015-10-30 07:48
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
回复 24楼 wfoo
25楼的代码可能符合你的说法,不过是用宏展开的,减少了代码量。

能编个毛线衣吗?
2015-10-30 07:54
wfoo
Rank: 3Rank: 3
等 级:论坛游侠
威 望:7
帖 子:120
专家分:134
注 册:2011-8-6
收藏
得分:0 
位数确定,乘除法都是很容易实现。过了学习的阶段,只是花这个闲功夫折腾这个不值得,不如静静的来喝杯茶。
2015-10-30 07:56
wfoo
Rank: 3Rank: 3
等 级:论坛游侠
威 望:7
帖 子:120
专家分:134
注 册:2011-8-6
收藏
得分:0 
就比如w版主的给的第一份代码,也是可以不要隐含if的,汇编里面应该有一类条件赋值语句叫CMOVxx,好像叫这个,性能比if跳转高。像这种问题那个代码我觉得是最好的
2015-10-30 08:04
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
常保好奇之心啊!
早几年单打独斗写程序还能有点用途,现如今编程已经于我工作、生活毫无瓜葛,不做点奇葩的题目提提兴趣,估计过两年就全忘了。

能编个毛线衣吗?
2015-10-30 08:08
pycansi
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:5
帖 子:418
专家分:1060
注 册:2012-7-26
收藏
得分:0 
回复 24楼 wfoo
我们对 if 的定义不太一样


莫问前尘有愧,但求今生无悔
2015-10-30 08:09
快速回复:看到一道有意思的题:累加求和,不能用乘除、if,for,while,case,等及条 ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.038814 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved