w********s
发帖数: 1570 | 1 第一题，其他方法包括：
1, bit count(n)
如果"1"为1个，那么就是2^n，可以用1条cpu instruction解决，叫popcnt，如果面试
你的不知道什么叫popcnt，那么太差劲了。
2, bsr == bsf，也就是左边数起1的位置==从右边数起1的位置
2条386汇编解决。
-1 |
|
g******z
发帖数: 5809 | 2 提升的SSE4.2
SSE4指令集被认为是2001年以来Intel最重要的指令集扩展，包含54条指令。
Intel在Penryn处理器中加入了对SSE4.1的支持，共增加了47条新指令，提升了处理器
在图形、3D图像与游戏、视频编码与影音处理等方面的性能表现。本次在Nehalem处理
器中，进一步支持了SSE4.2指令集。SSE4.2完整的实现了SSE4指令集，相对于SSE4.1加
入了7条新指令。
SSE4.2指令集
SSE4.2新加入的几条新指令有两类。第一类是字符串与文本新指令STTNI，STTNI包
含了四条具体的指令。STTNI指令可以对两个16位的数据进行匹配操作，以加速在XML分
析方面的性能。据Intel表示，新指令可以在XML分析方面取得3.8倍的性能提升。第二
类指令是面向应用的加速指令ATA。ATA包括冗余校验的CRC32指令、计算源操作数中非0
位个数的POPCNT指令，以及对于打包的64位算术运算的SIMD指令。 CRC32指令可以取代
上层数据协议中经常用到的循环冗余校验，据Intel表示其加速比可以达到6.5~18.6倍
；POPCNT用于 |
|
f*******u
发帖数: 76 | 3 by the way, you can also mention that the instruction POPCNT in x86 SSE4 can
do it by hardware. |
|
c*****e
发帖数: 737 | 4 【 以下文字转载自 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)一样快 |
|
c*****e
发帖数: 737 | 5 我觉得面试官也就靠记才知道，否则谁想得出？
况且现在popcnt(x)可以做到比他的trick更快。 |
|
w********s
发帖数: 1570 | 6 大概很多人都知道：
return x_ && (x_ & (x_ - 1)) == 0;
不过随着科技的进步，这个方法也落伍了，现在有了比这个还快2倍不止的方法:
return __builtin_popcount(x_) == 1;
经测试，popcnt在cpu的指令集支持下，比前方法快2.5倍。 |
|
|
r*****s
发帖数: 1815 | 8 POPCNT
原理应该也是查表
: n -= n |
|
r*****s
发帖数: 1815 | 9 popcnt指令集里没有的时候_mm_popcnt_u32就退化成这个。。
: 不查表的话，上个面试不会考的做法，O(lg8n) = O(3n)的：
: int main()
: {
: vector arr = {1,2,3,4,5,6,7,8,9,255};
: int sum = 0;
: for (auto n : arr)
: {
: n = (n |
|
f*******u
发帖数: 76 | 10 by the way, you can also mention that the instruction POPCNT in x86 SSE4 can
do it by hardware. |
|
f*******u
发帖数: 76 | 11 by the way, you can also mention that the instruction POPCNT in x86 SSE4 can
do it by hardware. |
|
f*******u
发帖数: 76 | 12 by the way, you can also mention that the instruction POPCNT in x86 SSE4 can
do it by hardware. |
|
f*******u
发帖数: 76 | 13 by the way, you can also mention that the instruction POPCNT in x86 SSE4 can
do it by hardware. |
|
f*******u
发帖数: 76 | 14 by the way, you can also mention that the instruction POPCNT in x86 SSE4 can
do it by hardware. |
|
f*******u
发帖数: 76 | 15 by the way, you can also mention that the instruction POPCNT in x86 SSE4 can
do it by hardware. |
|
f*******u
发帖数: 76 | 16 by the way, you can also mention that the instruction POPCNT in x86 SSE4 can
do it by hardware. |
|
f*******u
发帖数: 76 | 17 by the way, you can also mention that the instruction POPCNT in x86 SSE4 can
do it by hardware. |
|
a*o
发帖数: 19981 | 18 这啥烂bug？为啥好多文章都来这么一出？
发信人: fancieryu (Breeze), 信区: paladin
标 题: Re: 有什么好方法找int的binary表示里面1的个数？
发信站: BBS 未名空间站 (Sun Apr 4 23:15:19 2010, 美东)
by the way, you can also mention that the instruction POPCNT in x86 SSE4 can
do it by hardware. |
|
f*******u
发帖数: 76 | 19 by the way, you can also mention that the instruction POPCNT in x86 SSE4 can
do it by hardware. |
|
e*p
发帖数: 526 | 20 不是atom，是haswell赛扬. see flags: vmx
vendor_id : GenuineIntel
cpu family : 6
model : 69
model name : Intel(R) Celeron(R) 2955U @ 1.40GHz
stepping : 1
microcode : 0x15
cpu MHz : 1400.000
cache size : 2048 KB
physical id : 0
siblings : 2
core id : 0
cpu cores : 2
apicid : 0
initial apicid : 0
fpu : yes
fpu_exception : yes
cpuid level : 13
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat
pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb
r... 阅读全帖 |
|
v*******e
发帖数: 11604 | 21
processor : 3
vendor_id : GenuineIntel
cpu family : 6
model : 37
model name : Intel(R) Core(TM) i7 CPU M 620 @ 2.67GHz
stepping : 2
microcode : 0xe
cpu MHz : 1866.000
cache size : 4096 KB
physical id : 0
siblings : 4
core id : 2
cpu cores : 2
apicid : 5
initial apicid : 5
fpu : yes
fpu_exception : yes
cpuid level : 11
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov
pat p... 阅读全帖 |
|
c*****e
发帖数: 737 | 22 我首先回答了每次左移移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)一样快 |
|
c*****e
发帖数: 737 | 23 我首先回答了每次左移移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)一样快 |
|
