forked from xiaoningning/java-algorithm-2010
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMathOps.java
More file actions
116 lines (83 loc) · 2.66 KB
/
MathOps.java
File metadata and controls
116 lines (83 loc) · 2.66 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
/*
After test, there is bug for value -2147483648 (the minimus integer);
as for integer -(-2147483648) is still -2147483648, not 2147483648.
So we need a larger type which could contains value 2147483648
typedef long long_int;
if the sizeof(long) is equal to sizeof(int) in some system,
you may need to use long long instead
typedef long long long_int;
*/
public class MathOps {
public static int add(int x, int y) {
if (y == 0) return x;
int a = x ^ y; // add
int b = (x & y) << 1; // carry
return add(a, b);
}
public static double sqrt(double x) {
double y = x;
double e = 1e-15;
while (Math.abs(x / y - y) > e * y) {
y = (x / y + y) / 2.0;
}
return y;
}
public static double pow(double x, int y) {
if (y == 0) return 1;
if (y == 1) return x;
boolean negative = false;
if (y < 0) {
negative = true;
y = -y;
}
double r = pow(x, y / 2);
r = r * r;
if (y % 2 != 0) r = r * x;
if (negative) r = 1 / r;
return r;
}
public static int divide(int dividend, int divisor) {
if (divisor == 0)
throw new ArithmeticException("divisor is 0");
boolean neg_dividend = (dividend < 0);
boolean neg_divisor = (divisor < 0);
if (neg_dividend)
dividend = (dividend ^ -1) + 1;
if (neg_divisor)
divisor = (divisor ^ -1) + 1;
int result = 0;
while (dividend >= divisor) {
dividend -= divisor;
result++;
}
if (neg_dividend ^ neg_divisor)
result = (result ^ -1) + 1;
return result;
}
public static int divide1(int dividend, int divisor) {
assert (divisor != 0);
boolean bNeg = false;
if ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0))
bNeg = true;
long la = dividend;
long ula = la < 0 ? -la : la;
long lb = divisor;
long ulb = lb < 0 ? -lb : lb;
int msb = 0;
while ((ulb << msb) < ula) msb++;
int q = 0;
for (int i = msb; i >= 0; i--) {
if ((ulb << i) > ula) continue;
q |= (1 << i);
ula -= (ulb << i);
}
return bNeg ? -q : q;
}
public static void main(String[] args) {
System.out.println("add: " + add(6, -2));
System.out.println("sqrt: " + sqrt(120.0));
System.out.println("pow: " + pow(2.0, -3));
System.out.println("divide: " + divide(-21474, 3));
System.out.println("divide: " + divide1(-10, 3));
}
}