C語(yǔ)言位運(yùn)算總結(jié)位操作基礎(chǔ)基本的位操作符有與、或、異或、取反、左移、右移這6種，它們的運(yùn)算規(guī)則如下所示：
注意以下幾點(diǎn)：
位操作應(yīng)用
只要根據(jù)最未位是0還是1來(lái)決定，為0就是偶數(shù)，為1就是奇數(shù)。因此可以用if (a & 1 == 0)代替if (a % 2 == 0)來(lái)判斷a是不是偶數(shù)?？梢缘玫饺缦麓a：
可以這樣理解： 1）a^=b 即a=(a^b); 2）b^=a 即b=b^(a^b)，由于^運(yùn)算滿足交換律，b^(a^b)=b^b^a。由于一個(gè)數(shù)和自己異或的結(jié)果為0并且任何數(shù)與0異或都會(huì)不變的，所以此時(shí)b被賦上了a的值。 3）a^=b 就是a=a^b，由于前面二步可知a=(a^b)，b=a，所以a=a^b即a=(a^b)^a。故a會(huì)被賦上b的值。 再來(lái)個(gè)實(shí)例說(shuō)明下以加深印象。int a = 13, b = 6; a的二進(jìn)制為 13=8+4+1=1101(二進(jìn)制) b的二進(jìn)制為 6=4+2=110(二進(jìn)制) 第一步 a^=b a = 1101 ^ 110 = 1011; 第二步 b^=a b = 110 ^ 1011 = 1101;即b=13 第三步 a^=b a = 1011 ^ 1101 = 110;即a=5
變換符號(hào)就是正數(shù)變成負(fù)數(shù)，負(fù)數(shù)變成正數(shù)。可以利用求補(bǔ)碼的方法（按位取反+1）來(lái) 處理。 如對(duì)于-11和11，可以通過(guò)下面的變換方法將-11變成11 1111 0101(二進(jìn)制) –取反-> 0000 1010(二進(jìn)制) –加1-> 0000 1011(二進(jìn)制) 同樣可以這樣的將11變成-11 0000 1011(二進(jìn)制) –取反-> 0000 1010(二進(jìn)制) –加1-> 1111 0101(二進(jìn)制) 可以得到如下代碼：
對(duì)于任何數(shù)，與0異或都會(huì)保持不變，與-1即0xFFFFFFFF異或就相當(dāng)于取反,因此，a與i異或后再減i（因?yàn)閕為0或-1，所以減i即是要么加0要么加1）也可以得到絕對(duì)值因此可以得 到如下代碼：
給出一個(gè)32位的無(wú)符號(hào)整數(shù)。稱這個(gè)二進(jìn)制數(shù)的前16位為“高位”，后16位為“低位”。現(xiàn)在寫一程序?qū)⑺母叩臀唤粨Q。例如，數(shù)0x1234ABCD用二進(jìn)制表示為： 0001 0010 0011 0100 1010 1011 1100 1101 將它的高低位進(jìn)行交換，我們得到了一個(gè)新的二進(jìn)制數(shù)： 1010 1011 1100 1101 0001 0010 0011 0100 它即是0xABCD1234。 這個(gè)問(wèn)題用位操作解決起來(lái)非常方便，設(shè)x=0x1234ABCD由于x為無(wú)符號(hào)數(shù)，右移時(shí)會(huì)執(zhí)行邏輯右移即高位補(bǔ)0，因此x右移16位將得到0000 0000 0000 0000 0001 0010 0011 0100。而x左移8位將得到0000 0000 0000 0000 1010 1011 1100 1101。可以發(fā)現(xiàn)只要將x$amp;>amp;$gt;16與x$amp;
我們知道如何對(duì)字符串求逆序，現(xiàn)在要求計(jì)算二進(jìn)制的逆序，如數(shù)34520用二進(jìn)制表示為：10000110 11011000 00000000 00000000 將它逆序，我們得到了一個(gè)新的二進(jìn)制數(shù)：00000000 00000000 00011011 01100001 它即是十進(jìn)制的7009。 回顧下字符串的逆序的方法，可以從字符串的首尾開始，依次交換兩端的數(shù)據(jù)。在二進(jìn)制逆序我們也可以用這種方法，但運(yùn)用位操作的高低位交換來(lái)處理二進(jìn)制逆序?qū)?huì)得到更簡(jiǎn)潔的方法。類似于歸并排序的分組處理，可以通過(guò)下面4步得到32位數(shù)據(jù)的二進(jìn)制逆序： 第一步：每2位為一組，組內(nèi)高低位交換 00 00 00 00 00 00 00 00 10 00 01 10 11 01 10 00 → 00 00 00 00 00 00 00 00 01 00 10 01 11 10 01 00 第二步：每4位為一組，組內(nèi)高低位交換 0000 0000 0000 0000 0100 1001 1110 0100 → 0000 0000 0000 0000 0001 0110 1011 0001 第三步：每8位為一組，組內(nèi)高低位交換 00000000 00000000 00010110 10110001 → 00000000 00000000 01100001 00011011 第四步：每16位為一組，組內(nèi)高低位交換 0000000000000000 0110000100011011 → 0110000100011011 0000000000000000 對(duì)第一步，可以依次取出每2位作一組，再組內(nèi)高低位交換，這樣有點(diǎn)麻煩，下面介紹一種非常有技巧的 方法。先分別取10000110 11011000的奇數(shù)位和偶數(shù)位，空位以下劃線表示。 原 數(shù) 00000000 00000000 10000110 11011000 奇數(shù)位 0_0_0_0_ 0_0_0_0_ 1_0_0_1_ 1_0_1_0_ 偶數(shù)位 _0_0_0_ 0 _0_0_0_ 0 _0_0_1_0 _1_1_0_0 將下劃線用0填充，可得 原 數(shù) 00000000 00000000 10000110 11011000 奇數(shù)位 00000000 00000000 10000010 10001000 偶數(shù)位 00000000 00000000 00000100 01010000 再將奇數(shù)位右移一位，偶數(shù)位左移一位，此時(shí)將這兩個(gè)數(shù)據(jù)相與即可以達(dá)到奇偶位上數(shù)據(jù)交換的效果了。 原 數(shù) 00000000 00000000 10000110 11011000 奇數(shù)位右移 00000000 00000000 01000011 01101100 偶數(shù)位左移 00000000 00000000 00001000 10100000 相或得到 00000000 00000000 01001000 11100100 可以看出，結(jié)果完全達(dá)到了奇偶位的數(shù)據(jù)交換，再來(lái)考慮代碼的實(shí)現(xiàn)—— 取x的奇數(shù)位并將偶數(shù)位用0填充用代碼實(shí)現(xiàn)就是x & 0xAAAAAAAA 取x的偶數(shù)位并將奇數(shù)位用0填充用代碼實(shí)現(xiàn)就是x & 0×55555555 因此，第一步就用代碼實(shí)現(xiàn)就是： x = ((x & 0xAAAAAAAA) $amp;>amp;$gt; 1) | ((x & 0×55555555) $amp; 類似可以得到如下代碼：
方法1： 考慮到n-1會(huì)把n的二進(jìn)制表示中最低位的1置0并把其后的所有0置1，同時(shí)不改變此位置前的所有位，那么n&(n-1)即可消除這個(gè)最低位的1。這樣便有了比順序枚舉所有位更快的算法：循環(huán)消除最低位的1，循環(huán)次數(shù)即所求1的個(gè)數(shù)。此算法的時(shí)間復(fù)雜度為O(n的二進(jìn)制表示中的1的個(gè)數(shù))，最壞情況下的復(fù)雜度O(n的二進(jìn)制表示的總位數(shù))。
方法2： 通過(guò)下面四步來(lái)計(jì)算其二進(jìn)制中1的個(gè)數(shù)二進(jìn)制中1的個(gè)數(shù)。 第一步：每2位為一組，組內(nèi)高低位相加 00 00 00 00 00 00 00 00 10 00 01 10 11 01 10 00 → 00 00 00 00 00 00 00 00 01 00 01 01 10 01 01 00 第二步：每4位為一組，組內(nèi)高低位相加 0000 0000 0000 0000 0100 0101 1001 0100 → 0000 0000 0000 0000 0001 0010 0011 0001 第三步：每8位為一組，組內(nèi)高低位相加 00000000 00000000 00010010 00110001 → 00000000 00000000 00000011 00000100 第四步：每16位為一組，組內(nèi)高低位相加 0000000000000000 0000001100000100 → 0000000000000000 0000000000000111 代碼如下：
參考資料
你可能還喜歡：
|
|
|
來(lái)自： lixinhecom > 《C語(yǔ)言》
