腾讯2015校招笔试之（二）整形长度算法思路实现

MichealGeng

背景
小伙伴参加了企鹅厂的2015校招笔试，有五道大题，拿出三道算法类的题尝试着实现实现。这是第二道题：计算整形长度
其中第一题：抽奖算法实现可以看这里


题目
第二题题目大意是：*在不使用sizeof()函数的情况下，取出本机的整形所占位数，如32位、64位等*。

分析
在计算机中，常用的基本类型为：char、short int、long int、float、double。所以本体的巧妙之处在于，你不知道这个整形到底是长整形还是短整型。
因此，不同的操作系统整形所占的位数长度是不同的。在常见的Windows操作系统中，int型其实是short int型；在其他的系统中则并不一定。但是在所有计算机中字符型（char）均占用一个字节，其他类型都比int型长（或相等），因此这道题需要通过char类型来确定int型所占位数。
具体设计思路如下：

• 申请一个整形变量并对其赋值
• 申请一个字符型数组，将字符型数组的首地址指向上面申请的整形变量
• 申请一个新的字符型数组和新的整形变量，并用新的数组首地址指向新的整型变量，将上面的字符型数组从头开始每一个元素对新的字符型数组进行赋值，赋值完后，比较两个整形是否相等，若想等则观察两个数组一共有几个元素相等，借此判断出整形占用几个字节
• 将字节转化为位数
  
  

源代码

[C] 纯文本查看 复制代码

#include<stdio.h>
int calculate();                // 判断整形所占字节数
int main()
{
        // 输出整形所占位数，其中位数=字节数×8
        printf("本台计算机整形所占位数为：%d\n", calculate() * 8);
        return 0;
}
int calculate()
{
        int ori;       // 用于存放原整形
        // C语言中整形申请不赋值会自动分配一个随机负数
        int ret = 0;   // 存放新数据
        // 防止随机分配的某些字节与ori相同，对其赋0
        char *orig = (char *)&ori;  // 用于存放原数据
        char *retu = (char *)&ret;  // 用于存放新数据
        //orig = (char *)&ori;   // 将原整形地址赋值给orig数组首地址
        //retu = (char *)&ret;   // 将新整形地址赋值给retu数组首地址
        for (int num=0; num<8; num++) // 由计算机组成原理知，int不会大于8个字节
        {
                retu[num] = orig[num]; // 逐次赋值
                /*
                整型变量地址和数组的首地址相同，
                若两整形值相同，
                则说明在数组从零开始到整形所占字节数处，每个元素只都相同。
                这里只需要取到第一次相同的值即可表明整形所占字节数
                */
                if (ori == ret)
                        return ++num;        // 返回整形所占字节数
        }
        return -1;
}

总结
企鹅厂这道题出的水准不错，考察了微机原理、计算机组成、数据结构、C语言编码等多方面能力。如果这道题将取整形所占位数改为取一个字符串所占位数的话，难度会降低一个档次。这里考察了求职者是否对微机原理和计算机组成方面相关的基本类型是否掌握；是否知道整形是基本类型中唯一一个长度不确定的类型，以及其他类型所占的长度。
另外在设计算法的时候，对C语言编码以及数据结构也做了考察，总的来说，我很喜欢这道题……不过很可惜，没有参加这个笔试。

seemk

MichealGeng 发表于 2015-4-18 15:21
请教一个问题，如果变量地址转换成整形后，比整形能够存储的最大数还大，怎么办？比如截断后，一个变量地 ...

抱歉之前说的可能不太准确，查了查资料重新整理下：

cpu的寻址能力就是地址总线决定的，CPU的地址总线位数一般大于等于该CPU的字长（比如8086 16位CPU的地址总线为20位，字长为16位，所以int型的最大值是65535，而寻址范围是1048576），这样看的话，你担心的情况还真有可能发生。在操作系统层上情况不太一样，比如32位系统所能使用的地址总线就是32位（尽管地址总线可能是36位或40位），所以32位系统的物理寻址能力应该是4GB（当然也有特殊的，另当别论），因为2^32次方为4GB ，但是操作系统一般有虚拟内存的概念，所以经常听人说windows中每个程序都有4GB的虚拟内存空间。结论：
1，在windows等操作系统下使用unsigned int来存储内存地址应该是安全的，不会发生你担心的情况。
2，一些特殊平台下可能会发生你说的情况吧，但是我猜测局部变量使用的栈地址空间应该不会超过CPU字长的范围。

L4Nce

大概想了想这样可以否

[C] 纯文本查看 复制代码

int main()
{
	int a;
	int b;
	printf("%d",(int)&a - (int)&b);
	return 0;
}

//另外这句话，C语言中整形申请不赋值会自动分配一个随机负数。如果是局部变量只是取默认的栈中的值而已，并不是随机的也不一定是负的吧。
另外我感觉还可以用溢出的办法求得int的长度
int a=0;
a++
看a什么时候溢出就知道a的长度了。

cxxxx

int Ar[2];
int len = &Ar[1] - &Ar[0];


这样可以么..

gmh5225

L4Nce 发表于 2015-4-18 12:48
大概想了想这样可以否
[mw_shl_code=c,true]int main()
{

正如大神所说，不是随机数，看了大神的解答，非常膜拜~~~

gmh5225

L4Nce 发表于 2015-4-18 12:48
大概想了想这样可以否
[mw_shl_code=c,true]int main()
{

需要是连续的地址，大神看看我说的是否有道理。。

gmh5225

[C] 纯文本查看 复制代码

int a[1];
	printf("%d",(int)&a[1]-(int)&a[0]);

按照1楼大神的思路，不知道这样可行否。。。

MichealGeng

L4Nce 发表于 2015-4-18 12:48
大概想了想这样可以否
[mw_shl_code=c,true]int main()
{

我感觉你这个办法更好，而且我那个注释确实不严谨。
大神，交个朋友吧。

MichealGeng

L4Nce 发表于 2015-4-18 12:48
大概想了想这样可以否
[mw_shl_code=c,true]int main()
{

请教一个问题，如果变量地址转换成整形后，比整形能够存储的最大数还大，怎么办？比如截断后，一个变量地址为9999，一个变量地址溢出为0000。还是一定不会出现这种情况。
见谅我不是学计算机的，对计算机特别底层的东西不是很清楚……

pxm2525

代码编译不过去啊。。。我是菜鸟= =

f2pjn0xo01

感谢分享，学习了。