儿子这是流感还是其它病？ - 未名空间MITBBS历史存档

w*x2013-01-06 08:01

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;
}
我觉得这种题丢电面里是不是太扯了

h*s2013-01-06 08:01

2 楼

二岁儿子咳嗽流鼻涕一星期了，是被我这个不合格的妈妈从外面带病毒给传染了，我现
在也在吃药主要是鼻子赛咳嗽的厉害，痰很多还一阵阵地发冷，但没有发烧。儿子这
二天发烧了，精神非常不好，食欲也很差，昨天我们带他去看医生，医生没给药说是让
他自己扛。昨晚儿子又发烧虽然有给他吃泰洛，吃了后烧退了，可是后来烧又上来了，
这样一直反复，昨晚去了ER，带了一些药回来，还是吃完好好完又发烧，准备明天带他
去看我们自己的儿医。可是从现在到明天还有很长时间我们真的很不安啊，有类似生
病的宝妈吗可不可以讲讲这是不是流感还是肺炎脑膜炎甚至其它更严重的病？在线等
多谢。

a*r2013-01-06 08:01

3 楼

Read 'Structure and Interpretation of Comupter Programs"

l*r2013-01-06 08:01

4 楼

多少度？101，102问题不大。多半是流感。
退烧药本来就是暂时缓解，不会吃了就彻底退了。只有等病毒过了，才会退烧。现在能
做的就是每隔几小时查体温，药效过了就接着吃退烧药，等你发现什么时候体温回升的
时间段拉长了，就说明快好了。一般至少要两三天。

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

: 二岁儿子咳嗽流鼻涕一星期了，是被我这个不合格的妈妈从外面带病毒给传染了，我现
: 在也在吃药主要是鼻子赛咳嗽的厉害，痰很多还一阵阵地发冷，但没有发烧。儿子这
: 二天发烧了，精神非常不好，食欲也很差，昨天我们带他去看医生，医生没给药说是让
: 他自己扛。昨晚儿子又发烧虽然有给他吃泰洛，吃了后烧退了，可是后来烧又上来了，
: 这样一直反复，昨晚去了ER，带了一些药回来，还是吃完好好完又发烧，准备明天带他
: 去看我们自己的儿医。可是从现在到明天还有很长时间我们真的很不安啊，有类似生
: 病的宝妈吗可不可以讲讲这是不是流感还是肺炎脑膜炎甚至其它更严重的病？在线等
: 多谢。

z*c2013-01-06 08:01

5 楼

其实不难啊。基本思想就是把除数向左移位(×2)然后与被除数比较，直到发现仅次于
被除数的那个值，减去该值后继续。可以用递归做。

w*t2013-01-06 08:01

6 楼

描述有点混乱，一共发烧几天啦？
退烧药本来就是给了只退个烧，时间一过又回来的
但如果烧了3天还在继续，那就应该去看医生
ER开的什么样？抗生素吗？
如果有抗生素，一般3天起效，3天没起效，去看医生
现在很多人都咳嗽，如果你儿子带喘，或呼吸不均，看医生
医生会帮助你孩子止喘，喘多了不好，喘多了容易哮喘
如果没有，就是咳一咳，没关系，家里注意加湿器就行
如果去看医生，注意2点，1，鼻子里取分泌物，可以检验是否FLU，有专门的药
2，听肺音，查血液氧气含量，是否肺炎
其他的不用操心太多，第一次病？妈妈总是非常紧张，多病几次你就淡定了
以上纯属妈妈经验谈，非医学专业人士，后果自负，嘻嘻

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

: 二岁儿子咳嗽流鼻涕一星期了，是被我这个不合格的妈妈从外面带病毒给传染了，我现
: 在也在吃药主要是鼻子赛咳嗽的厉害，痰很多还一阵阵地发冷，但没有发烧。儿子这
: 二天发烧了，精神非常不好，食欲也很差，昨天我们带他去看医生，医生没给药说是让
: 他自己扛。昨晚儿子又发烧虽然有给他吃泰洛，吃了后烧退了，可是后来烧又上来了，
: 这样一直反复，昨晚去了ER，带了一些药回来，还是吃完好好完又发烧，准备明天带他
: 去看我们自己的儿医。可是从现在到明天还有很长时间我们真的很不安啊，有类似生
: 病的宝妈吗可不可以讲讲这是不是流感还是肺炎脑膜炎甚至其它更严重的病？在线等
: 多谢。

w*x2013-01-06 08:01

7 楼

话是这么说没错, 但是15分钟内做出来我看100个人里也不一定有一个吧, 要不就是我
太差了

h*s2013-01-06 08:01

8 楼

多谢宝妈，希望是流感，他就在这101，102 之间。病毒肯定有因为我自己也得病了我
第六感觉自己就是被传染病毒了。
我嘴巴也长东西了也是病毒引起的现在也在吃药了。

【在 l********r 的大作中提到】

: 多少度？101，102问题不大。多半是流感。
: 退烧药本来就是暂时缓解，不会吃了就彻底退了。只有等病毒过了，才会退烧。现在能
: 做的就是每隔几小时查体温，药效过了就接着吃退烧药，等你发现什么时候体温回升的
: 时间段拉长了，就说明快好了。一般至少要两三天。

w*x2013-01-06 08:01

9 楼

要考虑的有正负,溢出(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;
}

k*a2013-01-06 08:01

10 楼

宝妈别太担心，小孩生病大人是挺操心的。如果医生检查过，应该不太会是脑膜炎吧。
最近是流感季节，我儿子也中招了。这两天才好。前些天也是鼻塞，咳嗽，没胃口，还
发烧，睡了好几天。发烧时也去看了医生，医生取了鼻涕样品检查确定是流感，给他开
了点药。不过医生说这药只是让孩子舒服些，并不真正治病。吃不吃药，都得5到6天才
能好。不过我儿子已经7岁了，不知是不是那流感的药太小小孩吃副作用大些。如果你
实在担心，可以打电话给你的儿医咨询有什么药让小宝吃了舒服些的吗。
希望你宝宝快快好起来。

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

: 二岁儿子咳嗽流鼻涕一星期了，是被我这个不合格的妈妈从外面带病毒给传染了，我现
: 在也在吃药主要是鼻子赛咳嗽的厉害，痰很多还一阵阵地发冷，但没有发烧。儿子这
: 二天发烧了，精神非常不好，食欲也很差，昨天我们带他去看医生，医生没给药说是让
: 他自己扛。昨晚儿子又发烧虽然有给他吃泰洛，吃了后烧退了，可是后来烧又上来了，
: 这样一直反复，昨晚去了ER，带了一些药回来，还是吃完好好完又发烧，准备明天带他
: 去看我们自己的儿医。可是从现在到明天还有很长时间我们真的很不安啊，有类似生
: 病的宝妈吗可不可以讲讲这是不是流感还是肺炎脑膜炎甚至其它更严重的病？在线等
: 多谢。

z*c2013-01-06 08:01

11 楼

Under pressure确实不容易写出来。

w*t2013-01-06 08:01

12 楼

你所有描述里，只有一点值得多观察
101，102烧得真不算高啊，我儿子这个温度活蹦乱跳得很
你家精神不好？？这一点你要密切关注一下，多休息看看
饭不吃没关系，我儿子有时病了就跟绝食一样，但液体不能少

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

: 多谢宝妈，希望是流感，他就在这101，102 之间。病毒肯定有因为我自己也得病了我
: 第六感觉自己就是被传染病毒了。
: 我嘴巴也长东西了也是病毒引起的现在也在吃药了。

H*e2013-01-06 08:01

13 楼

现在面试就是水涨船高

【在 z****c 的大作中提到】

: Under pressure确实不容易写出来。

h*s2013-01-06 08:01

14 楼

宝宝这是第二次生病了，这次是被我传染的，我内疚啊。都是因为上周末，我在公车上
有个中国人在我旁边咳嗽得很厉害还不遮嘴，我当时虽然赶紧用手遮嘴还拿面巾放嘴上
偷偷地吐口水到面巾里还是被这人传染了。我对宝宝内疚啊。

【在 w********t 的大作中提到】

: 描述有点混乱，一共发烧几天啦？
: 退烧药本来就是给了只退个烧，时间一过又回来的
: 但如果烧了3天还在继续，那就应该去看医生
: ER开的什么样？抗生素吗？
: 如果有抗生素，一般3天起效，3天没起效，去看医生
: 现在很多人都咳嗽，如果你儿子带喘，或呼吸不均，看医生
: 医生会帮助你孩子止喘，喘多了不好，喘多了容易哮喘
: 如果没有，就是咳一咳，没关系，家里注意加湿器就行
: 如果去看医生，注意2点，1，鼻子里取分泌物，可以检验是否FLU，有专门的药
: 2，听肺音，查血液氧气含量，是否肺炎

g*e2013-01-06 08:01

15 楼

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) {

h*s2013-01-06 08:01

16 楼

是啊，他前二天自己站得好好的突然摔倒了，过一会儿走路也摔倒了，本来都已经没有
nap了，竟然这几天又开始nap了。

【在 w********t 的大作中提到】

: 你所有描述里，只有一点值得多观察
: 101，102烧得真不算高啊，我儿子这个温度活蹦乱跳得很
: 你家精神不好？？这一点你要密切关注一下，多休息看看
: 饭不吃没关系，我儿子有时病了就跟绝食一样，但液体不能少

p*22013-01-06 08:01

17 楼

没感觉这题容易。mark一下。一会儿好好看看。

t*r2013-01-06 08:01

18 楼

作为非医学人士，私下表示感冒累了 nap 多点也是自然。
如果不放心，每 2 小时叫醒一次，看看各种反应是不是正常，眼睛和脖子
转动是不是正常，脖子有没有僵硬或者抬不起来等等。
ER 看过了，应该验血验过了。但如果还有怀疑，也可以去看 urgent care。

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

: 是啊，他前二天自己站得好好的突然摔倒了，过一会儿走路也摔倒了，本来都已经没有
: nap了，竟然这几天又开始nap了。

p*22013-01-06 08:01

19 楼

这题没有要求不能用减法吗？

t*r2013-01-06 08:01

20 楼

另外如果是肺炎的话，多半呼吸频率会升高。数一下呼吸频率，然后上网查查
正常范围。通常肺炎发烧会比较高。当然，如果不确定，总是让医生听一听更
保险。

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

: 是啊，他前二天自己站得好好的突然摔倒了，过一会儿走路也摔倒了，本来都已经没有
: nap了，竟然这几天又开始nap了。

y*n2013-01-06 08:01

21 楼

mark学习了。

h*s2013-01-06 08:01

22 楼

多谢。

【在 t*******r 的大作中提到】

: 作为非医学人士，私下表示感冒累了 nap 多点也是自然。
: 如果不放心，每 2 小时叫醒一次，看看各种反应是不是正常，眼睛和脖子
: 转动是不是正常，脖子有没有僵硬或者抬不起来等等。
: ER 看过了，应该验血验过了。但如果还有怀疑，也可以去看 urgent care。

y*n2013-01-06 08:01

23 楼

一定要写出最优算法么= =可不可以。每次用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
方法是一样的，我觉得这样比较好想一点。

l*n2013-01-06 08:01

24 楼

去ER应该检查排除
肺炎脑膜炎甚至其它更严重的病啊
还可以call nurse line

i*e2013-01-06 08:01

25 楼

没有考虑 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*x2013-01-06 08:01

26 楼

谢谢, 这个办法真好, 算是正常解发

【在 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*t2013-01-06 08:01

27 楼

which part?

【在 a*******r 的大作中提到】

: Read 'Structure and Interpretation of Comupter Programs"

j*b2013-01-06 08:01

28 楼

练习了一下
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*e2013-01-06 08:01

29 楼

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*b2013-01-06 08:01

30 楼

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*x2013-01-06 08:01

31 楼

最优的算法实现除法, 不能用* 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*r2013-01-06 08:01

32 楼

Read 'Structure and Interpretation of Comupter Programs"

z*c2013-01-06 08:01

33 楼

其实不难啊。基本思想就是把除数向左移位(×2)然后与被除数比较，直到发现仅次于
被除数的那个值，减去该值后继续。可以用递归做。

w*x2013-01-06 08:01

34 楼

话是这么说没错, 但是15分钟内做出来我看100个人里也不一定有一个吧, 要不就是我
太差了

w*x2013-01-06 08:01

35 楼

要考虑的有正负,溢出(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*c2013-01-06 08:01

36 楼

Under pressure确实不容易写出来。

H*e2013-01-06 08:01

37 楼

现在面试就是水涨船高

【在 z****c 的大作中提到】

: Under pressure确实不容易写出来。

g*e2013-01-06 08:01

38 楼

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*22013-01-06 08:01

39 楼

没感觉这题容易。mark一下。一会儿好好看看。

p*22013-01-06 08:01

40 楼

这题没有要求不能用减法吗？

y*n2013-01-06 08:01

41 楼

mark学习了。

y*n2013-01-06 08:01

42 楼

一定要写出最优算法么= =可不可以。每次用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*e2013-01-06 08:01

43 楼

没有考虑 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*x2013-01-06 08:01

44 楼

谢谢, 这个办法真好, 算是正常解发

【在 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*t2013-01-06 08:01

45 楼

which part?

【在 a*******r 的大作中提到】

: Read 'Structure and Interpretation of Comupter Programs"

j*b2013-01-06 08:01

46 楼

练习了一下
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*e2013-01-06 08:01

47 楼

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*b2013-01-06 08:01

48 楼

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*g2013-01-06 08:01

49 楼

这个解法没看懂呀，哪位看懂的能不能帮忙讲讲？
最好给个详细点儿的例子？
谢谢！

【在 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*g2013-01-06 08:01

50 楼

继续求解释~~~~~

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

: 这个解法没看懂呀，哪位看懂的能不能帮忙讲讲？
: 最好给个详细点儿的例子？
: 谢谢！

G*e2013-01-06 08:01

51 楼

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*i2013-01-06 08:01

52 楼

在你的基础上做了一下小修改的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*e2013-01-06 08:01

53 楼

我觉得不扯
而且电面不止15min吧，至少有25min可以用来写code。25min内整出这个不算什么高要
求。当然minor bug可能会有（+ - case）

r*z2013-01-06 08:01

54 楼

文科生上来捣个乱
改成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) {