j**l
发帖数: 2911 | 1 下午发帖子问了道设计restaurant reservation system的题目，电面的时候真的就问
到了
http://www.mitbbs.com/article_t/JobHunting/31607277.html
更离奇的是，事后发现我的问题和之前的一个面经的内容和次序几乎一模一样
http://www.mitbbs.com/article/JobHunting/31585437_3.html
First phone:
1. how to find out the max value of int in C++
2. data structure in C++ that you know
3. different between list and array
4. design a restaurant reservation system
5. make a loop out of list in STL and write code to detect it.
除了第5题改为manually calculate how many hours are there in 2 |
r****o
发帖数: 1950 | 2 Cong!
【在 j**l 的大作中提到】
: 下午发帖子问了道设计restaurant reservation system的题目，电面的时候真的就问
: 到了
: http://www.mitbbs.com/article_t/JobHunting/31607277.html
: 更离奇的是，事后发现我的问题和之前的一个面经的内容和次序几乎一模一样
: http://www.mitbbs.com/article/JobHunting/31585437_3.html
: First phone:
: 1. how to find out the max value of int in C++
: 2. data structure in C++ that you know
: 3. different between list and array
: 4. design a restaurant reservation system
|
r****o
发帖数: 1950 | 3 how to find out the max value of int in C++?
这题是什么意思啊？
【在 j**l 的大作中提到】
: 下午发帖子问了道设计restaurant reservation system的题目，电面的时候真的就问
: 到了
: http://www.mitbbs.com/article_t/JobHunting/31607277.html
: 更离奇的是，事后发现我的问题和之前的一个面经的内容和次序几乎一模一样
: http://www.mitbbs.com/article/JobHunting/31585437_3.html
: First phone:
: 1. how to find out the max value of int in C++
: 2. data structure in C++ that you know
: 3. different between list and array
: 4. design a restaurant reservation system
|
w********p
发帖数: 948 | |
m*****g
发帖数: 226 | 5 MAX_INT?
【在 r****o 的大作中提到】
: how to find out the max value of int in C++?
: 这题是什么意思啊？
|
s********l
发帖数: 998 | 6 bless & cong~
同问
感觉这跟算法有关 和语言没关系啊~
【在 r****o 的大作中提到】
: how to find out the max value of int in C++?
: 这题是什么意思啊？
|
j**l
发帖数: 2911 | 7 int size = sizeof(int);
int bits = size * 8;
unsigned long num = 1;
num = num << (bits - 1);
long max_int = num - 1；
【在 r****o 的大作中提到】
: how to find out the max value of int in C++?
: 这题是什么意思啊？
|
n******r
发帖数: 1247 | 8 cong and bless!
【在 j**l 的大作中提到】
: 下午发帖子问了道设计restaurant reservation system的题目，电面的时候真的就问
: 到了
: http://www.mitbbs.com/article_t/JobHunting/31607277.html
: 更离奇的是，事后发现我的问题和之前的一个面经的内容和次序几乎一模一样
: http://www.mitbbs.com/article/JobHunting/31585437_3.html
: First phone:
: 1. how to find out the max value of int in C++
: 2. data structure in C++ that you know
: 3. different between list and array
: 4. design a restaurant reservation system
|
B*****t
发帖数: 335 | 9 这个好像不对吧！
【在 j**l 的大作中提到】
: int size = sizeof(int);
: int bits = size * 8;
: unsigned long num = 1;
: num = num << (bits - 1);
: long max_int = num - 1；
|
l******h
发帖数: 405 | 10 最后一句应该是max_int = max_int - 1 + max_int吧。
【在 B*****t 的大作中提到】
: 这个好像不对吧！
|
|
|
r****o
发帖数: 1950 | 11 typo吧, 应该是max_int<<=bits-1;
我发现这样也可以:
unsigned int max_uint=~0;
int max_int=max_uint/2;
【在 B*****t 的大作中提到】
: 这个好像不对吧！
|
j**l
发帖数: 2911 | 12 typo, 应该是
long max_int = 1;
max_int = (max_int << (bits - 1));
max_int--;
因为最高位是符号位
所以
bits = 4时， max_int = 2^3 - 1 = 7
bits = 16时，max_int = 2^15 - 1 = 32767
【在 B*****t 的大作中提到】
: 这个好像不对吧！
|
y*c
发帖数: 904 | |
S*******n
发帖数: 1867 | 14 在visual c++下面实验了一下
其实max_int的type是int一样奏效
int的size和long的size应该都是一样的 会有溢出的问题
用unsigned int才不会有溢出的问题
但是这三种类型之后获得的结果都是一样的
但是max_int 在 max_int 这一步之前的值是不一样的
【在 j**l 的大作中提到】
: int size = sizeof(int);
: int bits = size * 8;
: unsigned long num = 1;
: num = num << (bits - 1);
: long max_int = num - 1；
|
j**l
发帖数: 2911 | 15 我事后也考虑到万一long和int在有些机器上等长就有溢出风险了
确实应该用unsigned long
【在 S*******n 的大作中提到】
: 在visual c++下面实验了一下
: 其实max_int的type是int一样奏效
: int的size和long的size应该都是一样的 会有溢出的问题
: 用unsigned int才不会有溢出的问题
: 但是这三种类型之后获得的结果都是一样的
: 但是max_int 在 max_int 这一步之前的值是不一样的
|
B*****t
发帖数: 335 | 16 您这个改了还是不对吧！
【在 j**l 的大作中提到】
: typo, 应该是
: long max_int = 1;
: max_int = (max_int << (bits - 1));
: max_int--;
: 因为最高位是符号位
: 所以
: bits = 4时， max_int = 2^3 - 1 = 7
: bits = 16时，max_int = 2^15 - 1 = 32767
|
j**l
发帖数: 2911 | 17 说说看？
【在 B*****t 的大作中提到】
: 您这个改了还是不对吧！
|
w****m
发帖数: 146 | 18 int 和 long在32bit都是4 byte
可以用long long来..
【在 S*******n 的大作中提到】
: 在visual c++下面实验了一下
: 其实max_int的type是int一样奏效
: int的size和long的size应该都是一样的 会有溢出的问题
: 用unsigned int才不会有溢出的问题
: 但是这三种类型之后获得的结果都是一样的
: 但是max_int 在 max_int 这一步之前的值是不一样的
|
S*******n
发帖数: 1867 | 19 是对的 虽然有可能有溢出问题 不过最后结果是对的 哈哈
【在 B*****t 的大作中提到】
: 您这个改了还是不对吧！
|
S*******n
发帖数: 1867 | 20 才知道这种type。。
【在 w****m 的大作中提到】
: int 和 long在32bit都是4 byte
: 可以用long long来..
|
|
|
j**l
发帖数: 2911 | 21 如果sizeof(int) == sizeof(long) == 4
虽然运行结果也对，
但就好比4位时候1000 - 1 = 0111, 背后实际上是 -8 - 1 = +7
最好用
unsigned long num = 1;
num <<= (bits - 1);
long max_int = num - 1;
【在 B*****t 的大作中提到】
: 您这个改了还是不对吧！
|
y*c
发帖数: 904 | 22
可以用按位去反～吧
【在 j**l 的大作中提到】
: 如果sizeof(int) == sizeof(long) == 4
: 虽然运行结果也对，
: 但就好比4位时候1000 - 1 = 0111, 背后实际上是 -8 - 1 = +7
: 最好用
: unsigned long num = 1;
: num <<= (bits - 1);
: long max_int = num - 1;
|
j**l
发帖数: 2911 | 23 这个主意好
4位的情况
~(1000) = 0111?
感觉位操作的tricks很多阿
【在 y*c 的大作中提到】
:
: 可以用按位去反～吧
|
B*****t
发帖数: 335 | 24 only if max_int is defined as unsigned, but I didn't see the
definition.
【在 S*******n 的大作中提到】
: 是对的 虽然有可能有溢出问题 不过最后结果是对的 哈哈
|
c******f
发帖数: 2144 | |
S*******n
发帖数: 1867 | 26 定义为int或者long的结果在visual c++里面和定义为unsigned的是一样的
只是这个操作是不完全正确的
因为会溢出 见上面楼主的解释
【在 B*****t 的大作中提到】
: only if max_int is defined as unsigned, but I didn't see the
: definition.
|
j**l
发帖数: 2911 | 27 用unsigned long是最好的
用signed long只是碰巧运行结果对而已
我们用4位的signed int例子说明，范围是-8到+7
这个+7怎么来呢？
如果不用unsigned, 1 << 3实际上是1000, 表示-8而不是+8
减1的结果，虽然正确得到+7 (1000 - 1 = 0111)
但背后的逻辑会让人困惑 -8 - 1 = +7?
用unsigned, 就是+8 - 1 = +7了
【在 B*****t 的大作中提到】
: only if max_int is defined as unsigned, but I didn't see the
: definition.
|
y*c
发帖数: 904 | 28
1000 - 1 其实是 1000 + 1111 = 0111 加一个溢出位。既然我们用了最高位来表示正
负，就不能用它来做有溢出的运算了
用取反运算就明确是对位操作，而不是算术操作。
【在 j**l 的大作中提到】
: 用unsigned long是最好的
: 用signed long只是碰巧运行结果对而已
: 我们用4位的signed int例子说明，范围是-8到+7
: 这个+7怎么来呢？
: 如果不用unsigned, 1 << 3实际上是1000, 表示-8而不是+8
: 减1的结果，虽然正确得到+7 (1000 - 1 = 0111)
: 但背后的逻辑会让人困惑 -8 - 1 = +7?
: 用unsigned, 就是+8 - 1 = +7了
|
B*****t
发帖数: 335 | 29 建议您把unsigned和signed的在计算机内的存储以及各种在unsigned和signed上的运
算好好看看
【在 j**l 的大作中提到】
: 用unsigned long是最好的
: 用signed long只是碰巧运行结果对而已
: 我们用4位的signed int例子说明，范围是-8到+7
: 这个+7怎么来呢？
: 如果不用unsigned, 1 << 3实际上是1000, 表示-8而不是+8
: 减1的结果，虽然正确得到+7 (1000 - 1 = 0111)
: 但背后的逻辑会让人困惑 -8 - 1 = +7?
: 用unsigned, 就是+8 - 1 = +7了
|
j**l
发帖数: 2911 | 30 是不是有一个寄存器的标志位专门表示溢出？还有其他标志位表示进位...
【在 y*c 的大作中提到】
:
: 1000 - 1 其实是 1000 + 1111 = 0111 加一个溢出位。既然我们用了最高位来表示正
: 负，就不能用它来做有溢出的运算了
: 用取反运算就明确是对位操作，而不是算术操作。
|
|
|
S*******n
发帖数: 1867 | 31 详细说说？
【在 B*****t 的大作中提到】
: 建议您把unsigned和signed的在计算机内的存储以及各种在unsigned和signed上的运
: 算好好看看
|
j**l
发帖数: 2911 | 32 我的理解，假定int是4位二进制,
则signed int 的取值范围是从-8到+7，最高位是符号位并采用补码表示法，而
unsigned int的取值范围是0到+15
如果i = 1000是signed int变量，则它表示-8
i--, 计算机就是机械的给它加上1111, 从而得到0111, 也就是+7
-8 - 1的算术运算发生溢出，你得不到-9这个你要的结果(它根本不在-8到+7的表示范
围内), 而只能得到+7
如果i = 1000是unsigned int变量，则它表示+8
i--, 计算机同样机械的给它加上1111, 从而得到0111, 也就是+7
+8 - 1的算术运算没有发生溢出，你得到的+7(它在0到+15的表示范围内)正是你要的结果
【在 y*c 的大作中提到】
:
: 1000 - 1 其实是 1000 + 1111 = 0111 加一个溢出位。既然我们用了最高位来表示正
: 负，就不能用它来做有溢出的运算了
: 用取反运算就明确是对位操作，而不是算术操作。
|
j**l
发帖数: 2911 | 33 我的看法是，对四位二进制整数，计算机才不care它是signed还是unsigned, 对减去1
的操作，总是机械的加上1111
以1010为例子，加上1111并丢弃任何最高位的进位得到1001
1. 假如1010是unsigned, 则它表示10，而1001表示9，等式为10 - 1 = 9， 正确
2. 假如1010是signed,则补码表示-6，而1001的补码表示-7,等式为-6 - 1 = -7， 同
样正确
这两种情形都没有溢出。9在区间[0, 15]内，而-7也在区间[-8, 7]内
以1000为例子，加上1111并丢弃任何最高位的进位得到0111
3. 假如1000是unsigned, 则它表示8，而0111表示7，等式为8 - 1 = 7， 正确
4. 假如1000是signed,则该补码表示-8，而0111表示7,等式为-8 - 1 = 7， 不正确
情形3没有溢出，而4溢出了。7在区间[0, 15]内，而-9已不在区间[-8, 7]内了
【在 S*******n 的大作中提到】
: 详细说说？
|
t****t
发帖数: 6806 | 34 i think he want you to use
std::numeric_limits::max()
std::numeric_limits::min()
instead of this...
【在 j**l 的大作中提到】
: int size = sizeof(int);
: int bits = size * 8;
: unsigned long num = 1;
: num = num << (bits - 1);
: long max_int = num - 1；
|
t****t
发帖数: 6806 | 35 actually this is more correct than using bit operations, although this is
the method for C. C++ uses numeric_limits::max() (which is uniform for
all numerical types). the problem of bit operations is, number of bits is
not necessary 8*sizeof(), although it is extremely unlikely.
BTW, if interviewer just want to check whether a (long) input is in the
range
of int, you can just check long(int(i))==i. This is much easier.
【在 m*****g 的大作中提到】
: MAX_INT?
|
j**l
发帖数: 2911 | 36 这个对C不行吧，他说是C/C++，没说一定是C++
另外他提示说要用到sizeof
【在 t****t 的大作中提到】
: i think he want you to use
: std::numeric_limits::max()
: std::numeric_limits::min()
: instead of this...
|
t****t
发帖数: 6806 | 37 well, if you check your OP, you said c++.
【在 j**l 的大作中提到】
: 这个对C不行吧，他说是C/C++，没说一定是C++
: 另外他提示说要用到sizeof
|
