分类： C/C++
2009-11-16 19:02:57
有些信息在存储时，并不需要占用一个完整的字节， 而只需占几个或一个二进制位。例如在存放一个开关量时，只有0和1
两种状态，用一位二进制位即可。为了节省存储空间，并使处理简便，Ｃ语言又提供了一种数据结构，称为“位域”或“位段”。所谓“位域”是把一个字节中的二进制位划分为几个不同的区域，并说明每个区域的位数。每个域有一个域名，允许在程序中按域名进行操作。 这样就可以把几个不同的对象用一个字节的二进
制位域来表示。
一、位域的定义和位域变量的说明位域定义与结构定义相仿，其形式为：
struct 位域结构名
{ 位域列表 };
其中位域列表的形式为： 类型说明符 位域名：位域长度
例如：
struct bs
{
int a:8;
int b:2;
int c:6;
};
位域变量的说明与结构变量说明的方式相同。 可采用先定义后说明，同时定义说明或者直接说明这三种方式。例如：
struct bs
{
int a:8;
int b:2;
int c:6;
}data;
说明data为bs变量，共占两个字节。其中位域a占8位，位域b占2位，位域c占6位。对于位域的定义尚有以下几点说明：
1. 一个位域必须存储在同一个字节中，不能跨两个字节。如一个字节所剩空间不够存放另一位域时，应从下一单元起存放该位域。也可以有意使某位域从下一单元开始。
例如：
struct bs
{
unsigned a:4
unsigned :0 /*空域*/
unsigned b:4 /*从下一单元开始存放*/
unsigned c:4
}
在这个位域定义中，a占第一字节的4位，后4位填0表示不使用，b从第二字节开始，占用4位，c占用4位。
2. 由于位域不允许跨两个字节，因此位域的长度不能大于一个字节的长度，也就是说不能超过8位二进位。
3. 位域可以无位域名，这时它只用来作填充或调整位置。无名的位域是不能使用的。例如：
struct k
{
int a:1
int :2 /*该2位不能使用*/
int b:3
int c:2
};
从以上分析可以看出，位域在本质上就是一种结构类型， 不过其成员是按二进位分配的。
如果结构体中含有位域(bit-field)，那么VC中准则是：
1) 如果相邻位域字段的类型相同，且其位宽之和小于类型的sizeof大小，则后面的字段将紧邻前一个字段存储，直到不能容纳为止；
2) 如果相邻位域字段的类型相同，但其位宽之和大于类型的sizeof大小，则后面的字段将从新的存储单元开始，其偏移量为其类型大小的整数倍；
3) 如果相邻的位域字段的类型不同，则各编译器的具体实现有差异，VC6采取不压缩方式（不同位域字段存放在不同的位域类型字节中），Dev-C++和GCC都采取压缩方式；
系统会先为结构体成员按照对齐方式分配空间和填塞（padding）,然后对变量进行位域操作。
理解了吗？试着做下面几个例子（VS 2003）。
#pragma pack(1)
struct s4{
char a:4;
short b:4;
short c:4;
long d;
};
输出S4 sizeof:7
#pragma pack(1)
struct s4{
char a:4;
short b:4;
char c:4;
long d;
};
输出S4 sizeof:8
#pragma pack(2)
struct s4{
char a:4;
short b:4;
char c:4;
long d;
};
输出S4 sizeof:10
#pragma pack(2)
struct s4{
char a:4;
short b:4;
short c:4;
long d;
};
输出S4 sizeof:8
－－－－－－－－－－－－－－－－－－－－
#include
#include
typedef struct{
//unsigned int a:2;
//unsigned int b:2;
//unsigned int c:1;
int a:2;
int b:2;
int c:1;
}test;
int main (int argc, char *argv[])
{
test t;
t.a = 1;
t.b = 3;
t.c = 1;
printf("%d\n", t.a);
printf("%d\n", t.b);
printf("%d\n", t.c);
printf("%d\n", sizeof(test));
return 0;
}
gcc: 1 -1 -1 4
-----------------------------------------
检测一个无符号数是不为2^n-1(^为幂)：
x&(x+1)
将最右侧0位改为1位： x
| (x+1)
二进制补码运算公式：
-x = ~x + 1 =
~(x-1)
~x = -x-1
-(~x) = x+1
~(-x)
= x-1
x+y = x - ~y - 1 = (x|y)+(x&y)
x-y
= x + ~y + 1 = (x|~y)-(~x&y)
x^y =
(x|y)-(x&y)
x|y = (x&~y)+y
x&y =
(~x|y)-~x
x==y: ~(x-y|y-x)
x!=y:
x-y|y-x
x< y: (x-y)^((x^y)&((x-y)^x))
x<=y:
(x|~y)&((x^y)|~(y-x))
x< y:
(~x&y)|((~x|y)&(x-y))//无符号x,y比较
x<=y:
(~x|y)&((x^y)|~(y-x))//无符号x,y比较
使用位运算的无分支代
码：
计算绝对值
int abs( int x )
{
int
y ;
y = x >> 31 ;
return (x^y)-y
;//or: (x+y)^y
}
符号函数：sign(x) = -1,
x<0; 0, x == 0 ; 1, x > 0
int
sign(int x)
{
return (x>>31) |
(unsigned(-x))>>31 ;//x=-2^31时失败(^为幂)
}
三
值比较：cmp(x,y) = -1, x
int
cmp( int x, int y )
{
return
(x>y)-(x-y) ;
}
doz=x-y, x>=y; 0,
x
{
int
d ;
d = x-y ;
return d &
((~(d^((x^y)&(d^x))))>>31) ;
}
int
max(int x, int y )
{
int m ;
m
= (x-y)>>31 ;
return y & m | x
& ~m ;
}
不使用第三方交换x,y:
1.x ^=
y ; y ^= x ; x ^= y ;
2.x = x+y ; y
= x-y ; x = x-y ;
3.x = x-y ; y = y+x
; x = y-x ;
4.x = y-x ; x = y-x ; x
= x+y ;
双值交换:x = a, x==b; b,
x==a//常规编码为x = x==a ? b :a ;
1.x = a+b-x ;
2.x
= a^b^x ;
下舍入到2的k次方的倍数:
1.x &
((-1)<
1. t = (1<
位计数,统
计1位的数量：
1.
int pop(unsigned x)
{
x
= x-((x>>1)&0x55555555) ;
x =
(x&0x33333333) + ((x>>2) & 0x33333333 ) ;
x
= (x+(x>>4)) & 0x0f0f0f0f ;
x = x +
(x>>8) ;
x = x + (x>>16) ;
return
x & 0x0000003f ;
}
2.
int
pop(unsigned x) {
static char table[256] = {
0,1,1,2, 1,2,2,3, ...., 6,7,7,8 } ;
return
table[x&0xff]+table[(x>>8)&0xff]+table[(x>>16)&0xff]+table[(x>>24)]
;
}
奇偶性计算:
x = x ^ (
x>>1 ) ;
x = x ^ ( x>>2 ) ;
x
= x ^ ( x>>4 ) ;
x = x ^ (
x>>8 ) ;
x = x ^ ( x>>16 ) ;
结
果中位于x最低位，对无符号x,结果的第i位是原数第i位到最左侧位的奇偶性
位反转：
unsigned
rev(unsigned x)
{
x = (x & 0x55555555)
<< 1 | (x>>1) & 0x55555555 ;
x =
(x & 0x33333333) << 2 | (x>>2) &
0x33333333 ;
x = (x & 0x0f0f0f0f) << 4
| (x>>4) & 0x0f0f0f0f ;
x =
(x<<24) | ((x&0xff00)<<8) | ((x>>8)
& 0xff00) | (x>>24) ;
return x ;
}
递增位反转后的数：
unsigned inc_r(unsigned x)
{
unsigned m = 0x80000000 ;
x ^= m ;
if(
(int)x >= 0 )
do { m >>= 1 ; x
^= m ; } while( x < m ) ;
return x ;
}
混选位：
abcd efgh ijkl mnop ABCD EFGH
IJKL MNOP->aAbB cCdD eEfF gGhH iIjJ kKlL mMnN oOpP
unsigned
ps(unsigned x)
{
unsigned t ;
t =
(x ^ (x>>8)) & 0x0000ff00; x = x ^ t ^
(t<<8) ;
t = (x ^ (x>>4)) &
0x00f000f0; x = x ^ t ^ (t<<4) ;
t =
(x ^ (x>>2)) & 0x0c0c0c0c; x = x ^ t ^
(t<<2) ;
t = (x ^ (x>>1)) &
0x22222222; x = x ^ t ^ (t<<1) ;
return
x ;
}
位压缩：
选择并右移字x中对应于掩码m的1位的位,
如：compress(abcdefgh,01010101)=0000bdfh
compress_left(x,m)操作与此类似，
但结果位在左边: bdfh0000.
unsigned compress(unsigned x,
unsigned m)
{
unsigned mk, mp, mv, t ;
int
i ;
x &= m ;
mk = ~m
<< 1 ;
for( i = 0 ; i < 5 ; ++i
) {
mp = mk ^ ( mk << 1) ;
mp
^= ( mp << 2 ) ;
mp ^= ( mp
<< 4 ) ;
mp ^= ( mp << 8 ) ;
mp
^= ( mp << 16 ) ;
mv = mp & m
;
m = m ^ mv | (mv >> (1<
x = x ^ t |
( t >> ( 1<
}
return x ;
}
位
置换：
用32个5位数表示从最低位开始的位的目标位置，结果是一个32*5的位矩阵，
将该矩阵沿次对角线转置后用5
个32位字p[5]存放。
SAG(x,m) = compress_left(x,m) |
compress(x,~m) ;
准备工作：
void init( unsigned *p
) {
p[1] = SAG( p[1], p[0] ) ;
p[2] =
SAG( SAG( p[2], p[0]), p[1] ) ;
p[3] = SAG(
SAG( SAG( p[3], p[0] ), p[1]), p[2] ) ;
p[4]
= SAG( SAG( SAG( SAG( p[4], p[0] ), p[1]) ,p[2]),
p[3] ) ;
}
实际置换：
int rep( unsigned x
) {
x = SAG(x,p[0]);
x = SAG(x,p[1]);
x
= SAG(x,p[2]);
x = SAG(x,p[3]);
x =
SAG(x,p[4]);
return x ;
}
二进制码到GRAY码
的转换:
unsigned B2G(unsigned B )
{
return
B ^ (B>>1) ;
}
GRAY码到二进制码:
unsigned
G2B(unsigned G)
{
unsigned B ;
B =
G ^ (G>>1) ;
B = G ^ (G>>2) ;
B
= G ^ (G>>4) ;
B = G ^ (G>>8) ;
B = G ^ (G>>16) ;
return B ;
}
找出最左0字节的位置:
int zbytel( unsigned x )
{
static cahr table[16] = { 4,3,2,2, 1,1,1,1,
0,0,0,0, 0,0,0,0 } ;
unsigned y ;
y =
(x&0x7f7f7f7f) + 0x7f7f7f7f ;
y =
~(y|x|0x7f7f7f7f) ;
return table[y*0x00204081 >>
28] ;//乘法可用移位和加完成
