有没有好的公式. 能得出 一个byte中哪一位是1 如 00000100 得出3,(第三位是1),

selfrun

这个需求中，输入参数只有一个bit位为1, 例如:
unsigned char x = 00100000b; //如果将x值减1,看下面
x - 1 == 00011111;//看到了么，只要求出这个x-1中的bit个数，就是x中 那个为1的bit的偏移
剩下的问题，就是求一个byte中有多少个bit为1
求一个整数中bit为1的个数的方法，有过很多讨论，目前有两种比较优秀的，一种是查表，还有一种是多个bit位的加法，
查表方法对这个例子是比较合适的，一个byte，表格最大256个字节，只需一次内存读取操作。

多次加法的方法，是利用这样的方法:
  假设是32位的整数,
  第一步: 将bit0 与 bit1 的1的个数的和 放入 bit0和bit1这两位中; 将bit2和bit3中1的个数的和放如bit2和bit3中..... 将bit30和bit31的和放入bit30和bit31中.
  这些加操作只需用一次加法操作: x = ( (x >> 1) & 01010101010101010101010101010101b ) + (x & 01010101010101010101010101010101b)
  第二步: 重复第一步的思路, 这次是把每4 个 bit中 bit为 1的个数 存如这4个bit中,只要把上次操作的每两个bit的和相加就好: x = ((x >> 2) & 00110011001100110011001100110011b) + (x & 00110011001100110011001100110011b);
  第三步: 将每 8个bit中 bit为1的个数存入8个bit中,同样是取前次的4个bit的和:
x = ((x >> 4) & 00001111000011110000111100001111b) + ( x & 00001111000011110000111100001111b );
  第四步: 将每16个bit中bit为1的个数存入16个bit中,这次是取每个字节的和:
x = ((x >> & 00000000111111110000000011111111b) + ( x & 00000000111111110000000011111111b );
  第五步; 将32个bit中bit为1的个数存入32个bit中
x = ((x >> 16) & 0x0FFFF) + (x & 0x0FFFF );
x就是结果;
如果是字节,执行到第三步就得到结果了,这个方法的复杂度是O(logn),如果用查表计算32位或更大的数
就得通过多次查表求和，这个次数的复杂度是O(n)的

yecheng_110

原帖由 selfrun 于 2008-9-23 22:11 发表
这个需求中，输入参数只有一个bit位为1, 例如:
unsigned char x = 00100000b; //如果将x值减1,看下面
x - 1 == 00011111;//看到了么，只要求出这个x-1中的bit个数，就是x中 那个为1的bit的偏移
剩下的问题， ...

化简为繁？

rag

n=1/log(2,unsigned char byte)
n：为1的位数

jamesr

汇编那个应该最快, 一个指令周期就可以搞定, 只要一个存储单元, 计算都在内部寄存器里搞定. 如果需要在更长的位串里面进行测试, 还可以考虑MMX, 或者SSE, 现在amd和intel的cpu都支持这些指令.

第二快得就是查表, 如果不是重复复计算byte中的这个有效位, 优势也不大, 因为建立表也要花费时间, 否则就很快. 不过比单指令的汇编多了计算地址的操作. 这两个是O(1)的时间复杂度, 时间单位是指令周期哦.

插值多项式很有创意, 但是执行起来由于乘法运算不见得比for循环快, 而且占了O(n)的指令空间, O(n)的时间复杂度,不实用.

switch就更不实用了, 平均起来, 每个test做4次的比较和跳转, 而且生成大量的指令, 跳转可是性能的杀手, 能不用就不用. switch 就象把车从高速开到石子路上一样, 痛苦.

对数表达起来很简单, 但是运算起来却很慢, 查表或者逼近, 而且还是浮点运算, 效率很差.

看来你对CPU的了解还不够。
汇编使用ffs应该是最快了，这点应该没错，但不是一个指令周期就能完成。ffs是长指令，执行时会分解为多步微码，至少需要近十个指令周期才能完成。只有一系列ffs完全流水线化，指令完成时间才会会接近一个周期。

查表如果不算构造表的时间，的确是很快。这一点上我与你完全相同。

插值多项式绝对比switch慢。

我的观点是，除了不算构造表开销的查表法和ffs汇编指令外，任何方法都没有switch快。

你所谓的大量比较和跳转是性能杀手的理解有误。
跳转为何性能低下？因为CPU不知道分支（分支才是正确的说法）往哪里进行。
现代CPU都有分支预测机制，只要分支的两边稍稍不平衡（49%-51%），就会有很高的正确预测率。
在switch的例子中，比较只需一个指令；而分支的两边很不平衡，选择分支和选择不分支的比率大约是1：7（8位中只有1位为1），分支预测机制会选择不分支，这样就有87.5％的成功预测率。这样的成功预测率足以保证多数指令的连续进行而不会“开到石子路上”。

mik

原帖由 jamesr 于 2008-9-30 11:14 发表

看来你对CPU的了解还不够。
汇编使用ffs应该是最快了，这点应该没错，但不是一个指令周期就能完成。ffs是长指令，执行时会分解为多步微码，至少需要近十个指令周期才能完成。只有一系列ffs完全流水线化，指令 ...

ffs 指令? 是啥?  
x86 只有 bsf 或者 bsr

近10个指令周期夸张了点，大概 4 个左右吧

win_hate

Lz 说要 “公式”，但是...

让我们继续，ML 的

1. 
   
2. fun f 1=0|f 2=1|f 4=2|f 8=3|f 16=4|f 32=5|f 64=6|f 128=7;
   

复制代码

1. 
   
2. - map f [1,2,4, 8,16,32,64, 128];
   
3. > val it = [0, 1, 2, 3, 4, 5, 6, 7] : int list
   
4. - f 0;
   
5. ! Uncaught exception:
   
6. ! Match
   
7. -
   

复制代码

jamesr

[quote]原帖由 mik 于 2008-9-30 12:13 发表

ffs 指令? 是啥?  
x86 只有 bsf 或者 bsr

近10个指令周期夸张了点，大概 4 个左右吧

笔误，原来想说的是find-first-bit。x86的指令不了解，刚刚在gcc中看了半天，也没有看出你说的这两个指令要多少周期（貌似x86有所谓的prefixed指令一说，搞得我一点概念也没有）。
[/quote]

刚刚在CPU与编译器版看到了被顶上来的《intel 指令集（含时钟周期）》，也是mik你07年发的，终于找到了bsr的延迟

[ 本帖最后由 jamesr 于 2008-9-30 13:12 编辑 ]

hexyldog

进制转换能有什么公式啊....奇怪。

hanliu2008

都是些大牛

nhuczp

我晕！！

只有一个1哪么就判断是2多少次方不就完啦！如果是2的0次方就是0bit!!