190. Reverse Bits

两两交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        for (int i = 0; i < 16; i++) {
            int lowBit = (n >>> i) & 1;
            int highBit = (n >>> (31 - i)) & 1;
            if (lowBit != highBit) {
                if (lowBit == 0) {
                    // 高位改为 0, 低位改为 1
                    n &= ~(1 << (31 - i));
                    n |= (1 << i);
                } else {
                    // 高位改为 1, 低位改为 0
                    n |= (1 << (31 - i));
                    n &= ~(1 << i);
                }
            }
        }

        return n;
    }
}

循环

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int res = 0;

        for (int i = 0; i < 32 && n != 0; i++) {
            res |= (n & 1) << (31 - i);
            n >>>= 1;
        }

        return res;
    }
}

分治

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    // you need treat n as an unsigned value
    private static final int B1 = 0b01010101010101010101010101010101;
    private static final int B2 = 0b00110011001100110011001100110011;
    private static final int B4 = 0b00001111000011110000111100001111;
    private static final int B8 = 0b00000000111111110000000011111111;

    public int reverseBits(int n) {
        n = ((n >>> 1) & B1) | ((n & B1) << 1);
        n = ((n >>> 2) & B2) | ((n & B2) << 2);
        n = ((n >>> 4) & B4) | ((n & B4) << 4);
        n = ((n >>> 8) & B8) | ((n & B8) << 8);
        return (n >>> 16) | (n << 16);
    }
}

References

190. Reverse Bits