位運算直接對在內存中的二進制數據進行處理,因此處理數據的速度非常快,巧妙的運用位運算可以使程序更簡潔和高效。

C中基本的位運算包含&,|,~,^,<<,>>,其中取反(~)是單目運算,其餘為雙目運算,java中多了一個無符號右移>>>,最高位的符號位不參与補位。我們知道最高位表示這個數的符號0為正數,1為負數,>>位移會將高位的空缺補成符號位。下圖以byte為例


無符號右移.jpg

所以求int最大值可以使用(1<<31)-1,也可以使用-1>>>1這裏就利用了無符號右移技巧。

練習題:
房間有32盞燈,需要實現以下功能:
1.打開某盞燈
2.關閉某盞燈
3.打開所有燈
4.關閉所有燈
5.指定下標返回此燈的狀態
要求:使用最小的存儲空間。
很多人拿到這個題直接定義一個boolean數組或int數組,但是仔細想想開和關兩個狀態可以使用一個bit位來保存,int正好32位,所以用1個int就可以處理了。

class Light {
    int l; // 用一個int保存32盞燈的狀態
}

1、打開某盞燈,即將該位置設1。1或上0,1均為1,所以我們只需將1移到指定的位置然後求或即可。


No.1.jpg

代碼如下:

/**
 * 打開某盞燈
 * @param i 下標1~32
 */
public Light turnOn(int i) {
    l |= (1 << i - 1);
    return this;
}

2、關閉某盞燈,即將該位置設0。


No.2.jpg

代碼如下:

/**
 * 關閉某盞燈
 * @param i 下標1~32
 */
public Light turnOff(int i) {
    l &= ~(1 << i - 1);
    return this;
}

3、打開或關閉所有盞燈,即將所有位設1。上面無符號右移的圖中可知-1的二進制是全1所以我們可以使用l|-1,但暈個-1是個魔數無意思可以將-1換成~0變成l|~0,還可以使用異或(XOR)相同為0,不同為1,一個數XOR自己將得到0,那XOR自己的反則得到1於是可以寫成l^~l

/**
 * 打開所有燈
 */
public Light turnOnAll() {
    l ^= ~l; // 或 l |= ~0 或 l |= -1
    return this;
}
/**
 * 關閉所有燈
 */
public Light turnOffAll() {
    l ^= l; // 或 l &= 0
    return this;
}

5、指定下標返回此燈的狀態,這個比較簡單把這個位右移到首位然後與1即可

/**
 * 返回指定燈的狀態
 * @param i 下標1~32
 */
public int statusOf(int i) {
    return l >>> (i - 1) & 1;
}

下面是完整代碼附測試代碼

static class Light {
    int l; // 用一個int保存32盞燈的狀態

    /**
     * 打開某盞燈
     * @param i 下標1~32
     */
    public Light turnOn(int i) {
        l |= (1 << i - 1);
        return this;
    }

    /**
     * 關閉某盞燈
     * @param i 下標1~32
     */
    public Light turnOff(int i) {
        l &= ~(1 << i - 1);
        return this;
    }

    /**
     * 打開所有燈
     */
    public Light turnOnAll() {
        l ^= ~l; // 或 l |= ~0 或 l |= -1
        return this;
    }

    /**
     * 關閉所有燈
     */
    public Light turnOffAll() {
        l ^= l; // 或 l &= 0
        return this;
    }

    /**
     * 返回指定燈的狀態
     * @param i 下標1~32
     */
    public int statusOf(int i) {
        return l >>> (i - 1) & 1;
    }

    /**
     * 打印,將int轉為2進制格式輸出
     */
    public void println() {
        int charPos = 32;
        int var = l;
        char[] buf = new char[charPos];
        for (int i = 0; i < buf.length; i++) {
            buf[i] = '0';
        }
        do {
            buf[--charPos] += (var & 1);
            var >>>= 1;
        } while (var != 0 && charPos > 0);
        System.out.println(new String(buf));
    }
}

測試代碼

    public static void main(String[] args) {
        // TEST
        Light l = new Light();
        l.turnOn(1).println();
        l.turnOn(10).println();
        l.turnOff(1).println();
        l.turnOffAll().println();
        l.turnOnAll().println();
        l.turnOff(32).turnOff(12).println();
        System.out.println(l.statusOf(10));
        System.out.println(l.statusOf(12));
    }

位運算的優先級較低要記得寫括號,不然會造成意想不到的後果。

分享