《程式設計導論（Java）·12.1基本位運算》

能抓住和定位單個原子的機器将能制造任何東西…

當然，一次一原子地造個大物體會很慢。

——Eric Drexler《Engines of Creation: The Coming Eraof Nanotechnology》

     位運算(Bitwise operations)在bit層面上對操作數進行按位操作。內建電路的邏輯門(logic gate)能夠在bit上執行與、或、異、反操作，因而位運算在彙編語言中被廣泛使用。通常它們的效率比數值的加減運算稍快，而比數值的乘除運算則有顯著提高。進階語言如Java中，在通常情況下不會考慮如此低層的操作，隻有在特定場合或某些關鍵算法實作時，才使用位運算。

     本章将介紹位運算的各種操作及其應用。

12.1基本位運算

Java隻能對int、long進行按位操作。如果操作數短于int，如byte、char，它們将被自動提升為int然後再參與運算。

Java位運算操作符分成兩大類：位-邏輯運算符和移位運算符。

12.1.1 位-邏輯運算符

Java中的按位運算，使用了重載的運算符：&(AND、與)、|(OR、或)、^(XOR、異)。這三個重載的操作符，根據操作數的資料類型決定它們是邏輯運算還是位運算。如5&2是位運算而true|(3<2) 是邏輯運算。而~(tilde，求反)将一個數的二進制補碼按位求反。

每一個bit隻可能是0和1，對應地，boolean值隻有false和true。是以按位運算與邏輯運算具有本質上一緻的真值表，如表12-1所示。比較[表格3-4真值表]，以1對應于true、0對應于false，非常容易換算出彼此的真值表。

表格 12‑1 真值表

p	q	p & q	p ^ q	p| q	~p
1	1	1	1
1	1	1
1	1	1	1
1

位運算之是以稱為按位運算，是因為兩個操作數的對應位相操作，不會對其他位造成影響(沒有算術加法的進位等規則)。

練習12-1.：請比較位運算和邏輯運算的所有操作符。提示：&&和||、邏輯操作的!(非)與不等于操作符!=保持一緻而不與位運算的~重載。

練習12-2.：複習0.1.2二進制補碼，寫出97、-5的二進制補碼。

1. 與或反

按位與、按位或和按位非/反是基本的位操作。Java 7所引入了二進制文字，極大地增強了位操作代碼的可讀性。如果求10& -5 ，必須非常熟悉二進制補碼，才知道得數；如果準備計算0b1010& -0b0101，較容易看出操作結果。

正數如10的二進制文字，可以有若幹前導0，因而0b00_1010和0b1010均為10；而負數如-5，通常表示為-0b101，若表述為0b1111_1111_1111_1111_1111_1111_1111_1011就太長。

10         =0b1010 

-5    = 0b...1111_1011

10& -5 =      0b1010，即10。

【按位與、按位或和按位非/反的基本操作，同學們自己在練習12-3中 自己玩】

如果一個操作對操作數的位很敏感，則可以利用計算機存儲數值的二進制特點，通過位運算得到高效而簡潔的代碼。【有很多的例子，後面補充一些】例如判斷int i是否是2的幂次方。2的幂如16的二進制表示為0b0001_0000，僅僅有一位是1，而16-1的二進制表示為0b0000_1111，兩者相與為0。因為0& (0-1)也等于0，是以要排除，添加&&(v!=0)。

例程 12‑1判斷x的絕對值是否2的幂
package algorithm.bitOp;
public class BitOpDemo{    
    public static boolean 是否是2的幂(int x){
        int v= (x>=0) ? x : -x;
        return  ( (v & (v - 1)) == 0  &&(v!=0) );
    }    
}
           

練習12-3.：使用algorithm.bitOp. BitOpDemo的方法“與或異反操作()”，了解這四個運算符。

練習12-4.：判斷int變量i的值是奇數，可以boolean isOdd = (i % 2 = = 1)，請用位運算進行判斷。

練習12-5.：編寫方法complement(int)，為任意int數求其補碼。

補充：判斷一個數能否被3整除

在例程3-2中有方法

    privatestatic boolean is3X(int n){

        return( n%3 == 0);

    }

現在要求改變思路——使用位運算。如果一個數的每個位相加之和能被3整除，則這個數就可以被3整除。但是，這是十進制中的規律，那麼在二進制中，需要我們找到其特點——這是使用位運算的關鍵。 如果所有的偶數位出現1的次數為 even_count, 奇數位出現1的次數為 odd_count，兩者之差如果是3的倍數，那麼這個數就是3倍數。( 為什麼有這個特點，怎樣找到這個特點的？我不知道！)代碼中要用到移位，後面給出。

2. 掩碼

與、或運算常用于對某個數x的特定位進行設定和提取。表達式mask | x或mask & x中，與x運算的數稱為掩碼。令b表示一個位。

置1：按照真值表，1|b =1、0|b =b，是以mask | x能夠按照mask為1的位将x的對應位設定為1，其他位不變。例如需要設定x的倒數1、倒數6位設定為1，其他位不變，則可以令mask為0b10_0001。

清0：按照真值表，0&b =0、1&b =b，故mask & x能夠按照mask的0将x對應的位設定為0。

取位：不管置1還是清0，x都有一些位保持不變。假設需要提取int x的最低12位，可以使其他位清0，即求x & 0xFFF(清0型取位)；也可以使其他位為1，即x | 0xFFFF_F000(置1型取位)，但不友善。

掩碼通常參與移位運算，見下一節。

練習12-6.：如何提取int x的最低位元組；如何将x的倒數1、3，5，7位置1。令int mask = 0x80000000，mask & x的作用是什麼？

練習12-7.：何謂置1、清零。

3. 異或

令b表示一個位。按照真值表，1^b = ~b、0^b = b。因而可以推導出許多有趣的規律用于程式設計。例如對于int x，有性質：

²       x^ x = 0

²       x^ x^ x = x

²       x^ (-1) = ~x。

一個著名的例子，将[11.1說明] algorithm.sorting.IntSort的換位操作方法swap(int[] a ,int one, inttwo)以異或實作，其特點是不需要過渡的臨時變量。

例程 12‑2異或換位

package algorithm.bitOp;
public class XOR{
    public static void swap(int[] a ,int i, int j){
        a[i] = a[i]^a[j];
        a[j] = a[i]^a[j];
        a[i] = a[i]^a[j];
    }
}
           

異或換位的原因，記a[i]為x，a[j]為y。

第一步：x起臨時變量作用，記作x’= x ^y。

第2步：y’=x’ ^y = (x^y)^y=x^(y^y)=x^0=x；

第3步：x=x’^y’= (x^y)^ x=x^x^y=y。

練習12-8：根據性質x^ x = 0，說明x= a ^ b ^ x等價于切換語句(x僅取值a、b)： (1) if(x == a) x=b; else x =a; (2) x = (x == a) ? b:a;

12.1.2 移位運算符

移位意味着将一個數的各二進制位序列向左或右移動(shife、move)若幹位，移出的位自然地被抛棄，而移位運算的關注點是如何填充空缺位。

右移有兩種，>>操作符為算術右移，它保持原數值的算術符号，左邊用最高位(符号位)填充。>>>操作符為邏輯右移，左邊以0填充。因而算術右移>>可以用于替代正負整數的除法， 例如x>>1等價于x/2、x>>n等價于x/2n。邏輯右移x>>>并不重視x二進制的補碼是否是一個有效的算術運算值【一些時候，Java中缺少無符号數真的不友善】。

例程12-3中，以0x8000_0000為掩碼mask，提取x的最高位。通過mask的邏輯右移逐一提取x的一個位并列印該位。Java中int有32位，從最高位(符号位)移到最低位隻需要31次。為了友善每輸出4bit列印一個空格，i初始化為1。【在學習基本按位與、按位或和按位非的時候，這個工具 showBits(int x)有點用】

例程 12‑3列印int數值的位

package algorithm.bitOp;
public class BitOpDemo{
    private static final int iSIZE = 32;//integer
    public static void showBits(int x) {
        int mask = 0x8000_0000;
        for (int i = 1; i <=iSIZE; i++) {
            byte bit = (byte) ((mask & x) != 0 ? 1 : 0);            
            System.out.print(bit); 
            if (i % 4 == 0) { System.out.print(" "); }
            mask >>>= 1;
        }
}
}
           

例程12-4使用移位運算進行求幂，計算并傳回一個double數的int次方，記x exp，使用乘法需要計算exp-1次。而x exp可以形成x 1 x 2 x 4x 8 x 16……次方，如x 17＝ x 16x。通過exp移位，僅需要計算x 1 x 2 x 4……次方和所需要的有效位，如x 17僅需要計算5+2次而非16次。

例程 12‑4求一個double數的int次方

package algorithm.bitOp; public class ShifeOpDemo{     public static double power(double d, int exp) {         if (exp < 0) {             return 1 / power(d, -exp);         }else if(exp == 0){             return 1;         }         double value = 1;         while (exp > 0) {             if ((exp & 1) == 1) value *= d;                        exp >>= 1;// exp每右移一位，x 求平方一次。             d *= d;         }         return value;     } }

左移運算符<<，高位左移後溢出被舍棄，右端補0。是以算術左移運算要注意符号位的變化。在不産生溢出條件下，正數左移如i<<2等價于i*4；負數則以其絕對值左移再取負數。

例程12-5統計String的byte[]表示(01串)中1的個數。可以按照例程12-3将mask邏輯右移而提取x的一個位，這裡将x左移而提取x的一個位。

例程 12‑5統計01串中1的個數

package algorithm.bitOp; public class ShifeOpDemo{     public static void getOnes(String s){         byte[] sequence = s.getBytes();         int count = 0;//1的個數         int total = sequence.length * 8; //總個數         for (byte x:sequence) {             for(int i = 0;i<8;i++){//對位元組的每一位操作                 boolean bit = (x & 0x80) == 0;//提取最高位，為0則bit為false。                 if(!bit) count ++;//1的個數                 x<<=1;//高位左移後溢出被舍棄，右端補0。             }         }         System.out.println( count );     } }

在長期的彙編語言或C語言程式設計中，人們積累了大量位運算的技巧，位運算要比乘、除法運算效率高很多。在閱讀一些算法的源代碼時，經常會見到程式員使用這些位運算技巧。

練習12-9.給定byte[] bs，長度為8的倍數。請将bs的每個byte的第3位取出并儲存到byte b中。

練習12-10.：給定字元串s，它由01組成，如"00011101…"，将它們填入int n的第30位開始各位中。如果s長度不足，則n的低位補0。提示：定義int getBit()，完成從s中提取一個字元并輸出一個0或1。

/**
     * 如果所有的偶數位出現1的次數為 even_count, 奇數位出現1的次數為 odd_count，
     * 兩者之差如果是3的倍數，那麼這個數就是3倍數。
     */
    public static boolean is3X(int n){
        int odd_count =0,even_count =0;
        if(n < 0)   n = -n;
        if(n == 0) return true;
        if(n <= 2) return false;
        while(n!=0){
            if((n & 1)==1) odd_count++;
            n = n>>1;
            if((n & 1)==1) even_count++;
            n = n>>1;
        }
        return  is3X(odd_count - even_count);
    }