计算二进制数中1的个数Word文档下载推荐.docx
- 文档编号:8689502
- 上传时间:2023-05-12
- 格式:DOCX
- 页数:16
- 大小:21.43KB
计算二进制数中1的个数Word文档下载推荐.docx
《计算二进制数中1的个数Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《计算二进制数中1的个数Word文档下载推荐.docx(16页珍藏版)》请在冰点文库上搜索。
returnx&
0x0000003F;
}
其它:
intpop3(unsignedintx)//?
unsignedintn;
//每三位计算1数目
n=(x>
033333333333;
x=x-n;
n=(n>
3))&
030707070707;
//相邻的3位字段相加,形成6位字段和0
x=x%63;
//将各个6位字段相加0
returnx;
intpop4(unsignedintx)//?
unsignedintn;
//每四位计算1数目
n=(x>
0x77777777;
x=x-n;
x=(x+(x>
//四位和变成八位和
x=x*01010101;
//将四个字节相加,和放在高阶字节上
returnx>
24;
//稀疏字的1位计数法
intpop(unsignedintx)
intn=0;
while(x!
=0)
++n;
x=x&
(x-1);
returnn;
//查表法
staticchartable[256]={0,1,1,......,7,7,8};
returntable[x&
0xFF]+table[(x>
0xFF]
+table[(x>
24)];
}0
5.2字的奇偶性
1.计算1位的个数,然后由结果的最右侧位决定
2.由r<
-&
oplus;
(x>
i)(0<
=i<
n),结果由r的最右侧位决定
y=x^(x>
1)
y=y^(y>
2)
4)
8)
16)
若将右移位变成左移位,则x的奇偶性出现在y的最左侧位,而y的第i位给出x从这一位到最右侧位奇偶性
3.x=x^(x>
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;
8;
=0){n-=8;
if(x<
=0x0000FFFF)//if((x&
0xFFFF0000)==0)
4;
=0){n-=4;
{
2;
=0){n-=2;
n+=16;
x=x<
<
1;
=0)return(n-2);
}
return(n-x);
=0x00FFFFFF)//if((x&
0xFF000000)==0)
//n=32;
c=16;
//do{
n+=8;
//
c;
=0){n-=c;
}
c=c>
=0x0FFFFFFF)
//}while(c!
=0);
//return(n-x);
n+=4;
}
intnlz3(intx)
=0x3FFFFFFF)
inty=x,n=0;
n+=2;
L:
0)returnn;
if(y==0)return(32-n);
=0x7FFFFFFF)
n+=1;
}
y=y>
gotoL:
intnlz4(unsignedintx)
return-1;
x=x|(x>
1);
2);
4);
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&
0x0000FFFF)==0){n+=16;
x=x>
0x000000FF)==0){n+=8;
0x0000000F)==0){n+=4;
0x00000003)==0){n+=2;
returnn-(x&
1);
第六章字搜索
6.1寻找第一个0字节
intzbytel(unsignedintx)//最左0字节
if((x>
24)==0)return0;
0x00FF0000)==0)return1;
0x0000FF00)==0)return2;
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
15)^3;
(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分别对应于谓词&
ldquo;
第i字节非零&
rdquo;
,则zbytel(x)=a+ab+abc+abcd
y=(x&
y=y|x;
//leading1onnonzerobytes
a=y>
31;
b=(y>
23)&
a;
c=(y>
15)&
b;
d=(y>
7)&
returna+b+c+d;
另外为了搜索一个字中第一个4位、随后12位或最后16位是否有0值,可以用0x77FF7FFF取代该方法中的掩码
intzbyter(unsignedintx)//最右0字节
intn=ntz(y)>
//intn=(32-nlz(~y&
(y-1)))>
推广:
(1)搜索等于任意给定值的字节:
对变量x和给定值进行异或,再搜索x中的0字节;
例如为了搜索x中的ASCII空格(0x20),搜索x^0x20202020中的0字节;
同样为了搜索两个字x和y中相等字节的位置,可以搜索x^y中的0字节
(2)搜索给定范围内的值()
寻找0到9之间值得最左侧字节的下标:
0x7F7F7F7F)+0x76767676;
n=nlz(y)>
寻找字中第一个大写字母(0x41~0x5A):
d=(x|0x80808080)-0x41414141;
d=~((x|0x7F7F7F7F)^d);
y=(d&
0x7F7F7F7F)+0x66666666;
y=~(y|d|0x7F7F7F7F);
6.2寻找第一个给定长度或更长的1位串
intffstr1(unsignedintx,intn)
intk,p=0;
while(x!
=0){
k=nlz(x);
k;
p+=k;
k=nlz(~x);
if(k>
=n)
returnp;
return32;
intffstr2(unsignedntx,intn)
ints;
while(n>
s=n>
(x<
s);
n=n-s;
}
returnnlz(x);
例如计算一个32位字中搜索长度>
=8的连续1位串
x=x&
(x<
//顺序可以颠倒
n=nlz(x);
第7章位与字节的重排列
7.1位与字节的反转
if(k&
1)x=(x&
0x55555555)<
1|(x&
0xAAAAAAAA)>
2)x=(x&
0x33333333)<
2|(x&
0xCCCCCCCC)>
4)x=(x&
0x0F0F0F0F)<
4|(x&
0xF0F0F0F0)>
8)x=(x&
0x00FF00FF)<
8|(x&
0xFF00FF00)>
16)x=(x&
0x0000FFFF)<
16|(x&
0xFFFF0000)>
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)&
2)|x)&
0x33333333;
1)|x)&
0x55555555;
将0000000000000000abcdefghijklmnop变为0a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p
其逆过程为:
x=((x>
0x00FF00FF;
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&
2|(a3&
b1=(a0&
4)<
1|(a1&
4)|(a2&
4)>
1|(a3&
b2=(a0&
2)<
2|(a1&
2)|(a3&
2)>
b4=(a0&
1)<
3|(a1&
2|(a2&
一种好的编码:
m=m^(m<
j),j的取值依次是16、8、4、2和1,而m的取值依次是:
0x0000FFFF、0x00FF00FF、0x0F0F0F0F、0x33333333、0x55555555
voidtranspose32(unsignedintA[32]){
//32*32矩阵转换
intj,k,m,t;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算 二进制 个数