d****o
发帖数: 1055 | 1 这道题除了-n次以外，还有更好的办法吗？
Divide two integers without using multiplication, division and mod operator. |
g*********e
发帖数: 14401 | 2 suppose
10101 divided by 11
11>110>1100 4
(10101-1100)=1001
11>110 2
(1001-110)=11
11 1
(11-11)=0
so result is 4+2+1=7 |
d****o
发帖数: 1055 | 3 不错~~
【在 g*********e 的大作中提到】
: suppose
: 10101 divided by 11
: 11>110>1100 4
: (10101-1100)=1001
: 11>110 2
: (1001-110)=11
: 11 1
: (11-11)=0
: so result is 4+2+1=7
|
p*****2
发帖数: 21240 | 4 常规题得多练呀。
public int divide(int dividend, int divisor)
{
if (divisor == 0)
throw new ArithmeticException();
long a = dividend;
long b = divisor;
boolean neg = false;
if (a < 0)
neg = !neg;
if (b < 0)
neg = !neg;
a=Math.abs(a);
b=Math.abs(b);
int c = 0;
while (b << c <= a)
c++;
int ans = 0;
while (c >= 0)
{
if (b << c <= a)
{
a -= b << c;
ans |= 1 << c;
}
c--;
}
return neg ? -ans : ans;
} |
l*********8
发帖数: 4642 | 5 我也练习一个：
// caculate a/b
int devide(int a, int b)
{
if (b==0) throw std::overflow_error("Divide by zero exception");
if (a<0) return -devide(-a,b);
if (b<0) return -devide(a,-b);
if (a
int d = 1;
while(b>0 && b<=a) {
b <<= 1;
d <<= 1;
}
b = unsigned int(b) >> 1;
d = unsigned int(d) >> 1;
int ans = 0;
while(b) {
ans += d;
a -= b;
while(b>a) {
b >>= 1;
d >>= 1;
}
}
return ans;
} |
p*****2
发帖数: 21240 | 6
你这个会不会overflow?
while(b>0 && b<=a) {
b <<= 1;
d <<= 1;
}
【在 l*********8 的大作中提到】
: 我也练习一个：
: // caculate a/b
: int devide(int a, int b)
: {
: if (b==0) throw std::overflow_error("Divide by zero exception");
: if (a<0) return -devide(-a,b);
: if (b<0) return -devide(a,-b);
: if (a: int d = 1;
: while(b>0 && b<=a) {
|
l*********8
发帖数: 4642 | 7 peking2, 你的程序通过leetcode了吗？
【在 p*****2 的大作中提到】
: 常规题得多练呀。
: public int divide(int dividend, int divisor)
: {
: if (divisor == 0)
: throw new ArithmeticException();
: long a = dividend;
: long b = divisor;
:
: boolean neg = false;
: if (a < 0)
|
l*********8
发帖数: 4642 | 8 我就是用b>0来防止overflow的
不过我的程序还没有通过leetcode.
【在 p*****2 的大作中提到】
:
: 你这个会不会overflow?
: while(b>0 && b<=a) {
: b <<= 1;
: d <<= 1;
: }
|
y**********u
发帖数: 6366 | 9 应该到a < (b<<1)就停了
【在 p*****2 的大作中提到】
:
: 你这个会不会overflow?
: while(b>0 && b<=a) {
: b <<= 1;
: d <<= 1;
: }
|
p*****2
发帖数: 21240 | 10
通过了呀。
【在 l*********8 的大作中提到】
: peking2, 你的程序通过leetcode了吗？
|
|
|
p*****2
发帖数: 21240 | 11
那最后的b不一定大于a呀。
【在 l*********8 的大作中提到】
: 我就是用b>0来防止overflow的
: 不过我的程序还没有通过leetcode.
|
y**********u
发帖数: 6366 | 12 因为leetcode有-(1<<31)这样的test case...
【在 l*********8 的大作中提到】
: 我就是用b>0来防止overflow的
: 不过我的程序还没有通过leetcode.
|
l*********8
发帖数: 4642 | 13 哦，可能java里面的long和int是不一样的。
很多c++编译器默认int就是long， 所以你的程序直接翻译成c++的话，可能会溢出。
【在 p*****2 的大作中提到】
:
: 那最后的b不一定大于a呀。
|
l*********8
发帖数: 4642 | 14 谢谢提醒， 是这个问题。
【在 y**********u 的大作中提到】
: 因为leetcode有-(1<<31)这样的test case...
|
p*****2
发帖数: 21240 | 15
javain里边是64位
【在 l*********8 的大作中提到】
: 哦，可能java里面的long和int是不一样的。
: 很多c++编译器默认int就是long， 所以你的程序直接翻译成c++的话，可能会溢出。
|
l*********8
发帖数: 4642 | 16 How to divide two Long integers then?
【在 p*****2 的大作中提到】
:
: javain里边是64位
|
p*****2
发帖数: 21240 | 17
BigInteger.
【在 l*********8 的大作中提到】
: How to divide two Long integers then?
|
y**********u
发帖数: 6366 | 18 c++里头有unsigned 类型的，没那么费劲。。。
【在 p*****2 的大作中提到】
:
: BigInteger.
|
p*****2
发帖数: 21240 | 19
那不也有unsigned相除的问题吗。
【在 y**********u 的大作中提到】
: c++里头有unsigned 类型的，没那么费劲。。。
|
c****p
发帖数: 6474 | 20 unsigned相除不考虑符号，比较好处理。
【在 p*****2 的大作中提到】
:
: 那不也有unsigned相除的问题吗。
|
|
|
a****l
发帖数: 8211 | 21 good
【在 g*********e 的大作中提到】
: suppose
: 10101 divided by 11
: 11>110>1100 4
: (10101-1100)=1001
: 11>110 2
: (1001-110)=11
: 11 1
: (11-11)=0
: so result is 4+2+1=7
|
d****o
发帖数: 1055 | 22 这道题除了-n次以外，还有更好的办法吗？
Divide two integers without using multiplication, division and mod operator. |
g*********e
发帖数: 14401 | 23 suppose
10101 divided by 11
11>110>1100 4
(10101-1100)=1001
11>110 2
(1001-110)=11
11 1
(11-11)=0
so result is 4+2+1=7 |
d****o
发帖数: 1055 | 24 不错~~
【在 g*********e 的大作中提到】
: suppose
: 10101 divided by 11
: 11>110>1100 4
: (10101-1100)=1001
: 11>110 2
: (1001-110)=11
: 11 1
: (11-11)=0
: so result is 4+2+1=7
|
p*****2
发帖数: 21240 | 25 常规题得多练呀。
public int divide(int dividend, int divisor)
{
if (divisor == 0)
throw new ArithmeticException();
long a = dividend;
long b = divisor;
boolean neg = false;
if (a < 0)
neg = !neg;
if (b < 0)
neg = !neg;
a=Math.abs(a);
b=Math.abs(b);
int c = 0;
while (b << c <= a)
c++;
int ans = 0;
while (c >= 0)
{
if (b << c <= a)
{
a -= b << c;
ans |= 1 << c;
}
c--;
}
return neg ? -ans : ans;
} |
l*********8
发帖数: 4642 | 26 我也练习一个：
// caculate a/b
int devide(int a, int b)
{
if (b==0) throw std::overflow_error("Divide by zero exception");
if (a<0) return -devide(-a,b);
if (b<0) return -devide(a,-b);
if (a
int d = 1;
while(b>0 && b<=a) {
b <<= 1;
d <<= 1;
}
b = unsigned int(b) >> 1;
d = unsigned int(d) >> 1;
int ans = 0;
while(b) {
ans += d;
a -= b;
while(b>a) {
b >>= 1;
d >>= 1;
}
}
return ans;
} |
p*****2
发帖数: 21240 | 27
你这个会不会overflow?
while(b>0 && b<=a) {
b <<= 1;
d <<= 1;
}
【在 l*********8 的大作中提到】
: 我也练习一个：
: // caculate a/b
: int devide(int a, int b)
: {
: if (b==0) throw std::overflow_error("Divide by zero exception");
: if (a<0) return -devide(-a,b);
: if (b<0) return -devide(a,-b);
: if (a: int d = 1;
: while(b>0 && b<=a) {
|
l*********8
发帖数: 4642 | 28 peking2, 你的程序通过leetcode了吗？
【在 p*****2 的大作中提到】
: 常规题得多练呀。
: public int divide(int dividend, int divisor)
: {
: if (divisor == 0)
: throw new ArithmeticException();
: long a = dividend;
: long b = divisor;
:
: boolean neg = false;
: if (a < 0)
|
l*********8
发帖数: 4642 | 29 我就是用b>0来防止overflow的
不过我的程序还没有通过leetcode.
【在 p*****2 的大作中提到】
:
: 你这个会不会overflow?
: while(b>0 && b<=a) {
: b <<= 1;
: d <<= 1;
: }
|
y**********u
发帖数: 6366 | 30 应该到a < (b<<1)就停了
【在 p*****2 的大作中提到】
:
: 你这个会不会overflow?
: while(b>0 && b<=a) {
: b <<= 1;
: d <<= 1;
: }
|
|
|
p*****2
发帖数: 21240 | 31
通过了呀。
【在 l*********8 的大作中提到】
: peking2, 你的程序通过leetcode了吗？
|
p*****2
发帖数: 21240 | 32
那最后的b不一定大于a呀。
【在 l*********8 的大作中提到】
: 我就是用b>0来防止overflow的
: 不过我的程序还没有通过leetcode.
|
y**********u
发帖数: 6366 | 33 因为leetcode有-(1<<31)这样的test case...
【在 l*********8 的大作中提到】
: 我就是用b>0来防止overflow的
: 不过我的程序还没有通过leetcode.
|
l*********8
发帖数: 4642 | 34 哦，可能java里面的long和int是不一样的。
很多c++编译器默认int就是long， 所以你的程序直接翻译成c++的话，可能会溢出。
【在 p*****2 的大作中提到】
:
: 那最后的b不一定大于a呀。
|
l*********8
发帖数: 4642 | 35 谢谢提醒， 是这个问题。
【在 y**********u 的大作中提到】
: 因为leetcode有-(1<<31)这样的test case...
|
p*****2
发帖数: 21240 | 36
javain里边是64位
【在 l*********8 的大作中提到】
: 哦，可能java里面的long和int是不一样的。
: 很多c++编译器默认int就是long， 所以你的程序直接翻译成c++的话，可能会溢出。
|
l*********8
发帖数: 4642 | 37 How to divide two Long integers then?
【在 p*****2 的大作中提到】
:
: javain里边是64位
|
p*****2
发帖数: 21240 | 38
BigInteger.
【在 l*********8 的大作中提到】
: How to divide two Long integers then?
|
y**********u
发帖数: 6366 | 39 c++里头有unsigned 类型的，没那么费劲。。。
【在 p*****2 的大作中提到】
:
: BigInteger.
|
p*****2
发帖数: 21240 | 40
那不也有unsigned相除的问题吗。
【在 y**********u 的大作中提到】
: c++里头有unsigned 类型的，没那么费劲。。。
|
|
|
c****p
发帖数: 6474 | 41 unsigned相除不考虑符号，比较好处理。
【在 p*****2 的大作中提到】
:
: 那不也有unsigned相除的问题吗。
|
a****l
发帖数: 8211 | 42 good
【在 g*********e 的大作中提到】
: suppose
: 10101 divided by 11
: 11>110>1100 4
: (10101-1100)=1001
: 11>110 2
: (1001-110)=11
: 11 1
: (11-11)=0
: so result is 4+2+1=7
|
c********t
发帖数: 5706 | 43 为什么一上来要转成long?
我没转，思路一样，但是过不了OJ, exceed time limit
求教
【在 p*****2 的大作中提到】
: 常规题得多练呀。
: public int divide(int dividend, int divisor)
: {
: if (divisor == 0)
: throw new ArithmeticException();
: long a = dividend;
: long b = divisor;
:
: boolean neg = false;
: if (a < 0)
|
Q*******e
发帖数: 939 | 44 上个咱的, 若干天写的
int
my_div1(int a, int b) {
int divident = a;
int divsor = b;
int negative = 0;
int result = 0;
if (divsor == 0) {
printf("Error, divee is 0\n");
abort();
}
if (divident == 0) {
return 0;
}
if (divident < 0) {
negative = 1;
divident = -divident;
}
if (divsor < 0) {
negative = !negative;
divsor = -divsor;
}
while (divident >= divsor) {
divident -= divsor;
result++;
}
if (negative) {
result = -result;
}
return result;
} |
c*****a
发帖数: 808 | 45 a/b = exp( log(a) - log(b) ) |
c********t
发帖数: 5706 | 46 这个过不了OJ吧？
【在 Q*******e 的大作中提到】
: 上个咱的, 若干天写的
: int
: my_div1(int a, int b) {
: int divident = a;
: int divsor = b;
: int negative = 0;
: int result = 0;
: if (divsor == 0) {
: printf("Error, divee is 0\n");
: abort();
|
c********t
发帖数: 5706 | 47 呵呵，有点意思。
5/2是多少？也许用2^(lg(a)- lg(b))可以？
【在 c*****a 的大作中提到】
: a/b = exp( log(a) - log(b) )
|
P******r
发帖数: 842 | 48 这题能用log exp做吗？能用的话code太短了。另外偷懒了，除0就返回0了。
int divide(int dividend, int divisor) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
long long x = dividend;
long long y = divisor;
if (0 == x || 0 == y)
return 0;
int sign = (x > 0 && y > 0 || x < 0 && y < 0) ? 1 : -1;
x = abs(x);
y = abs(y);
int r = exp(log(x)-log(y));
return sign*r;
} |
l**b
发帖数: 457 | 49 public int divide(int dividend, int divisor) {
assert(divisor != 0);
if (dividend == 0) {
return 0;
}
boolean negative = false;
if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
negative = true;
}
int result = 0;
long lDividend = Math.abs((long) dividend);
long lDivisor = Math.abs((long) divisor);
while (lDividend >= lDivisor) {
long d = lDivisor;
int temp = 1;
while (lDividend >= d << 1) {
d = d << 1;
temp = temp << 1;
}
lDividend -= d;
result += temp;
}
if (negative) return -result;
else return result;
}
跟大潮练，结果忘记写Math。abs了。。。 |
l**b
发帖数: 457 | 50 ColdKnight，你去看看Math.abs(Integer.MIN_VALUE)输出的是什么你就知道为什么TLE了
【在 c********t 的大作中提到】
: 为什么一上来要转成long?
: 我没转，思路一样，但是过不了OJ, exceed time limit
: 求教
|
|
|
c**s
发帖数: 159 | 51 a = -2147483648 不会溢出么？
【在 l*********8 的大作中提到】
: 我也练习一个：
: // caculate a/b
: int devide(int a, int b)
: {
: if (b==0) throw std::overflow_error("Divide by zero exception");
: if (a<0) return -devide(-a,b);
: if (b<0) return -devide(a,-b);
: if (a: int d = 1;
: while(b>0 && b<=a) {
|
