位運算(上)

菜鳥日記—1月18日

案例1:

陣列中確定唯一成對的數

1~N-1在長度為N的陣列中,只有唯一一個元素值重復,其它均只出現一次
每個陣列元素只能訪問一次,設計一個演算法將他找出來，不用輔助空間

*第一種方法
構造新陣列與其進行與運算

先構造陣列

public class 陣列中確定唯一成對的數 {
    public static void main(String[] args) {
    int N = 11;		//N可自己自行設定
    int[] arr = new int[N];
    for (int i = 0; i < arr.length-1; i++) {
        arr[i] = i + 1;}

最后一個數取亂數,并與前面隨機一個元素對換位置

	//最后一個數取亂數
    arr[arr.length-1] = new Random().nextInt(N-1)+1;
    //隨機下標
    int index = new Random().nextInt(N);
    //最后一個數與前面隨機一個數互換位置
    int t=arr[N-1];
    arr[N-1]=arr[index];
    arr[index]=t;
    System.out.println(Arrays.toString(arr));
    int x = 0;

構造新陣列與其進行與運算并輸出

	//構造一個1~N-1的陣列
    for (int i = 0; i < N-1; i++) {
        x = x ^ (i + 1);
        }
    //新陣列與舊陣列作亦或運算,其余相同的數亦或為零
    //而成對的數加新陣列里面那個數則有3個,所以亦或結果便是成對的那個數
    for (int i = 0; i < N; i++) {
        x ^= arr[i];
        }
    System.out.println(x);

*第二種方法

輔助空間解法(暴力破解)

int[] f = new int[N];
        for (int i = 0; i <N ; i++) {
            f[arr[i]] += 1;//原先每個元素都是0,現在給下標為arr[i]的每個都加1
                            //因為其中有兩個數是一樣的,所以會加兩次
        }
        //System.out.println(Arrays.toString(f));
        for (int i = 0; i < N; i++) {
            //當新陣列中某個元素等于2時,那么他的下標就是重復的那個數
            // (因為第一個元素被0占用了，所以下標不用加一)
            if(f[i]==2){
                System.out.println(i);
            }
        }
    }
}

效果圖:

每次結果都不一樣

案例2:

求二進制中’1’的個數

輸一個整數,判斷其二進制中有多少個’1’

有三種解法

1.從右往左依次比對

public class 二進制中1的個數 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(Integer.toString(N,2));
        //1.從右往左挨個比對是否為1
        int count1 = 0;
        for (int i = 0; i < 32; i++) {
            if ((N&(1<<i))==(1<<i)){
                count1++;
            }
        }
        System.out.println(count1);

2.從左往右依次比對

	int count2 = 0;
        for (int i = 0; i < 32; i++) {
            if (((N>>i)&1)==1){
                count2++;
            }
        }
        System.out.println(count2);

3.減1法
通過將輸入的數減1與原數進行與運算,與幾次就有幾個1

	int count3 = 0;
        //因為不知道要回圈幾次,所以用while
        while (N != 0){
            N = (N-1)&N;
            count3++;
        }
        System.out.println(count3);
    }
}

下面是減1法的圖解,些許潦草,別介意
假設輸入的數是20,有兩個1,則與兩次

效果圖:

案例3:

是不是2的整次方

輸入一個數,判斷其是不是2的整數次方
思考:當一個數的二進制位上有且只有一個1時,那么他便是2的整數次方；
比如:8只有從右往左第4位為一,64則是第7位

public class 是不是2的整次方 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int a = 2;
        if ((N & (N - 1)) == 0){
            System.out.println("yes");
        }
        else {
            System.out.println("no");
        }
    }
}

效果圖:


案例4:

奇偶位互換

給出一個整數,將他的二進制奇偶位互換,并驗證互換是否成功
如9的二進制為: 1001，奇偶位互換后為:0110等于6

public class 交換奇偶位 {
    public static void main(String[] args) {
        int a = 9;
        int b = huan(a);
        //驗證換位是否成功,9奇偶位互換等于6
        int c = 6;
        System.out.println(b);
        if (c == b){
            System.out.println("yes");
        }
    }

    private static int huan(int i) {
    	//這里用二進制太長了,我用十六進制表示
        int ji = i & 0x55555555; //和1010 1010 1010 1010......做與運算取出奇數位
        int ou = i & 0xaaaaaaaa; //和0101 0101 0101 0101......做與運算取出偶數位
        return (ji << 1) ^ (ou >> 1); //合并成一個二進制數
    }
}

圖解:
假設要互換的數是9

效果圖:

over!!!
寒冷而充實的一天結束，