Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

C++:
01 int divide(int dividend, int divisor) {
02         assert(divisor!=0);
03         if(dividend==0)
04             return 0;
05         int sign=1;
06         if(dividend<0){
07             dividend=-dividend;
08             sign=-sign;
09         }
10         if(divisor<0){
11             divisor=-divisor;
12             sign=-sign;
13         }
14         unsigned int long u_dividend=dividend;
15         unsigned int long u_divisor=divisor;
16         unsigned int long tmp=u_divisor;
17         unsigned int long pw=1;
18         int result=0;
19         bool flag=false;
20         while(dividend>=tmp){
21             if(tmp<(tmp<<1)){
22                 tmp=tmp<<1;
23                 pw=pw<<1;
24             }
25             else{
26                 flag=true;
27                 break;
28             }
29         }
30         if(flag==false){
31             tmp=tmp>>1;
32             pw=pw>>1;
33         }
34         while(u_dividend>=u_divisor){
35             if(u_dividend>=tmp){
36                 result+=pw;
37                 u_dividend-=tmp;
38             }
39             tmp=tmp>>1;
40             pw=pw>>1;
41         }
42         if(sign>0)
43             return result;
44         else
45             return result;
46 }
Advertisements
This entry was posted in Bit operation, Number trick. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s