位操作实现加减乘除

  1 // Bit Operation Implements Add, Submit, Multiply, Divide
  2 // Use only Integer with little length
  3 
  4 #include <iostream>
  5 using namespace std;
  6 
  7 // add
  8 int add( int a, int b ){ 
  9 　　int c;
 10 　　while( c = (a&b) ){
 11 　　　　a = (a^b);
 12 　　　　b = (c<<1);
 13 　　}
 14 　　return (a^b);
 15 }
 16 
 17 // complementary code
 18 int rev( int a ){
 19 　　return add((~a), 1);
 20 }
 21 
 22 // is positive
 23 int ispos( int a ){
 24 　　return (a&0xFFFF) && !(a&0x8000);
 25 }
 26 
 27 // is negative
 28 int isneg( int a ){
 29 　　return a&0x8000;
 30 }
 31 
 32 // is 0
 33 int iszero( int a ){
 34 　　return !(a&0xFFFF);
 35 }
 36 
 37 // if or not have a > b >= 0
 38 int isbig_pos( int a, int b ){
 39 　　int c = 1;
 40     b = (a^b);
 41 　　if( iszero(b) ) return 0;
 42 　　while( b >>= 1 ){
 43 　　　　c <<= 1;
 44 　　}
 45 　　return (c&a);
 46 }
 47 
 48 // if or not have a > b
 49 int isbig( int a, int b ){
 50 　　if( isneg(a) ){
 51 　　　　if( isneg(b) ){
 52 　　　　　　return isbig_pos( rev(b), rev(a) );
 53 　　　　}
 54 　　　　return 0;
 55 　　}
 56 　　if( isneg(b) ) return 1;
 57 　　return isbig_pos(a, b);
 58 }
 59 
 60 // submit
 61 int sub( int a, int b ){ 
 62 　　return add(a, rev(b));
 63 }
 64 
 65 // two positive numbers multiply
 66 int pos_mul( int a, int b ){
 67 　　int c = 0x8000;
 68 　　int re = a;
 69 　　while( (c>>=1) && (!(b&c)) );
 70 　　while( c >>= 1 ){
 71 　　　　re <<= 1;
 72 　　　　if( c&b )
 73 　　　　re = add(re, a);
 74 　　}
 75 　　return re;
 76 }
 77 
 78 // multiply
 79 int mul( int a, int b ){
 80 　　if (iszero(a) || iszero(b)) return 0;
 81 　　if (ispos(a) && ispos(b))
 82 　　　　return pos_mul(a, b);
 83 　　if (isneg(a)) {
 84 　　　　if (isneg(b)) {
 85 　　　　　　return pos_mul(rev(a), rev(b));
 86 　　　　}
 87 　　　　return rev(pos_mul(rev(a), b ));
 88 　　}
 89 　　return rev(pos_mul(a, rev(b)));
 90 }
 91 
 92 // two positive numbers divide
 93 int pos_div(int a, int b) {
 94 　　int re = 0, temp = b;
 95 　　if(isbig_pos(b, a)) return 0;
 96 　　do {
 97 　　　　temp <<= 1;
 98 　　}
 99 　　while (!isbig_pos(temp, a));
100 　　while (isbig_pos(temp, b)) {
101 　　　　re <<= 1;
102 　　　　temp >>= 1;
103 　　　　if (!isbig_pos(temp, a)) {
104 　　　　　　a = sub(a, temp);
105 　　　　　　re = add(re, 1);
106 　　　　}
107 　　}
108 　　return re;
109 }
110 
111 // divide
112 int idiv( int a, int b ){
113 　　if (iszero(b)) {
114 　　　　cout << "error" << endl;
115 　　　　exit(1);
116 　　}
117 　　if (iszero(a)) return 0;
118 　　if (ispos(a)){
119 　　　　if (ispos(b))
120 　　　　　　return pos_div(a, b);
121 　　　　return rev(pos_div(a, rev(b)));
122 　　}
123 　　if (ispos(b))
124 　　　　return rev(pos_div( rev(a), b));
125 　　return pos_div(rev(a), rev(b));
126 }
127 
128 int main () {
129 　　int a, b;
130 　　while (cin >> a >> b) {
131 　　　　if (isbig(a,b)&&(a<=b)) cout << "big error" << endl;
132 　　　　if (add(a,b) != (a+b)) cout << "add error" << endl;
133 　　　　if (sub(a,b) != (a-b)) cout << "sub error" << endl;
134 　　　　if (mul(a,b) != (a*b)) cout << "mul error" << endl;
135 　　　　if (idiv(a,b) != (a/b)) cout << "div error" << endl;
136 　　}
137 　　return 0;
138 }