面试被问了议题: check if an integer is power of 2 (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

面试被问了议题: check if an integer is power of 2 (转载)

面试被问了议题: check if an integer is power of 2 (转载)# JobHunting - 待字闺中

c*e2012-02-15 08:02

1 楼

【以下文字转载自 Programming 讨论区】
发信人: coollpe (coollpe), 信区: Programming
标题: 面试被问了议题: check if an integer is power of 2
发信站: BBS 未名空间站 (Wed Feb 15 10:16:41 2012, 美东)
我首先回答了每次左移移1位比较，然后面试官不满意，我又想出来bitmap，开个64k数
组，他说能不能只有1条语句的判断，我死活想不出来。
后来回家google发现了 x & (x-1)这个trick。不过我觉得如果没看到过的话要在面试
时间内想出来简直不可能。
测试了一下，bitmap的速度要比 x && (x & (x-1))快一些。但机器不同结果也不同。
回家我又想了若干方法
1, popcnt (x) == 1, 新处理器已经可以在1个指令周期内完成。
2, ffs(x)查表，这个表大概只要存32个整数，占用存储小很多，速度和x & (x-1)差不多
3, asm bsrl, asfl, 2个指令周期+1次比较，和x && (x & (x-1)一样快

m*l2012-02-15 08:02

2 楼

150上有

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

: 【以下文字转载自 Programming 讨论区】
: 发信人: coollpe (coollpe), 信区: Programming
: 标题: 面试被问了议题: check if an integer is power of 2
: 发信站: BBS 未名空间站 (Wed Feb 15 10:16:41 2012, 美东)
: 我首先回答了每次左移移1位比较，然后面试官不满意，我又想出来bitmap，开个64k数
: 组，他说能不能只有1条语句的判断，我死活想不出来。
: 后来回家google发现了 x & (x-1)这个trick。不过我觉得如果没看到过的话要在面试
: 时间内想出来简直不可能。
: 测试了一下，bitmap的速度要比 x && (x & (x-1))快一些。但机器不同结果也不同。
: 回家我又想了若干方法

c*e2012-02-15 08:02

3 楼

比较最高位1的位置是否等于最低位1的位置
bool isPowerOfTwo(int x_)
{
register int bitpos, bitpos2;
asm ("bsrl %1,%0": "+r" (bitpos):"rm" (x_));
asm ("bsfl %1,%0": "+r" (bitpos2):"rm" (x_));
return bitpos == bitpos2;
}

c*e2012-02-15 08:02

4 楼

我觉得面试官也就靠记才知道，否则谁想得出？
况且现在popcnt(x)可以做到比他的trick更快。

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

: 150上有