我的C实践(8)：字搜索

  字搜索就搜索一个数中具有某些特征的位。实现如下：
/* wsearch.c：字搜索 */
/* 从左边寻找第一个0字节：第0(1,2,3)个字节是0时，返回0(1,2,3)，否则返回4 */
int zbytel(unsigned x){
if((x>>24)==0) return 0;
else if((x & 0x00ff0000)==0) return 1;
else if((x & 0x0000ff00)==0) return 2;
else if((x & 0x000000ff)==0) return 3;
else return 4;
}
/* 方案2：无分支代码，用到了nlz指令 */
int zbytel_2(unsigned x){
int nlz(unsigned); /* 前向声明 */
unsigned y;
y=(x & 0x7f7f7f7f)+0x7f7f7f7f; /* 把0字节变成0x7f，非0字节最高位变成1 */
y=~(y | x | 0x7f7f7f7f); /* 把0字节变成0x80，非0字节变成0x00 */
return nlz(y)>>3; /* 第0(1,2,3)个字节是0时，y的前导有0(8,16,24)个0，故返回0(1,2,3)，否则返回4 */
}
/* 从左边寻找第一个长为n的连续1位串，返回其位置（从0开始编号） */
int ffstr1(unsigned x, int n){
int nlz(unsigned); /* 前向声明 */
int k,p;
p=0; /* 初始化返回的位置 */
while(x!=0){
k=nlz(x);
x=x<<k; /* 跳过前导的0 */
p=p+k;
k=nlz(~x); /* 计算前导1的个数 */
if(k>=n)
return p; /* 若前导1的个数足够，则找到，直接返回其位置 */
x=x<<k; /* 否则连续的1不足n个，跳过它们，继续向前找 */
p=p+k;
}
return 32; /* 没找到则返回32 */
}
/* 计算前导0的个数 */
int nlz(unsigned x){
int n;
if(x==0) return (32);
n=1;
/* 用分治策略 */
if((x>>16)==0){ /* x<=0x0000ffff时 */
n=n+16;
x=x<<16; /* 移除前导的16个0 */
}
if((x>>24)==0){ /* x<=0x00ffffff时 */
n=n+8;
x=x<<8; /* 移除前导的8个0 */
}
if((x>>28)==0){ /* x<=0x0fffffff时 */
n=n+4;
x=x<<4; /* 移除前导的4个0 */
}
if((x>>30)==0){ /* x<=0x3fffffff时 */
n=n+2;
x=x<<2; /* 移除前导的2个0 */
}
return n-(x>>31); /* 注意n初始时为1，如果移除前导0后的x最高位为0，则n恰好计算了这个0；
如果最高位为1，则没有额外的前导0，n必须要减去多出的1 */
}