[算法]不使用*、/、+、-、%操作符求一个数的1/3

摘要：算法一直是程序员进阶的一道龙门，通常算法都是为了更高效地解决问题而创造的，但也有的只是出于学术性，并不在意其实际意义。这是近日在国外技术问答网站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);//div()是标准C语言函数
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);
}

第六种方法：

//注意:itoa不是个标准函数，但它可以实现
//don'tseemtohandlenegativewhenbase!=10
intdiv3(inti){
charstr[42];
sprintf(str,"%d",INT_MIN);//putminussignatstr[0]
if(i>0)str[0]='';//removesignifpositive
itoa(abs(i),&str[1],3);//putternaryabsolutevaluestartingatstr[1]
str[strlen(&str[1])]='\0';//droplastdigit
returnstrtol(str,NULL,3);//readbackresult
}

第七种方法：

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;//溢出（注意：这里的x和mask都是0）
}

这个版本更快一些：

unsignedadd(charconstzero[],unsignedconstx,unsignedconsty){
//这是因为：如果foo是char*类型，&foo[bar]==foo+bar
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#，但本题更倾向于算法，所以语言并不是太重要吧？（当然只是在不使用语言特性的前提下。）

如果你还想了解更多的方法可以点击这里。