下面的結(jié)論都是基于用補碼表示負數(shù)的計算機平臺
1
void main(unsigned int x)
2
{
3
//判斷無符號整數(shù)x是否是2的冪
4 if(x&(x-1))//若一個數(shù)是2的冪，則除最高位為1外，其余位均為0(二進制表示，下同)
5 printf("False\n");
6 else
7 printf("True\n");
8
9 //判斷一個無符號整數(shù)是否為2^n-1的形式(原理同上)
10 if(x&(x+1))//若為2^n-1，則低位全為1
11 printf("False\n");
12 else
13 printf("True\n");
14
15 //整數(shù)能被最大的2的冪(?)整除 : 析出最右側(cè)為1的位
16 //e.g.: 100->4
17 printf("%d\n",x&(-x));//將其余位置0
18
19 //析出最右側(cè)為0的位(原理同上)
20 //e.g.:111b->1000b, 10->1
21 printf("%d\n",~x&(x+1));//將該位置1，其余位置0
22
23 //識別后綴0的掩碼(將右側(cè)連續(xù)的0位置1，其余各位置0)
24 //e.g.:1100b->0011b
25 printf("%d\n", ~x&(x-1)); //或
26 printf("%d\n", ~(x|-x)); //或
27 printf("%d\n", (x&-x)-1);
28
29 //識別最右側(cè)的1未和后綴0的掩碼(將最右側(cè)的1位保留，并將其后面所有的0位置1)
30 //e.g.:1100b->0111b
31 printf("%d\n", x^(x-1));
32
33 //向右傳播最右側(cè)的1位
34 //e.g.:1100b->1111b
35 printf("%d\n", x|(x-1));
36
37 //將最右側(cè)連續(xù)的1位置0
38 //e.g.:10110b->10000
39 printf("%d\n", ((x|(x-1))+1)&x);
40
}
void main(unsigned int x)2
{ 
3
//判斷無符號整數(shù)x是否是2的冪 4
if(x&(x-1))//若一個數(shù)是2的冪，則除最高位為1外，其余位均為0(二進制表示，下同)5
printf("False\n");6
else7
printf("True\n");8
9
//判斷一個無符號整數(shù)是否為2^n-1的形式(原理同上) 10
if(x&(x+1))//若為2^n-1，則低位全為1 11
printf("False\n");12
else13
printf("True\n"); 14
15
//整數(shù)能被最大的2的冪(?)整除 : 析出最右側(cè)為1的位16
//e.g.: 100->417
printf("%d\n",x&(-x));//將其余位置0 18
19
//析出最右側(cè)為0的位(原理同上) 20
//e.g.:111b->1000b, 10->121
printf("%d\n",~x&(x+1));//將該位置1，其余位置022
23
//識別后綴0的掩碼(將右側(cè)連續(xù)的0位置1，其余各位置0)24
//e.g.:1100b->0011b25
printf("%d\n", ~x&(x-1)); //或 26
printf("%d\n", ~(x|-x)); //或 27
printf("%d\n", (x&-x)-1);28
29
//識別最右側(cè)的1未和后綴0的掩碼(將最右側(cè)的1位保留，并將其后面所有的0位置1) 30
//e.g.:1100b->0111b31
printf("%d\n", x^(x-1)); 32
33
//向右傳播最右側(cè)的1位 34
//e.g.:1100b->1111b35
printf("%d\n", x|(x-1));36
37
//將最右側(cè)連續(xù)的1位置038
//e.g.:10110b->1000039
printf("%d\n", ((x|(x-1))+1)&x); 40
}計算x中有多少個為1的位：
1int Count1(int x)
2{
3 int n = 0;
4 while(x)
5
{
6 n++;
7 x&=x-1;
8
}
9 return n;
10}
int Count1(int x)2
{3
int n = 0;4
while(x)5
{
6
n++;7
x&=x-1;8
}9
return n;10
}獲取下一個具有同樣數(shù)量的1位的更大的數(shù)；應用：在用位串表示集合的子集時
1unsigned snoob(unsigned x)
2{
3 unsigned smallest, ripple, ones;//e.g.: x=XXX0 1111 0000
4 smallest = x & -x; // 0000 0001 0000
5 ripple = x + smallest; // XXX1 0000 0000
6 ones = x ^ ripple; // 0001 1111 0000
7 ones = (ones >> 2) / smallest; // 0000 0000 0111
8 return ripple | ones; // XXX1 0000 0111
9}
unsigned snoob(unsigned x)2
{3
unsigned smallest, ripple, ones;//e.g.: x=XXX0 1111 00004
smallest = x & -x; // 0000 0001 00005
ripple = x + smallest; // XXX1 0000 00006
ones = x ^ ripple; // 0001 1111 00007
ones = (ones >> 2) / smallest; // 0000 0000 01118
return ripple | ones; // XXX1 0000 01119
}
浙公網(wǎng)安備 33010602011771號