爱站seo,个人网站备案核验单填写,域名备案与网站备案的区别,网站设计定做接前一篇文章#xff1a;Linux内核与驱动面试经典“小”问题集锦#xff08;5#xff09; 问题8
问#xff1a;如何判断一个数是否是2的幂次#xff08;假设最多32位#xff09;#xff1f;
备注#xff1a;此问题是笔者年前参加小米面试时遇到的一个问题#xff0c…接前一篇文章Linux内核与驱动面试经典“小”问题集锦5 问题8
问如何判断一个数是否是2的幂次假设最多32位
备注此问题是笔者年前参加小米面试时遇到的一个问题是属于面试中的笔试。原题是一语句实现y是否为2的若干次幂的判断。 答
其实上图中已经提供了一些思路先要观察规律为了简化以8位为例 正例 10x01即0b000000012的0次幂 20x02即0b000000102的1次幂 40x04即0b000001002的2次幂 …… 1280x80即0b100000002的7次幂 反例 30x03即0b00000011 50x05即0b00000101 60x06即0b00000110 70x07即0b00000111 当时那为面试官还蛮有耐心还提示到要从本数和其掩码的方面考虑。不过本人资质比较愚钝一时也没有找到规律。他后来直接给出了答案也就是上图中的那个
#define is2pow(x) ((x (x-1)) 0)
验证
x1时x (x-1)为0返回真说明是2的幂次。x2时x (x-1)为0返回真说明是2的幂次。x4时x (x-1)为0返回真说明是2的幂次。x8时x (x-1)为0返回真说明是2的幂次。x3时x (x-1)为2返回假说明不是2的幂次。x5时x (x-1)为4返回假说明不是2的幂次。x6时x (x-1)为4返回假说明不是2的幂次。x7时x (x-1)为6返回假说明不是2的幂次。
总结
这道题背后考察的不光是候选者的智商和数字敏感性而更多地是考察内核的功力因为Linux内核中有很多基于2的幂次的判断。对于此不熟悉说明对于内核与驱动看得不够透彻、不够精通。 问题9
问container_of内核中经常遇到吧请写出其具体的代码实现
备注此问题是笔者年前参加小米面试时遇到的一个问题是属于面试中的笔试。笔者几年之前参加位于北京玉泉慧谷的一家公司公司名字已不记得了只记得地点面试的时候也被问到过这个问题不过当时只是和面试官说了思路并没有直接写出完整代码。
答
container_of(ptr, type, member)宏的作用是通过结构体成员的地址和结构体类型推导出结构体的地址type是指结构体的类型member是成员在结构体中的名字ptr是该成员在type结构体中的地址。
实际上笔者多年来看内核的代码经常会遇到container_of也花时间研究过代码尤其是之前面试中被问到时面试结束回来后曾经认真研究过一番。但是几次都是当时弄得很明白时间一长就淡忘了。并不能做到信手拈来这也应该是不经常玩内核的一种不足。
笔者在小米面试时被问到这个问题后就努力在脑海中回忆container_of这个宏的具体实现。依稀记得是这样
#define container_of(pointer, structure, member) (structure *)(pointer - (((structure *)0)-member))
这是当时笔者第一时间想出来的。但是并不完全正确。
当时面试官说要实现container_of宏必须先实现offset_off宏因此笔者就没有直接给出container_of的实现而是按照面试官的思路即要求先写出了offset_off宏如下
#define offset_off(structure, member) ((((structure *)NULL)-member))
这样写完了之后面试官指出了不足应该将偏移强制转换为int类型如下
#define offset_off(structure, member) ((int)(((structure *)NULL)-member))
完成了offset_off宏之后进一步再实现container_of宏我开始的实现是这样
#define container_of(pointer, structure, member) ((int)(pointer) - offset_off(structure, member))
面试官又指出了一处不足应该强制转换为void *类型更正后实现如下
#define container_of(pointer, structure, member) (void *)((int)(pointer) - offset_off(structure, member))
将offset_off宏完全展开后最终得到
#define container_of(pointer, structure, member) (void *)((int)(pointer) - ((int)(((structure *)NULL)-member)))
和笔者最开始所构想的进行对比
最初构想的
#define container_of(pointer, structure, member) (structure *)(pointer - (((structure *)0)-member)) 最终实现的
#define container_of(pointer, structure, member) (void *)((int)(pointer) - ((int)(((structure *)0)-member))) 总结
通过以上过程可以发现虽然在大方向上能够答出但在细节、精细度上和大公司那些人还是有一些差距这是今后做技术需要弥补的。
在此顺带给出Linux内核中container_of宏的完整实现在include/linux/container_of.h中实际上内核中有多处实现但最为“正宗”的是这一个代码如下
/*** container_of - cast a member of a structure out to the containing structure* ptr: the pointer to the member.* type: the type of the container struct this is embedded in.* member: the name of the member within the struct.** WARNING: any const qualifier of ptr is lost.*/
#define container_of(ptr, type, member) ({ \void *__mptr (void *)(ptr); \static_assert(__same_type(*(ptr), ((type *)0)-member) || \__same_type(*(ptr), void), \pointer type mismatch in container_of()); \((type *)(__mptr - offsetof(type, member))); })
这个正宗的container_of的定义比较复杂换一个相对比较好理解的版本在tools/include/linux/kernel.h中代码如下
#define offsetof(TYPE, MEMBER) ((size_t) ((TYPE *)0)-MEMBER)/*** container_of - cast a member of a structure out to the containing structure* ptr: the pointer to the member.* type: the type of the container struct this is embedded in.* member: the name of the member within the struct.**/
#define container_of(ptr, type, member) ({ \const typeof(((type *)0)-member) * __mptr (ptr); \(type *)((char *)__mptr - offsetof(type, member)); })
对比
