d******u
发帖数: 397 | 1 这道题也挺经典的，做乘法比较简单
假设输入是正整数，如果不是要处理一下
int multiply(int a, int b){
if(a==0 ||b==0) return 0;
if(a==1) return b;
if(b==1) return a;
int r =0;
while(b>0){
if(b%2==1) r+=a;
a<<=1;
b>>=1;
}
return r;
}
问题除法的话怎么做呢？另外，怎么在parallel的环境下scale呢？
请指教，谢谢！ |
p*****2
发帖数: 21240 | 2
是不是需要处理一下负数？
【在 d******u 的大作中提到】
: 这道题也挺经典的，做乘法比较简单
: 假设输入是正整数，如果不是要处理一下
: int multiply(int a, int b){
: if(a==0 ||b==0) return 0;
: if(a==1) return b;
: if(b==1) return a;
: int r =0;
: while(b>0){
: if(b%2==1) r+=a;
: a<<=1;
|
S******t
发帖数: 151 | 3 会做乘法就肯定可以做除法啊……
你这个乘法做的方法就是展开成二进制然后逐次加然后移位，语法有点小问题
除法你直接用乘法去二分找结果就可以了
【在 d******u 的大作中提到】
: 这道题也挺经典的，做乘法比较简单
: 假设输入是正整数，如果不是要处理一下
: int multiply(int a, int b){
: if(a==0 ||b==0) return 0;
: if(a==1) return b;
: if(b==1) return a;
: int r =0;
: while(b>0){
: if(b%2==1) r+=a;
: a<<=1;
|
p*****2
发帖数: 21240 | 4 int divide(int a, int b) // return c=a/b;
{
if (b == 0)
throw new ArithmeticException();
boolean neg = false;
if (a < 0)
neg = !neg;
if (b < 0)
neg = !neg;
a = Math.abs(a);
b = Math.abs(b);
int d = 0;
while (b << d <= a)
{
d++;
}
int c = 0;
for (int i = d; i >= 0; i--)
{
if (b << i <= a)
{
c |= 1 << i;
a -= b << i;
}
}
if (neg)
c = -c;
return c;
} |
d******u
发帖数: 397 | 5 请问在parallel环境下怎么scale呢？
楼上程序运行了一下，结果时对的。。。。谢谢！ |
d******u
发帖数: 397 | 6 多谢，语法纠正了。。。
【在 S******t 的大作中提到】
: 会做乘法就肯定可以做除法啊……
: 你这个乘法做的方法就是展开成二进制然后逐次加然后移位，语法有点小问题
: 除法你直接用乘法去二分找结果就可以了
|
p*****2
发帖数: 21240 | 7 刚才上leetcode上run了一下，timeout呀。1337过来说一下吧。我search半天没知道他
的点评。 |
i**********e
发帖数: 1145 | 8 while (b << d <= a)
应该是这里死循环了。
当 a 很大的时候，bit左移就会产生溢出，而成为负数。一直死循环下去。
【在 p*****2 的大作中提到】
: 刚才上leetcode上run了一下，timeout呀。1337过来说一下吧。我search半天没知道他
: 的点评。
|
i**********e
发帖数: 1145 | |
p*****2
发帖数: 21240 | 10
多谢。pass了。
【在 i**********e 的大作中提到】
: while (b << d <= a)
: 应该是这里死循环了。
: 当 a 很大的时候，bit左移就会产生溢出，而成为负数。一直死循环下去。
|
t********6
发帖数: 348 | 11 while ( b << digit <= a ）
-》
while ( (a >> digit) > b)
right?
【在 p*****2 的大作中提到】
:
: 多谢。pass了。
|
c*********t
发帖数: 2921 | 12 北京二爷，你是怎么改的，能不能把你的代码更新一下。
【在 p*****2 的大作中提到】
:
: 多谢。pass了。
|
p*****2
发帖数: 21240 | 13
就是改成long了。
public int divide(int dividend, int divisor) // return c=a/b;
{
long a = dividend;
long b = divisor;
if (b == 0)
throw new ArithmeticException();
boolean neg = false;
if (a < 0)
neg = !neg;
if (b < 0)
neg = !neg;
a = Math.abs(a);
b = Math.abs(b);
int d = 0;
while (b << d <= a)
{
d++;
}
int c = 0;
for (int i = d; i >= 0; i--)
{
if (b << i <= a)
{
c |= 1 << i;
a -= b << i;
}
}
if (neg)
c = -c;
return c;
}
【在 c*********t 的大作中提到】
: 北京二爷，你是怎么改的，能不能把你的代码更新一下。
|
