按位運算相關算法筆記

1. 前言

首先，在記憶體中，數都以反碼表示，示例如下：

• 正數：+1：0,000，0001
• 負數：-1：1,111，1111

關于移位運算移，它包括循環移位、邏輯移位和算數移位（帶符号），C語言中，移位運算方式與具體的C語言編譯器有關，通常實作中，采用算數移位，即左移補0，右移運算補符号位：

• 無符号數：右移補0
• 有符号數：右移補符号位1

2. 基本位運算

位運算符	意義	特點	用處
&	and	按位與	與1不變 與0變0	取位操作
|	or	按位或	或0不變 或1變1	無條件指派
^	xor	按位異或	異或0不變 異或1取反	取反操作
~	not	全取反
<<	shl	左移補0
>>	shr	右移補0

其他運算的位實作

絕對值：求得原碼并将符号取反

1. 取的符号位：a>>31(正數：0, 負數：-1)
2. x^(x>>31)-(x>>31)： x>0時，x^0-0 = |x|； x<0時，x^(-1)+1 = |x|

二進制快速求幂：a^11 = a(20 + 2^1 + 2^3)

對2的幂次取模：x&y取出x和y二進制位1的所有位。x^y>>1取出x,y隻有一個二進制位1的并除以2

3. 基本位操作

3.1. 對數操作以及and、or、xor按位運算特性

操作	變化或特性
-x	0,110→1,010
x-1	0,100→0,011
x+1	0,011→0,100
	與1不變 與0變0
	或0不變 或1變1

3.2. 基本操作

操作含義	示例	運算
最低位 1 保留，其餘清0	0,110 and 1,010 = 0,010	x and (-x)
最低位 1 右置0，左置1	0,110 or 1,010 = 1,110	x or (-x)
最低位 1 且右置0，左置1	0,110 xor 1,010 = 1,100	x xor (-x)
最低位 1 且右 -- 置 0	0,100 and 0,011 = 0,000	x and (x-1)
最低位 1 且右 -- 置 1	0,100 or 0,011 = 0,111	x or (x-1)
最低位 1 且右 -- 置 1，左置0	0,100 xor 0,011 = 0,111	x xor (x-1)
最低位 0 且右 -- 置 0	0,011 and 0,100 = 0,000	x and (x+1)
最低位 0 且右 -- 置 1	0,011 or 0,100 = 0,111	x or (x+1)
最低位 0 且右 -- 置 1，左置0	0,011 xor 0,100 = 0,111	x xor (x+1)

3.3基本操作應用示例

取右側連續的 1 (100101111->1111) ：(x xor (x+1)) shr 1

取第一個1的右側 (100101000->1000) ：(x xor (x-1)) and x

4. 二進制分治

1. 二進制中的 1 有奇數個還是偶數個

8位整數為例：奇數個結果為1，偶數個結果為0

x=x xor (x shr 1);
x=x xor (x shr 2); 
x=x xor (x shr 4); 
           

其中右起第 i 位上的數表示原數中第 i 和 i+1 位上有奇數個 1 還是偶數個 1

2. 計算二進制中的 1 的個數

以8位整數為例：經過下面s三次指派後，x 的值就是原數的二進制表示中數字 1 的個數

x = (x and 0101 0101B ) + ((x shr 1) and 0101 0101B);  //截取并将相鄰兩位加起來，得到裡面的1的個數
x = (x and 0011 0011B) + ((x shr 2) and 0011 0011B);  //繼續相加
x = (x and 0000 1111B) + ((x shr 4) and 0000 1111B);  //繼續相加
           

3. 将整數A轉換為B，需要改變多少個bit位：計算A異或B之後這個數中1的個數

4. 二進制逆序

x = (x and 0x55555555) << 1  or  (x and 0xAAAAAAAA) shr 1; 
	x = (x and 0x33333333) << 2  or  (x and 0xCCCCCCCC) shr 2; 
	x = (x and 0x0F0F0F0F) << 4  or  (x and 0xF0F0F0F0) shr 4; 
	x = (x and 0x00FF00FF) << 8  or  (x and 0xFF00FF00) shr 8; 
	x = (x and 0x0000FFFF) << 16  or  (x and 0xFFFF0000) shr 16;
           

5. 其他運用

int calc(int n)
	{
	    n |= n>>1;
	    n |= n>>2;
	    n |= n>>4;
	    n |= n>>8;
	    n |= n>>16;
	    return n+1;
	}