关于除法的问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

关于除法的问题

关于除法的问题# JobHunting - 待字闺中

h*i2012-02-21 08:02

1 楼

除2个整数不能用乘除.那位给个O(lgn)的解法阿？我只知道O(n)的

r*n2012-02-21 08:02

2 楼

如果是m/n
那start from x=m
step = m/2
loop:
if x * n > m
x = x - step/2
else:
x = x + step/2
step /= 2
基本就是个对分查找

【在 h******i 的大作中提到】

: 除2个整数不能用乘除.那位给个O(lgn)的解法阿？我只知道O(n)的

h*i2012-02-21 08:02

3 楼

这个我也想到了不过题目要求不能用乘法。 x*n>m不合要求阿。

r*n2012-02-21 08:02

4 楼

可以位移和加法啊.....
不还是binary search咩

【在 h******i 的大作中提到】

: 这个我也想到了不过题目要求不能用乘法。 x*n>m不合要求阿。

c*p2012-02-21 08:02

5 楼

对于x/y，
先找到k，使2^k<=x<2^(k+1)，
x -= 2^k
然后依次比较x和2^(k-1)...2^0至x为零为止。
结果的每一位，如果够减就是1，不够减就是0【在 happylii (小马哥) 的大作中提到

h*i2012-02-21 08:02

6 楼

照着写了个code 不过放在leetcode上测试连small set都超时了。那位给贴个效率高的
，让我学习一下。
int Multiply(int x, int y)
{
bool neg = (x>0&&y<0)||(x<0&&y>0);
y = abs(y);
int res = 0;
int orgy = y;
while(y>1)
{
res += x << 1;
y-=2;
}
if(y==1)
res+=x;
if(neg&&orgy<0)
return -res;
else
return res;
}
int divide(int dividend, int divisor) {
int res = dividend;
int step = dividend;
while(1)
{
int product = Multiply(res,divisor);
if(step>1)
step=step>>1;
if(product>dividend)
{
res-=step;
}
else if((product+divisor)res+=step;
else
break;
}
return res;
}

p*22012-02-21 08:02

7 楼

int divide(int dividend, int divisor) {
if (divisor == 0)
throw new ArithmeticException();
int k = 0;
long a = dividend;
long b = divisor;
a = Math.abs(a);
b = Math.abs(b);
boolean neg = (dividend & 1 << 31 ^ divisor & 1 << 31) != 0;
while (b << k <= a)
k++;
int r = 0;
for (int i = k; i >= 0; i--) {
if (b << i > a)
continue;
else {
r |= 1 << i;
a -= b << i;
}
}
return neg ? -r : r;
}

h*i2012-02-21 08:02

8 楼

刚才在oj上试了下，还是超时了。。。。

【在 p*****2 的大作中提到】

: int divide(int dividend, int divisor) {
: if (divisor == 0)
: throw new ArithmeticException();
: int k = 0;
: long a = dividend;
: long b = divisor;
: a = Math.abs(a);
: b = Math.abs(b);
: boolean neg = (dividend & 1 << 31 ^ divisor & 1 << 31) != 0;
: while (b << k <= a)

p*22012-02-21 08:02

9 楼

我在leetcode上试了。可以。

【在 h******i 的大作中提到】

: 刚才在oj上试了下，还是超时了。。。。

t*t2012-02-21 08:02

10 楼

你这乘法是线性的, 能不超时吗.

【在 h******i 的大作中提到】

: 照着写了个code 不过放在leetcode上测试连small set都超时了。那位给贴个效率高的
: ，让我学习一下。
: int Multiply(int x, int y)
: {
: bool neg = (x>0&&y<0)||(x<0&&y>0);
: y = abs(y);
: int res = 0;
: int orgy = y;
: while(y>1)
: {

c*p2012-02-21 08:02

11 楼

http://www.mitbbs.com/mitbbs_article.php?board=JobHunting&id=31

【在 h******i 的大作中提到】

: 刚才在oj上试了下，还是超时了。。。。