算法实现

int ffs1(int i)
{static const unsigned char table[] = {0, 1, 2, 0, 3, 0, 0, 0, 4};unsigned int a, b;unsigned int x = i & -i;a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24);b = x >> a;if (b > 8) { b /= 16; a += 4;}return table[b] + a;
}

改编自libc string/ffs.c，原代码使用太多的table内存。当然这只是纯软件的实现方法，在特定应减少还是直接调用libc的ffs函数就好，会有相应的硬件实现。

测试程序

#include <time.h>
#include <stdlib.h>
#include <stdio.h>int ffs1(int i)
{static const unsigned char table[] = {0, 1, 2, 0, 3, 0, 0, 0, 4};unsigned int a, b;unsigned int x = i & -i;a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24);b = x >> a;if (b > 8) { b /= 16; a += 4;}return table[b] + a;
}int ffs2(int i)
{int x = i;int pos = 1;if (!i) return 0;while (!(x & 1)) {pos++;x >>= 1;}return pos;
}#define NUM 1000int main()
{int test[NUM];int err = 0;srand(time(NULL));  for (int i = 0; i < NUM; i++)test[i] = (unsigned int)rand() << rand();  for (int i=0; i<NUM; i++)if (ffs1(test[i]) != ffs2(test[i])) {printf("fail: %x\n", test[i]);err++;}if (!err) printf("success!\n");return 0;
}

扩展

拷贝libc实现64位

int ffsll1 (long long int i)
{unsigned long long int x = i & -i;if (x <= 0xffffffff)return ffs1(i);elsereturn 32 + ffs1(i >> 32);
}