C:位運算

1.負數表示-二類補數(twos complement)

一般使用二類補數表示負數,最左邊一位為符號位.

將一個十進制負數轉化為二進制符號數時,首先給這個數加1,然後取絕對值,再將其轉換為二進制,最後對這個二進制求補.

[1]-5

[2]-4

[3]4

[4]0000 0100

[5]1111 1011

將一個負數從二進制轉換為十進制,首先對其所有位求補,然後將結果轉換為十進制,再改變其符號,最後再減1.

[1]1111 1011

[2]0000 0100

[3]4

[4]-4

[5]-5

使用二類補數表示數字時,用n位可存儲的最大正數是2n-1-1,用n位可存儲的最小負數-2n-1.

假設整數占32位(4字節),此時可存儲的最大正數231-1,最小負數-231,而如果是無符號整數,即unsigned int,其表示范圍為0至232-1.

2.按位與和按位或

按位與經常用於屏蔽一個數中的某些位,

word &= 0x1//除最右邊4位外,其余位清零

按位或經常用於將某些位設定為1

word |= 0x1//將最右邊4位設定為1

3.異或運算

異或運算可以交換兩個值而不需要使用臨時變量.

/*exchange two integer values*/
void swap(int　* a, int　* b)
{
　　*a ^= *b;
　　*b ^= *a;
　　*a ^= *b;
}

如果某數與1進行異或運算,可以達到取反的效果,0^1=1,1^1=0.

這裡假設機器的整型數長度為32位,對整數0的31位取反,得到最大整數.

int main()
{
　　int a=0;
　　printf("%i,%i",a,a ^ 0x7fffffff);
　　return 0;
}

4.幾個經典的位運算函數

4.1求當前機器無符號整型最大長度

/*the max length of unsigned int*/
int　int_size ()
{
　　unsigned int　bits;
　　int size = 0;
　　bits = ~0;
　　while ( bits ) {
　　　 ++size;
　　　 bits >>= 1;
　　}
　　return size;
}

4.2移位運算

/*a bit mover for unsigned int
　if n > 0 move left for n bits,else move right*/
unsigned int bit_shift (unsigned int value,int n)
{
　　int intsize=int_size();　　 /*the length of unsigned int*/
　　if(n>0 && n< intsize)　　　 /*move left*/
　　　value<<=n;
　　else if (n<0 && n> -intsize)　/*move right*/
　　　value>>=-n;
　　else
　　　value=0;
　　return value;
}

4.3循環移位運算

/*a bit rotate mover for unsigned int
　if n > 0 move left for n bits,else move right*/
unsigned int bit_rotate (unsigned int value, int n)
{
　　unsigned int result,bits,intsize;
　　intsize=int_size();　/*the length of unsigned int*/
　　if(n > 0)
　　　n=n % intsize;
　　else
　　　n=-(-n % intsize);
　　if(n==0)
　　　result=value;
　　else if(n >0 ){　　　　　　　 /*move left*/
　　　　bits=value >> (intsize-n);/*bits should be in the rightest*/
　　　　result=value << n|bits;
　　}else{　　　　　　　　　　　/*move right*/
　　　　n=-n;
　　　　bits=value << (intsize-n);/*bits should be in the leftest*/
　　　　result=value >> n|bits;
　　}
　　return result;
}

4.4返回無符號整型數value中從右起第p位的值

/* get bit No.p(from right) of value to see if it is on */
int　bit_get (unsigned int　value, int　n)
{
　　int intsize=int_size();　　　 /*the length of unsigned int*/
　　if ( p < 0　|| p > intsize-1 )/*out of range*/
　　　 return　0;
　　if ( (value >> p) & 1 )
　　　 return 1;
　　else
　　　 return 0;
}

4.5 將無符號整型數value中從右起的第p位置1

/* set bit No.p(from right) of value on */
unsigned int　bit_set (unsigned int value, int　p)
{
　　int intsize=int_size();　　　 /*the length of unsigned int*/
　　if ( p < 0　|| p > intsize-1 )/*out of range*/
　　　 return　0;
　　return　value | (1 << p);
}

4.6返回無符號整型數value中從第p位(右起)向右n位的值

[1]~(~0 << n)表示最右邊n位全為1;

[2]value >> (p+1-n)表示將目標位字段移至最右端;

/*get n bits of value at position p(from right) */
unsigned bits_get (unsigned int value, int p, int n)
{
　　 int intsize=int_size();　/*the length of unsigned int*/
　　 if ( n < 0　|| p < 0　||　p + n > intsize )
　　　 return　0;
　　return(value >> (p+1-n)) & ~(~0 << n);
}

4.7將無符號整型數value中從第p位(右起)向右n位設置為y最右邊n位的值

[1]~(~0 << n)表示最右邊n位全為1;

[2](~(~0 << n) << (p+1-n)表示將這n個1位左移至位置p;

[3]~(~(~0 << n) << (p+1-n))表示將從位置p開始的n位設置零,其余位設置一;

[4]unsigned tar=bits_get(y,n-1,n);取出y的低n位;

/*set n bits of value at position p(from right) with bits of y*/
unsigned bits_set (unsigned value, int p, int n, unsigned int y)
{
　　int intsize=int_size();　/*the length of unsigned int*/
　　if ( n < 0　||　p < 0　||　p + n > intsize )
　　　 return　0;
　　unsigned tar=bits_get(y,n-1,n);
　　return (value & ~(~(~0 << n) << (p+1-n))) | tar;
}

本文出自 “子 孑” 博客，請務必保留此出處http://zhangjunhd.blog.51cto.com/113473/52734