c*****e
发帖数: 737 | 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*******l
发帖数: 12782 | 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*****e
发帖数: 737 | 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*****e
发帖数: 737 | 4 我觉得面试官也就靠记才知道，否则谁想得出？
况且现在popcnt(x)可以做到比他的trick更快。
【在 m*******l 的大作中提到】
: 150上有
| a********n
发帖数: 1287 | 5 这个没做过的确想不出来。
【在 c*****e 的大作中提到】
: 我觉得面试官也就靠记才知道，否则谁想得出？
: 况且现在popcnt(x)可以做到比他的trick更快。
|
|
