输出一行,包含两个整数a和b(a和b均为32位整数)和一个运算符,运算符为“+”,“-”,“*”,"\"中的一个。(数据保证不会出现除0的情况)
输出一个整数,为上述表达式计算出的结果。
2 * 4
8
5 / 4
1
3 + 23
26
时间复杂度,额外空间复杂度。
测试错误的数据
输入:363213591 * -850993220
结果:265850340
Python代码如下:
def add(x,y): while(y): temp=x^y y=(x&y)<<1 x=temp return x def negative(x): return add(~x,1) def subtraction(x,y): if(x<y): y=negative(y) return add(x,y) elif(x==y): return 0 else: x=negative(x) return negative(add(x,y)) def multiply(x,y): c=1 if(x^y<0) else 0 x=negative(x) if(x<0) else x y=negative(y) if(y<0) else y temp=0 while(y): if(y&1): temp=add(temp,x) x<<=1 y>>=1 temp=negative(temp) if(c) else temp return temp def division(x,y): if(x==0 and y!=0): return 0 c=1 if(x^y<0) else 0 x=negative(x) if(x<0) else x y=negative(y) if(y<0) else y if(x<y and y!=0): return 0 temp=0 while(x>=y): trial=y t=1 while((trial<<1)<=x and (trial<<1)>0): t<<=1 trial<<=1 temp=add(temp,t) x=subtraction(x,trial) temp=negative(temp) if(c) else temp return temp ls=input().strip().split() x=int(ls[0]) y=int(ls[2]) o=ls[1] if '+' in o: print(add(x,y)) elif '-' in o: print(subtraction(x,y)) elif '*' in o: print(multiply(x,y)) elif '/' in o or '\\' in o: print(division(x,y))
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String expression = br.readLine(); String[] params = expression.split(" "); int x = Integer.parseInt(params[0]), y = Integer.parseInt(params[2]); String operator = params[1]; if(operator.indexOf("+") > -1){ System.out.println(add(x, y)); }else if(operator.indexOf("-") > -1){ System.out.println(subtract(x, y)); }else if(operator.indexOf("*") > -1){ System.out.println(multiply(x, y)); }else{ System.out.println(divide(x, y)); } } private static int add(int sum, int carry) { if(carry == 0) return sum; // 进位为0,直接返回num // 异或为无进位和, return add(sum ^ carry, (sum & carry) << 1); } private static int subtract(int x, int y) { return add(x, add(~y, 1)); } private static int multiply(int x, int y) { int res = 0; while(y != 0){ if((y & 1) != 0) res = add(res, x); // 看y的最后一位是否为1 x <<= 1; y >>>= 1; // y右移 } return res; } private static int divide(int a, int b) { // 先把两个数转成正数 int x = a < 0? add(~a, 1): a; int y = b < 0? add(~b, 1): b; int res = 0; for(int i = 31; i >= 0; i--){ if((x >> i) >= y) { res |= (1 << i); // 将res从右往左的第i位标记为1 x = subtract(x, y << i); // x减去y向左移i位的结果 } } // 同号直接返回结果,异号返回相反数 return ((a <= 0 && b <= 0) || (a >= 0 && b >= 0))? res: add(~res, 1); } }
#include <iostream> using namespace std; int Add(int num1, int num2) { if (num1 == 0) return num2; if (num2 == 0) return num1; while (num2) { int a = num1 ^ num2; num2 = (num1 & num2) << 1; num1 = a; } return num1; } int Sub(int num1, int num2) { return Add(num1, Add(~num2, 1)); } int Mul(int num1, int num2) { int res = 0; while (num2 != 0) { if ((num2 & 1) != 0) { res = Add(res, num1); } num2 >>= 1; num1 <<= 1; } return res; } int Div(int num1, int num2) { if (num1 == 0 || num2 == 0) return 0; int count = 0; int flag = 1; if (num1 != abs(num1)) flag = Add(flag, 1); if (num2 != abs(num2)) flag = Add(flag, 1); if (flag == 3 || flag == 1) flag = 1; else flag = -1; num1 = abs(num1); num2 = abs(num2); while (num1 >= num2) { num1 = Sub(num1, num2); count = Add(count, 1); } if (flag == -1) count = Add(~count, 1); return count; } int main() { string s; while (getline(cin, s)) { string a, b; int i = 0; while (i < s.size() && s[i] != ' ') a += s[i++]; while (i < s.size() && s[i] == ' ') i++; char flag = s[i++]; while (i < s.size() && s[i] == ' ') i++; while (i < s.size() && s[i] != ' ') b += s[i++]; int num1 = atoi(a.c_str()); int num2 = atoi(b.c_str()); switch (flag) { case '+': cout << Add(num1, num2) << endl; break; case '-': cout << Sub(num1, num2) << endl; break; case '*': cout << Mul(num1, num2) << endl; break; case '/': cout << Div(num1, num2) << endl; break; case '\\': cout << Div(num1, num2) << endl; break; default: break; } } return 0; }
#include <iostream> #include <string> using namespace std; // 定义一个加法函数 int add(int num1,int num2){ while(num1 != 0){ int tmp = num2; num2 = num2^num1; num1 = (tmp&num1)<<1; } return num2; } // 定义一个减法函数 int sub(int num1,int num2){ int tmp = num2; tmp = add(~num2,1); return add(num1,tmp); } // 定义一个乘法函数 int mult(int num1,int num2){ int res = 0; while(num2 != 0){ if((num2 & 1) != 0){ res = add(res,num1); } num2 >>= 1; num1 <<= 1; } return res; } int main(){ int num1,num2; string str; cin>>num1>>str>>num2; bool flag1 = false; bool flag2 = false; if(num1 < 0){ flag1 = true; } if(num2 < 0){ flag2 = true; } // 定义一个函数为加法函数 add if(str == "+"){ cout<<add(num1,num2)<<endl; } else if(str == "-"){ cout<<sub(num1,num2)<<endl; }else if(str == "*"){ cout<<mult(num1, num2)<<endl; }else if(str == "\\"){ int ans = 0; num1 = abs(num1); num2 = abs(num2); while(num1 >= num2){ num1 = sub(num1,num2); ans = add(ans,1); } if((flag1 && !flag2) || (!flag1 && flag2)){ cout<<add(~ans,1)<<endl; }else{ cout<<ans<<endl; } } return 0; }
内联汇编,g++通过测试
不知道为什么,clang++不能通过,除法计算的结果不对!也看不到编译的的结果,无法调试...
#include <iostream> #include <functional> #include <unordered_map> int add(long a, long b){ asm( "leaq (%rdi,%rsi), %rax\n" ); } int minus_(long a, long b){ asm( "sub %rsi, %rdi\n" "mov %rdi, %rax\n" ); } int multiply(long a, long b){ asm( "mov %rdi, %rax\n" "imul %rsi, %rax\n" ); } int divide(long a, long b){ asm( "mov %rdi, %rax\n" "cqto\n" "idivq %rsi, %rax\n" ); } static std::unordered_map<char, std::function<int(int, int)>> op_map{ {'+', add}, {'-', minus_}, {'*', multiply}, {'\\', divide}}; int main() { using namespace std; int lh, rh; char op; while (cin >> lh >> op >> rh) { cout << (op_map[op])(lh, rh) << endl; } return 0; }
import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); String operator = scanner.next(); int m = scanner.nextInt(); int res = 0; switch(operator){ case "+": res = add(n,m); break; case "-": res = minus(n,m); break; case "*": res = multi(n,m); break; case "/": res = div(n,m); break; } System.out.print(res); } public static int add(int a,int b){ int carry = (a&b) << 1; int noCarrySum = a ^ b; int sum = noCarrySum; while(carry != 0){ sum = noCarrySum ^ carry; carry = (noCarrySum & carry) << 1; noCarrySum = sum; } return sum; } public static int minus(int a,int b){ return add(a,add(~b,1)); } public static int multi(int a,int b){ int res = 0; while(b!=0){ if((b & 1) != 0){ res = add(res,a); } b >>= 1; a <<= 1; } return res; } public static int div(int a,int b){ return (a/b); } }