摘要:算法一直是程序员进阶的一道龙门,通常算法都是为了更高效地解决问题而创造的,但也有的只是出于学术性,并不在意其实际意义。这是近日在国外技术问答网站stackoverflow的一个热门问题,不知道你能给出几种解决方法?
导读:算法一直是程序员进阶的一道龙门,通常算法都是为了更高效地解决问题而创造的,但也有的只是出于学术性,并不在意其实际意义。这是近日在国外技术问答网站stackoverflow的一个热门问题,不知道你能给出几种解决方法?
问:在不使用*、/、+、-、%操作符的情况下,如何求一个数的1/3?(用C语言实现)
第一种方法:使用位操作符并实现“+”操作
- //替换加法运算符
-
intadd(intx,inty){
-
inta,b;
-
do{
- a=x&y;
- b=x^y;
- x=a<<1;
- y=b;
- }while(a);
-
returnb;
- }
-
-
intdivideby3(intnum){
-
intsum=0;
-
while(num>3){
- sum=add(num>>2,sum);
- num=add(num>>2,num&3);
- }
-
if(num==3)
- sum=add(sum,1);
-
returnsum;
- }
原理:n = 4 * a + b; n / 3 = a + (a + b) / 3; 然后 sum += a, n = a + b 并迭代; 当 a == 0 (n < 4)时,sum += floor(n / 3); i.e. 1, if n == 3, else 0
第二种方法:
-
#include<stdio.h>
-
#include<stdlib.h>
-
intmain()
- {
-
FILE*fp=fopen("temp.dat","w+b");
-
intnumber=12346;
-
intdivisor=3;
-
char*buf=calloc(number,1);
- fwrite(buf,number,1,fp);
- rewind(fp);
-
intresult=fread(buf,divisor,number,fp);
- printf("%d/%d=%d",number,divisor,result);
- free(buf);
- fclose(fp);
-
return0;
- }
第三种方法:
- log(pow(exp(number),0.33333333333333333333))
增强版:
- log(pow(exp(number),sin(atan2(1,sqrt(8)))))
第四种方法:
-
#include<stdio.h>
-
#include<stdlib.h>
-
intmain(intargc,char*argv[])
- {
-
intnum=1234567;
-
intden=3;
-
div_tr=div(num,den);
- printf("%d\n",r.quot);
-
return0;
- }
第五种方法:使用内联汇编
- #include<stdio.h>
- intmain(){
- intdividend=-42,divisor=3,quotient,remainder;
-
- __asm__("movl%2,%%edx;"
- "sarl$31,%%edx;"
- "movl%2,%%eax;"
- "movl%3,%%ebx;"
- "idivl%%ebx;"
- :"=a"(quotient),"=d"(remainder)
- :"g"(dividend),"g"(divisor)
- :"ebx");
-
- printf("%i/%i=%i,remainder:%i\n",dividend,divisor,quotient,remainder);
- }
第六种方法:
-
-
intdiv3(inti){
-
charstr[42];
- sprintf(str,"%d",INT_MIN);
-
if(i>0)str[0]='';
- itoa(abs(i),&str[1],3);
- str[strlen(&str[1])]='\0';
-
returnstrtol(str,NULL,3);
- }
第七种方法:
- unsigneddiv_by(unsignedconstx,unsignedconstby){
- unsignedfloor=0;
-
for(unsignedcmp=0,r=0;cmp<=x;){
-
for(unsignedi=0;i<by;i++)
- cmp++;
- floor=r;
- r++;
- }
-
returnfloor;
- }
替换掉上面算法的++运算符:
- unsignedinc(unsignedx){
-
for(unsignedmask=1;mask;mask<<=1){
-
if(mask&x)
- x&=~mask;
- else
-
returnx&mask;
- }
-
return0;
- }
这个版本更快一些:
- unsignedadd(charconstzero[],unsignedconstx,unsignedconsty){
-
-
return(int)(uintptr_t)(&((&zero[x])[y]));
- }
-
- unsigneddiv_by(unsignedconstx,unsignedconstby){
- unsignedfloor=0;
-
for(unsignedcmp=0,r=0;cmp<=x;){
- cmp=add(0,cmp,by);
- floor=r;
- r=add(0,r,1);
- }
-
returnfloor;
- }
第八种方法:实现乘法
-
intmul(intconstx,intconsty){
-
returnsizeof(struct{
-
charconstignore[y];
- }[x]);
- }
第九种方法:极限
-
publicstaticintdiv_by_3(longa){
- a<<=30;
-
for(inti=2;i<=32;i<<=1){
- a=add(a,a>>i);
- }
-
return(int)(a>>32);
- }
-
-
publicstaticlongadd(longa,longb){
-
longcarry=(a&b)<<1;
-
longsum=(a^b);
-
returncarry==0?sum:add(carry,sum);
- }
原理:
因为, 1/3 = 1/4 + 1/16 + 1/64 + ...
所以,
a/3 = a * 1/3
a/3 = a * (1/4 + 1/16 + 1/64 + ...)
a/3 = a/4 + a/16 + 1/64 + ...
a/3 = a >> 2 + a >> 4 + a >> 6 + ...
第十种方法:
- publicstaticintDivideBy3(inta){
- boolnegative=a<0;
- if(negative)a=Negate(a);
- intresult;
- intsub=3<<29;
- intthrees=1<<29;
-
result=0;
- while(threes>0){
- if(a>=sub){
-
a=Add(a,Negate(sub));
-
result=Add(result,threes);
- }
- sub>>=1;
- threes>>=1;
- }
- if(negative)result=Negate(result);
- returnresult;
- }
- publicstaticintNegate(inta){
- returnAdd(~a,1);
- }
- publicstaticintAdd(inta,intb){
- intx=0;
-
x=a^b;
- while((a&b)!=0){
-
b=(a&b)<<1;
-
a=x;
-
x=a^b;
- }
- returnx;
- }
注:本例是C#实现,因为作者更熟悉C#,但本题更倾向于算法,所以语言并不是太重要吧?(当然只是在不使用语言特性的前提下。)
如果你还想了解更多的方法可以点击这里。
分享到:
相关推荐
算法输入:一个算术表达式,由常量、变量、运算符和括号组成(以字符串形式输入)。为简化,规定操作数只能为正整数,操作符为+、-*、/,用#表示结束。 算法输出:表达式运算结果。
C/C++面试之算法系列--几个典型的内存拷贝及字符串函数实现 写一个函数,完成内存之间的拷贝。[考虑问题是否全面,是否考虑内存重叠问题] 返回void *支持链式操作,参数类型是void *以支持任意类型的指针,输入...
具体事例如下: 知识点:堆栈、队列 实际输入输出情况: 正确的表达式 对负数的处理 表达式括号不匹配 表达式出现非法字符 表达式中操作符位置错误 求余操作符左右出现非整数 其他输入错误 数据结构与算法描述 解决...
这个计算机实现了: 1. 基本计算 (e * ** / % + -) * 括号的处理会让代码逻辑变得混乱得多,所以还没实现左右... * 仅支持二元操作符 * 支持小数 2. 优先级 3. 错误回显:可指出出错位置、原因 4. 中间过程显示
本文实例讲述了Python3.4常用操作符,条件分支和循环用法。分享给大家供大家参考,具体如下: #Pyhon常用操作符 c = d = 10 d /= 8 #3.x真正的除法 print(d) #1.25 c //= 8 #用两个斜杠实现2.x默认的地板除法(整数...
本题主要是要求设计一种算法,使用数组来存放n个人,而后从1号人员开始报数(顺时针方向),当数到k时(其中k>1由用户通过cin输入指定),则该号人员被“淘汰出局”;接着仍沿顺时针方向从被淘汰出局者的下一人员又...
(1)建立两个栈,一个S1用来存放操作符+ - * / ( ),另一个S2用来存放生成的逆波兰表达式(本文中为了方便用一个字符串来存放逆波兰表达式),操作符栈遵循越往栈顶操作符优先级越高的原则。 (2)从中缀表达式的...
操作符: \ 转义符 (), (?:), (?=), [] 圆括号和方括号 *, +, ?, {n}, {n,}, {n,m} 限定符 ^, $, \anymetacharacter 位置和顺序 | “或”操作 元字符: \ ^ $ * + ? {n} {n,} {n,m} ? . (pattern) (?:...
设计一个程序,演示用算符优先法对算术表达式求值的过程。 【基本要求】 以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用运算符优先关系,实现对算术四则混合运算表达式的求值。 【测试数据】 ...
在这里用到了两个栈,一个是操作符栈,另一个是操作数栈,分别用来保存操作符和操作数。在读取表达式的时候如果是操作数则进栈。如果是操作符则把栈顶元素取出来和它比较。如果栈顶的优先级小,则入栈。如果等于则去...
每个助记符对应一个特定的二进制操作码。 3. **低级操作**: - **直接硬件控制**:汇编语言允许程序员直接操控硬件资源,如寄存器、内存地址、I/O端口等,这使得它非常适合编写对时间和空间效率要求极高、需要精确...
回文判断,试编写一个算法,判断依次读入的一个以@为结素符的字母序列。自己找到的,希望帮到你们。
此类运用了大量C++的基础语法,无参构造、数值构造,数字字符串构造、拷贝构造、各种操作符重载、友元函数重载、使 string 类型变量可以像 stringstream 类型一样级联式输出,将数据级联式输出到 LagerData 类中。
1) 运算符 + - * / **(指数操作符) 2) 关系 =(相当于JAVA中的==) > < <> != ~= ^= <= >= 3) 赋值 := 例子a:=2 4) 连接 || 例: 'abc' || 123 5) 标号 需要的标记 >> 6) 注释 --(单行) /* */(段落) 7) 替代...
种算法就是算符优先算法,它通过使用两个栈来实现,一个用于暂存操作数,另一个用于暂存操作符。此算法的基本思路是: (1) 初始化操作数栈、操作符栈,并将数字0压入操作数栈,’=’压入操作数栈作为栈底元素。 ...
骆 骥 -《由"汽车问题"浅谈深度搜索的一个方面——搜索对象与策略的重要性》 毛子青 -《动态规划算法的优化技巧》 俞 玮 -《基本动态规划问题的扩展》 张一飞 -《求N!的高精度算法》 ## 2002 戴德承 -《退...
--选择1--选择第一个磁盘; 选择1 access this volume group and start a shell 当出现提示符(如#时)开始操作 # cd /etc # cp passwd.old passwd (就是你刚刚保存的那个文件) # chown root:security passwd # ...
位运算操作符通常包括与(&)、或(|)、异或(^)、取反(~)、左移()和右移(>>)等。 以下是常见的位运算操作: ### 1. 与(&) - 运算规则:两个相应的位都为1时,结果为1;否则结果为0。 - 示例:`1010 & ...
快速排序算法测试,操作符重载,模板应用. 在VS2005下调试通过
C/C++基本类型做算术运算时长度有限,但也...本资源用C++封装了一个高精度整型,完整重载了+-*/%==>>等操作符, 可以直接当整型使用于工程项目,包含了功能测试和性能测试程序,在vs 2019、及ubuntu gcc 均能编译运行。