计算二进制数中1的个数.docx
- 文档编号:8110574
- 上传时间:2023-05-12
- 格式:DOCX
- 页数:16
- 大小:21.43KB
计算二进制数中1的个数.docx
《计算二进制数中1的个数.docx》由会员分享,可在线阅读,更多相关《计算二进制数中1的个数.docx(16页珍藏版)》请在冰点文库上搜索。
计算二进制数中1的个数
0
0
0
0
0
0
0
0
第五章 位计数
5.11位计数
1.二分法:
x=(x&0x55555555)+((x>>1)&0x55555555)
x=(x&0x33333333)+((x>>2)&0x33333333)
x=(x&0x0F0F0F0F)+((x>>4)&0x0F0F0F0F)
x=(x&0x00FF00FF)+((x>>8)&0x00FF00FF)
x=(x&0x0000FFFF)+((x>>16)&0x0000FFFF)0
另外利用pop(x)=x-x/2-x/4-...-x/2^31(x/2^31=0,x为无符号整数)
intpop2(unsignedintx)
{
x=x-((x>>1)&0x55555555); //相当于x=(x&0x55555555)+((x>>1)&0x55555555)
x=(x&0x33333333)+((x>>2)&0x33333333);
x=(x+(x>>4))&0x0F0F0F0F; //相当于(x&0x0F0F0F0F)+((x>>4)&0x0F0F0F0F),无进位
x=x+(x>>8);
x=x+(x>>16);
returnx&0x0000003F;
}
其它:
intpop3(unsignedintx)//?
{
unsignedintn;
//每三位计算1数目
n=(x>>1)&033333333333;
x=x-n;
n=(n>>1)&033333333333;
x=x-n;
x=(x+(x>>3))&030707070707;//相邻的3位字段相加,形成6位字段和0
x=x%63;//将各个6位字段相加0
returnx;
}
intpop4(unsignedintx)//?
{
unsignedintn;
//每四位计算1数目
n=(x>>1)&0x77777777;
x=x-n;
n=(x>>1)&0x77777777;
x=x-n;
n=(x>>1)&0x77777777;
x=x-n;0
x=(x+(x>>4))&0x0F0F0F0F;//四位和变成八位和
x=x*01010101;//将四个字节相加,和放在高阶字节上
returnx>>24;
}
//稀疏字的1位计数法
intpop(unsignedintx)
{
intn=0;
while(x!
=0)
{
++n;
x=x&(x-1);
}
returnn;
}
//查表法
intpop(unsignedintx)
{
staticchartable[256]={0,1,1,......,7,7,8};
returntable[x&0xFF]+table[(x>>8)&0xFF]
+table[(x>>16)&0xFF]+table[(x>>24)];
}0
5.2字的奇偶性
1.计算1位的个数,然后由结果的最右侧位决定
2.由r<-⊕(x>>i)(0<=i y=x^(x>>1) y=y^(y>>2) y=y^(y>>4) y=y^(y>>8) y=y^(y>>16) 若将右移位变成左移位,则x的奇偶性出现在y的最左侧位,而y的第i位给出x从这一位到最右侧位奇偶性 3.x=x^(x>>1) x=(x^(x>>2))&0x11111111 x=x*0x11111111 //将各个四位数加到一起并把和放入到高阶十六进制位的数字中 p=(x>>28)&1 //p=1(odd)orp=0(even) 5.3前导0计数 intnlz1(unsignedintx) intnlz2(unsignedintx) { { intn=0; unsignedinty,n=32; if(x==0)return32; y=x>>16;if(y! =0){n-=16;x=y;} y=x>>8;if(y! =0){n-=8;x=y;} if(x<=0x0000FFFF)//if((x&0xFFFF0000)==0) y=x>>4;if(y! =0){n-=4;x=y;} { y=x>>2;if(y! =0){n-=2;x=y;} n+=16;x=x<<16; y=x>>1;if(y! =0)return(n-2); } return(n-x); if(x<=0x00FFFFFF)//if((x&0xFF000000)==0) //n=32;c=16; { //do{ n+=8;x=x<<8; // y=x>>c;if(y! =0){n-=c;x=y;} } // c=c>>1; if(x<=0x0FFFFFFF) //}while(c! =0); { //return(n-x); n+=4;x=x<<4; } } intnlz3(intx) if(x<=0x3FFFFFFF) { { inty=x,n=0; n+=2;x=x<<2; L: if(x<0)returnn; } if(y==0)return(32-n); if(x<=0x7FFFFFFF) n+=1; n+=1; x=x<<1; } y=y>>1; gotoL: intnlz4(unsignedintx) return-1; { } x=x|(x>>1); x=x|(x>>2); x=x|(x>>4); x=x|(x>>8); x=x|(x>>16); returnpop(~x);//见5.1节 } 与对数关系: (无符号整数x! =0)floor(log2(x))=31-nlz(x);ceiling(log2(x))=32-nlz(x-1)0 5.4后缀0计数 1.ntz(x)=32-nlz(~x&(x-1))=pop(~x&(x-1))=32-pop(x|-x) 2.二分法 intntz(unsignedintx) { intn=1; if(x==0)return32; if((x&0x0000FFFF)==0){n+=16;x=x>>16;} if((x&0x000000FF)==0){n+=8;x=x>>8;} if((x&0x0000000F)==0){n+=4;x=x>>4;} if((x&0x00000003)==0){n+=2;x=x>>2;} returnn-(x&1); }0 第六章字搜索 6.1寻找第一个0字节 intzbytel(unsignedintx)//最左0字节 { if((x>>24)==0)return0; if((x&0x00FF0000)==0)return1; if((x&0x0000FF00)==0)return2; if((x&0x000000FF)==0)return3; elsreturn4;//没有0字节 } intzbytel(unsignedintx)//将每个0字节变为0x80,每个非0字节变为0x00 { unsignedinty=(x&0x7F7F7F7F)+0x7F7F7F7F; y=~(y|x|0x7F7F7F7F);//leading1onzerobytes intn=nlz(y)>>3; /* (1)不用nlz指令的分支方法 if(y==0)return4; elseif(y>0x0000FFFF) return(y>>31)^1; else return(y>>15)^3; return-1; (2)查表法 //求对0x7F的余数,将原始值中最多的四个1位移动并压缩到最右侧4个位上 //0x80808080%127=15;0x80000000%127=8;0x00008080%127=3etc. staticchartable[16]={4,3,4,4,1,1,1,1,0,0,0,0,0,0,0,0}; returntable[y%127]; */ returnn; } 该方法一种有趣变形: 设a、b、c、d分别对应于谓词“第i字节非零”,则zbytel(x)=a+ab+abc+abcd y=(x&0x7F7F7F7F)+0x7F7F7F7F; y=y|x; //leading1onnonzerobytes a=y>>31; b=(y>>23)&a; c=(y>>15)&b; d=(y>>7)&c; returna+b+c+d; 另外为了搜索一个字中第一个4位、随后12位或最后16位是否有0值,可以用0x77FF7FFF取代该方法中的掩码 intzbyter(unsignedintx)//最右0字节 { unsignedinty=(x&0x7F7F7F7F)+0x7F7F7F7F; y=~(y|x|0x7F7F7F7F); intn=ntz(y)>>3; //intn=(32-nlz(~y&(y-1)))>>3; returnn; } 推广: (1)搜索等于任意给定值的字节: 对变量x和给定值进行异或,再搜索x中的0字节;例如为了搜索x中的ASCII空格(0x20),搜索x^0x20202020中的0字节;同样为了搜索两个字x和y中相等字节的位置,可以搜索x^y中的0字节 (2)搜索给定范围内的值() 寻找0到9之间值得最左侧字节的下标: y=(x&0x7F7F7F7F)+0x76767676;y=~(y|x|0x7F7F7F7F);n=nlz(y)>>3;0 寻找字中第一个大写字母(0x41~0x5A): d=(x|0x80808080)-0x41414141;d=~((x|0x7F7F7F7F)^d); y=(d&0x7F7F7F7F)+0x66666666;y=~(y|d|0x7F7F7F7F);n=nlz(y)>>3; 6.2寻找第一个给定长度或更长的1位串 intffstr1(unsignedintx,intn) { intk,p=0; while(x! =0){ k=nlz(x); x=x< p+=k; k=nlz(~x); if(k>=n) returnp; x=x< p+=k; } return32; } intffstr2(unsignedntx,intn) { ints; while(n>1) { s=n>>1; x=x&(x< n=n-s; } returnnlz(x); } 例如计算一个32位字中搜索长度>=8的连续1位串 x=x&(x<<1);x=x&(x<<2);x=x&(x<<4);//顺序可以颠倒 n=nlz(x);0 第7章位与字节的重排列 7.1位与字节的反转 if(k&1)x=(x&0x55555555)<<1|(x&0xAAAAAAAA)>>1; if(k&2)x=(x&0x33333333)<<2|(x&0xCCCCCCCC)>>2; if(k&4)x=(x&0x0F0F0F0F)<<4|(x&0xF0F0F0F0)>>4; if(k&8)x=(x&0x00FF00FF)<<8|(x&0xFF00FF00)>>8; if(k&16)x=(x&0x0000FFFF)<<16|(x&0xFFFF0000)>>16; k=31反转字中的位,例如: rev(0x01234567)=0xE6A2C480 k=24反转字中的字节,例如: rev(0x1234567)=0x67452301 k=16反转字中左右两个半字,例如: rev(0x1234567)=0x45670123 k=7反转每个字节中的位,例如: rev(0x1234567)=0x80C4A2E6 7.2混洗位 abcdefghijklmnopABCDEFGHIJKLMNOPx=(x&0x0000FF00)<<8|(x>>8)&0x0000FF00|x&0xFF0000FF abcdefghABCDEFGHijklmnopIJKLMNOPx=(x&0x00F000F0)<<4|(x>>4)&0x00F000F0|x&0xF00FF00F abcdABCDefghEFGHijklIJKLmnopMNOPx=(x&0x0C0C0C0C)<<2|(x>>2)&0x0C0C0C0C|x&0xC3C3C3C3 abABcdCDefEFghGHijIJklKLmnMNopOPx=(x&0x22222222)<<1|(x>>1)&0x22222222|x&0x99999999 aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpP外混洗结果 在上面序列前面加上x=(x>>16)|(x<<16)可得到AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPp内混洗结果 以相反顺序可以实现操作的逆顺序 另外针对字左半部所有位都为0的情况,可以通过 x=((x&0xFF00)<<8)|(x&0x00FF)); x=((x<<4)|x)&0x0F0F0F0F; x=((x<<2)|x)&0x33333333; x=((x<<1)|x)&0x55555555; 将0000000000000000abcdefghijklmnop变为0a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p 其逆过程为: x=((x>>1)|x)&0x33333333; x=((x>>2)|x)&0x0F0F0F0F; x=((x>>4)|x)&0x00FF00FF; x=((x>>8)|x)&0x0000FFFF; 7.3转置位矩阵 a0=0123 b0=048c a1=4567==>b1=159d a2=89ab b2=26ae a3=cdef b3=37bf 简单方法: b0=(a0&8)|(a1&8)>>1|(a2&8)>>2|(a3&8)>>3; b1=(a0&4)<<1|(a1&4)|(a2&4)>>1|(a3&4)>>2; b2=(a0&2)<<2|(a1&2)<<1|(a2&2)|(a3&2)>>1; b4=(a0&1)<<3|(a1&1)<<2|(a2&1)<<1|(a3&1); 一种好的编码: m=m^(m< 0x0000FFFF、0x00FF00FF、0x0F0F0F0F、0x33333333、0x55555555 voidtranspose32(unsignedintA[32]){ //32*32矩阵转换 intj,k,m,t;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算 二进制 个数