w****x
发帖数: 2483 | 1 最优的算法实现除法, 不能用* or /
google上查德答案是用bit除, 大概逻辑是(有bug):
int divide(int a, int b) {
int msb = 0;
while ((b << msb) <= a)
msb++;
int q = 0;
for (int i = msb; i >= 0; i--) { //msb is the first bit make (b << mst)
> a.
if ((b << i) > a) {
continue;
}
q |= (1 << i);
a -= (b << i);
}
return q;
}
我觉得这种题丢电面里是不是太扯了 |
a*******r
发帖数: 122 | 2 Read 'Structure and Interpretation of Comupter Programs" |
z****c
发帖数: 602 | 3 其实不难啊。基本思想就是把除数向左移位(×2)然后与被除数比较，直到发现仅次于
被除数的那个值，减去该值后继续。可以用递归做。 |
w****x
发帖数: 2483 | 4 话是这么说没错, 但是15分钟内做出来我看100个人里也不一定有一个吧, 要不就是我
太差了 |
w****x
发帖数: 2483 | 5 要考虑的有正负,溢出(INT_MIN)的版本:
int divide(int a, int b) {
assert(b != 0);
bool bNeg = false;
if ((a < 0 && b > 0) || (a > 0 && b < 0))
bNeg = true;
unsigned int ua = a < 0 ? -a : a;
unsigned int ub = b < 0 ? -b : b;
int msb = 0;
while ((ub << msb) < ua) msb++;
int q = 0;
for (int i = msb; i >= 0; i--) {
if ((ub << i) > ua) {
continue;
}
q |= (1 << i);
ua -= (ub << i);
}
return bNeg ? -q : q;
} |
z****c
发帖数: 602 | |
H***e
发帖数: 476 | 7 现在面试就是水涨船高
【在 z****c 的大作中提到】
: Under pressure确实不容易写出来。
|
g*********e
发帖数: 14401 | 8
mst)
平时想个半小时一个钟头 应该可以弄出来， 现场基本写不出，直接慌了
【在 w****x 的大作中提到】
: 最优的算法实现除法, 不能用* or /
: google上查德答案是用bit除, 大概逻辑是(有bug):
: int divide(int a, int b) {
: int msb = 0;
: while ((b << msb) <= a)
: msb++;
: int q = 0;
: for (int i = msb; i >= 0; i--) { //msb is the first bit make (b << mst)
: > a.
: if ((b << i) > a) {
|
p*****2
发帖数: 21240 | |
p*****2
发帖数: 21240 | |
|
|
y*****n
发帖数: 243 | |
y*****n
发帖数: 243 | 12 一定要写出最优算法么= =可不可以。每次用b = b+b 并存到一个数组c里。 C[1] = b
C[2] = 2b c[3] =4b 然后到c[n]的时候c[n]>a这时再backtracking一路加回去. 如果C
[n-1]+C[n-2]>a那么就跳过去找c[n-3]这样最后就找到C[n0]+c[n1]+C[n2]...C[nm]= a
。那么结果就是2^n0+2^n1....2^nm
方法是一样的，我觉得这样比较好想一点。 |
i**********e
发帖数: 1145 | 13 没有考虑 overflow，思路跟楼上的一样。
我首先想到的是 binary search 的思路，这个用 bit 的思路还是没那么直接和容易想
到。
typedef unsigned int uint;
uint divide(uint a, uint b) {
uint x = 0, ret = 0;
int numBits = sizeof(uint) * 8;
for (int i = numBits - 1; i >= 0; i--) {
x |= ((a >> i) & 1);
if (x >= b) {
ret |= 1;
x -= b;
}
if (i > 0)
ret <<= 1;
x <<= 1;
}
return ret;
}
int divide(int a, int b) {
assert(b != 0);
int sign = 1;
if ((a > 0 && b < 0) ||
(a < 0 && b > 0)) {
sign = -1;
}
uint x = abs(a);
uint y = abs(b);
uint ret = divide(x, y);
return (int)ret * sign;
} |
w****x
发帖数: 2483 | 14
谢谢, 这个办法真好, 算是正常解发
【在 i**********e 的大作中提到】
: 没有考虑 overflow，思路跟楼上的一样。
: 我首先想到的是 binary search 的思路，这个用 bit 的思路还是没那么直接和容易想
: 到。
: typedef unsigned int uint;
: uint divide(uint a, uint b) {
: uint x = 0, ret = 0;
: int numBits = sizeof(uint) * 8;
: for (int i = numBits - 1; i >= 0; i--) {
: x |= ((a >> i) & 1);
: if (x >= b) {
|
a**********t
发帖数: 20 | 15 which part?
【在 a*******r 的大作中提到】
: Read 'Structure and Interpretation of Comupter Programs"
|
j****b
发帖数: 108 | 16 练习了一下
public static void main(String[] args) {
int a = -34434;
int b = -1234;
boolean sign = false;
if (a < 0) {
a = -a;
sign = sign ? false : true;
}
if (b < 0) {
b = -b;
sign = sign ? false : true;
}
if(b == 0){
System.out.println("cannot divide 0");
return;
}
int c = 0;
for(int i=0; i<32; i++){
int aa = a >> (31-i);
c = c << 1;
if(aa >= b){
a -= b << (31-i);
c += 1;
}
}
if(sign)
c = -c;
System.out.println(c);
} |
i**********e
发帖数: 1145 | 17 Just tried running your code here:
http://www.leetcode.com/onlinejudge
it seemed it failed for some test cases when a or b == -2147483648.
This is because if (a < 0) a = -a; cause it to overflow for negative
integers. Since Java doesn't have unsigned int, you may have to use long
long to avoid overflow.
Run Status: Wrong Answer
Progress: 13/17 test cases passed.
input output expected
-2147483648, 1 0 -2147483648
【在 j****b 的大作中提到】
: 练习了一下
: public static void main(String[] args) {
: int a = -34434;
: int b = -1234;
: boolean sign = false;
: if (a < 0) {
: a = -a;
: sign = sign ? false : true;
: }
: if (b < 0) {
|
j****b
发帖数: 108 | 18 Thanks!
Good to know there is an online judge system.
【在 i**********e 的大作中提到】
: Just tried running your code here:
: http://www.leetcode.com/onlinejudge
: it seemed it failed for some test cases when a or b == -2147483648.
: This is because if (a < 0) a = -a; cause it to overflow for negative
: integers. Since Java doesn't have unsigned int, you may have to use long
: long to avoid overflow.
: Run Status: Wrong Answer
: Progress: 13/17 test cases passed.
: input output expected
: -2147483648, 1 0 -2147483648
|
w****x
发帖数: 2483 | 19 最优的算法实现除法, 不能用* or /
google上查德答案是用bit除, 大概逻辑是(有bug):
int divide(int a, int b) {
int msb = 0;
while ((b << msb) <= a)
msb++;
int q = 0;
for (int i = msb; i >= 0; i--) { //msb is the first bit make (b << mst)
> a.
if ((b << i) > a) {
continue;
}
q |= (1 << i);
a -= (b << i);
}
return q;
}
我觉得这种题丢电面里是不是太扯了 |
a*******r
发帖数: 122 | 20 Read 'Structure and Interpretation of Comupter Programs" |
|
|
z****c
发帖数: 602 | 21 其实不难啊。基本思想就是把除数向左移位(×2)然后与被除数比较，直到发现仅次于
被除数的那个值，减去该值后继续。可以用递归做。 |
w****x
发帖数: 2483 | 22 话是这么说没错, 但是15分钟内做出来我看100个人里也不一定有一个吧, 要不就是我
太差了 |
w****x
发帖数: 2483 | 23 要考虑的有正负,溢出(INT_MIN)的版本:
int divide(int a, int b) {
assert(b != 0);
bool bNeg = false;
if ((a < 0 && b > 0) || (a > 0 && b < 0))
bNeg = true;
unsigned int ua = a < 0 ? -a : a;
unsigned int ub = b < 0 ? -b : b;
int msb = 0;
while ((ub << msb) < ua) msb++;
int q = 0;
for (int i = msb; i >= 0; i--) {
if ((ub << i) > ua) {
continue;
}
q |= (1 << i);
ua -= (ub << i);
}
return bNeg ? -q : q;
} |
z****c
发帖数: 602 | 24 Under pressure确实不容易写出来。 |
H***e
发帖数: 476 | 25 现在面试就是水涨船高
【在 z****c 的大作中提到】
: Under pressure确实不容易写出来。
|
g*********e
发帖数: 14401 | 26
mst)
平时想个半小时一个钟头 应该可以弄出来， 现场基本写不出，直接慌了
【在 w****x 的大作中提到】
: 最优的算法实现除法, 不能用* or /
: google上查德答案是用bit除, 大概逻辑是(有bug):
: int divide(int a, int b) {
: int msb = 0;
: while ((b << msb) <= a)
: msb++;
: int q = 0;
: for (int i = msb; i >= 0; i--) { //msb is the first bit make (b << mst)
: > a.
: if ((b << i) > a) {
|
p*****2
发帖数: 21240 | 27 没感觉这题容易。mark一下。一会儿好好看看。 |
p*****2
发帖数: 21240 | |
y*****n
发帖数: 243 | |
y*****n
发帖数: 243 | 30 一定要写出最优算法么= =可不可以。每次用b = b+b 并存到一个数组c里。 C[1] = b
C[2] = 2b c[3] =4b 然后到c[n]的时候c[n]>a这时再backtracking一路加回去. 如果C
[n-1]+C[n-2]>a那么就跳过去找c[n-3]这样最后就找到C[n0]+c[n1]+C[n2]...C[nm]= a
。那么结果就是2^n0+2^n1....2^nm
方法是一样的，我觉得这样比较好想一点。 |
|
|
i**********e
发帖数: 1145 | 31 没有考虑 overflow，思路跟楼上的一样。
我首先想到的是 binary search 的思路，这个用 bit 的思路还是没那么直接和容易想
到。
typedef unsigned int uint;
uint divide(uint a, uint b) {
uint x = 0, ret = 0;
int numBits = sizeof(uint) * 8;
for (int i = numBits - 1; i >= 0; i--) {
x |= ((a >> i) & 1);
if (x >= b) {
ret |= 1;
x -= b;
}
if (i > 0)
ret <<= 1;
x <<= 1;
}
return ret;
}
int divide(int a, int b) {
assert(b != 0);
int sign = 1;
if ((a > 0 && b < 0) ||
(a < 0 && b > 0)) {
sign = -1;
}
uint x = abs(a);
uint y = abs(b);
uint ret = divide(x, y);
return (int)ret * sign;
} |
w****x
发帖数: 2483 | 32
谢谢, 这个办法真好, 算是正常解发
【在 i**********e 的大作中提到】
: 没有考虑 overflow，思路跟楼上的一样。
: 我首先想到的是 binary search 的思路，这个用 bit 的思路还是没那么直接和容易想
: 到。
: typedef unsigned int uint;
: uint divide(uint a, uint b) {
: uint x = 0, ret = 0;
: int numBits = sizeof(uint) * 8;
: for (int i = numBits - 1; i >= 0; i--) {
: x |= ((a >> i) & 1);
: if (x >= b) {
|
a**********t
发帖数: 20 | 33 which part?
【在 a*******r 的大作中提到】
: Read 'Structure and Interpretation of Comupter Programs"
|
j****b
发帖数: 108 | 34 练习了一下
public static void main(String[] args) {
int a = -34434;
int b = -1234;
boolean sign = false;
if (a < 0) {
a = -a;
sign = sign ? false : true;
}
if (b < 0) {
b = -b;
sign = sign ? false : true;
}
if(b == 0){
System.out.println("cannot divide 0");
return;
}
int c = 0;
for(int i=0; i<32; i++){
int aa = a >> (31-i);
c = c << 1;
if(aa >= b){
a -= b << (31-i);
c += 1;
}
}
if(sign)
c = -c;
System.out.println(c);
} |
i**********e
发帖数: 1145 | 35 Just tried running your code here:
http://www.leetcode.com/onlinejudge
it seemed it failed for some test cases when a or b == -2147483648.
This is because if (a < 0) a = -a; cause it to overflow for negative
integers. Since Java doesn't have unsigned int, you may have to use long
long to avoid overflow.
Run Status: Wrong Answer
Progress: 13/17 test cases passed.
input output expected
-2147483648, 1 0 -2147483648
【在 j****b 的大作中提到】
: 练习了一下
: public static void main(String[] args) {
: int a = -34434;
: int b = -1234;
: boolean sign = false;
: if (a < 0) {
: a = -a;
: sign = sign ? false : true;
: }
: if (b < 0) {
|
j****b
发帖数: 108 | 36 Thanks!
Good to know there is an online judge system.
【在 i**********e 的大作中提到】
: Just tried running your code here:
: http://www.leetcode.com/onlinejudge
: it seemed it failed for some test cases when a or b == -2147483648.
: This is because if (a < 0) a = -a; cause it to overflow for negative
: integers. Since Java doesn't have unsigned int, you may have to use long
: long to avoid overflow.
: Run Status: Wrong Answer
: Progress: 13/17 test cases passed.
: input output expected
: -2147483648, 1 0 -2147483648
|
h*****g
发帖数: 312 | 37 这个解法没看懂呀，哪位看懂的能不能帮忙讲讲？
最好给个详细点儿的例子？
谢谢！
【在 i**********e 的大作中提到】
: 没有考虑 overflow，思路跟楼上的一样。
: 我首先想到的是 binary search 的思路，这个用 bit 的思路还是没那么直接和容易想
: 到。
: typedef unsigned int uint;
: uint divide(uint a, uint b) {
: uint x = 0, ret = 0;
: int numBits = sizeof(uint) * 8;
: for (int i = numBits - 1; i >= 0; i--) {
: x |= ((a >> i) & 1);
: if (x >= b) {
|
h*****g
发帖数: 312 | 38 继续 求 解释~~~~~
【在 h*****g 的大作中提到】
: 这个解法没看懂呀，哪位看懂的能不能帮忙讲讲？
: 最好给个详细点儿的例子？
: 谢谢！
|
G******e
发帖数: 229 | 39 This is the most natural way of doing division: suppose you want to compute
a/b. First you multiply b by 1, 2, 4,.. until you find the largest k such
that b*(2^k) <= a (This is done by keep shifting b to the left). So your first
step result of the division is 10...0 with k zeros. Now you update a by a-(2
^k) *b and repeat this process again until you find the least significant bit
of a/b. Hope this helps.
【在 h*****g 的大作中提到】
: 继续 求 解释~~~~~
|
t**i
发帖数: 314 | 40 在你的基础上做了一下小修改的java code，通过了leetcode的测试：
public int divide(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;
}
【在 w****x 的大作中提到】
: 要考虑的有正负,溢出(INT_MIN)的版本:
: int divide(int a, int b) {
: assert(b != 0);
: bool bNeg = false;
: if ((a < 0 && b > 0) || (a > 0 && b < 0))
: bNeg = true;
: unsigned int ua = a < 0 ? -a : a;
: unsigned int ub = b < 0 ? -b : b;
: int msb = 0;
: while ((ub << msb) < ua) msb++;
|
|
|
g*********e
发帖数: 14401 | 41 我觉得不扯
而且电面不止15min吧，至少有25min可以用来写code。25min内整出这个不算什么高要
求。当然minor bug可能会有（+ - case） |
r*****z
发帖数: 641 | 42 文科生上来捣个乱
改成log然后做减法不行么？
是不是log运行时间太长了？
mst)
【在 w****x 的大作中提到】
: 最优的算法实现除法, 不能用* or /
: google上查德答案是用bit除, 大概逻辑是(有bug):
: int divide(int a, int b) {
: int msb = 0;
: while ((b << msb) <= a)
: msb++;
: int q = 0;
: for (int i = msb; i >= 0; i--) { //msb is the first bit make (b << mst)
: > a.
: if ((b << i) > a) {
|
