ReverseBits [source code]

public class ReverseBits {
static
/******************************************************************************/
public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int[] bits = new int[32];
        int index = 0;
        while (n != 0) {
            bits[index++] = n & 1;
            n >>>=1;
        }
        int base = 1;
        int sum = 0;
        for (int i = 31; i >= 0; i--) {
            sum += base * bits[i];
            base *= 2;
        }
        return sum;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ReverseBits.Solution tester = new ReverseBits.Solution();
        int[] inputs = {
            43261596, 964176192,
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int n = inputs[2 * i];
            int output = tester.reverseBits(n);
            int expected = inputs[1 + 2 * i];
            System.out.println(Printer.seperator());
            Printer.openColor("magenta");
            System.out.print(n);
            Printer.closeColor();
            System.out.print(" -> " + output);
            Printer.openColor(output == expected ? "green" : "red");
            System.out.println(", expected: " + expected);
            Printer.closeColor();
        }
    }
}

32-bit unsigned, 最后肯定有overflow的case;
不过最后实际上并没有这个overflow的检查. 这个问题本身的算法是比较简单的, 唯一一个技巧就是用一个array倒序存放, leading 0s直接用array的默认初始值来完成就行了. 最后的速度是3(14), 倒是不怎么理想;

这个是submission最优解: 2(40):

public class Solution {  
    // you need treat n as an unsigned value  
    public int reverseBits(int n) {  
        int result = 0;  
        for(int i = 0; i < 32; i++) {  
            result = result + (n & 1);  
            n = n >> 1;  
            if(i < 31) {  
                result = result << 1;  
            }  
        }  
        return result;  
    }  
}

算法本身还是很简单, 核心思想还是一样的, 对于leading0, 不借用array其实也是可以处理的, 就像这里, 他的做法的核心是, 循环的header不是使用常用的n != 0这样的判断: 这个判断本身的意思就是"到leading1就停止", 所以自然你处理前面的leading0就很麻烦. 正确的做法就是跟他这里一样, 直接header里面强制32位全部走完, 至于当前的位上是0还是1, 无所谓. 在循环内部, 直接一个res储存结果.

discussion里面对此提出一个小优化:

for(int i=0; i<32; i++){  
result = result << 1;  
//bitwise OR is cheaper than add  
result = result | n&1;  
n = n >> 1;  
}

discussion上面一个稍微有点奇葩的解法:

class Solution {  
public:  
    uint32_t reverseBits(uint32_t n) {  
        n = (n >> 16) | (n << 16);  
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);  
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);  
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);  
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);  
        return n;  
    }  
};

for 8 bit binary number abcdefgh, the process is as follow:

abcdefgh -> efghabcd -> ghefcdab -> hgfedcba

这个就是一个divide and conquer的做法, 因为这里int的长度是固定的, 所以实际做的时候可以直接用bit运算来完成移动; 这些bit运算的核心操作就是使用&来完成一个类似filter的操作, 然后shift, 让shift之后的空白区域(被前面的&filter给覆盖掉的全0区域)与另一边产生的有效区域进行 | 运算, 来完成一个组合的操作;

这个算法本身还是有点trivial, 不过这里学一学达成特定目的的bit手段还是有所帮助; 尤其是bit操作当中的reverse block操作, 怎么用shift来实现: 先覆盖, 再组合;

The same algorithm appears in Integer.reverse of JDK and is discussed in Hackers Delight. Just FYI

这个是另外一个人给出的解释:

//方法2：使用位操作  
public int reverseBits2(int n){  
    n = ((n & 0xAAAAAAAA ) >>> 1) | ((n & 0x55555555) << 1);  
    n = ((n & 0xCCCCCCCC ) >>> 2) | ((n & 0x33333333) << 2);  
    n = ((n & 0xf0f0f0f0 ) >>> 4) | ((n & 0x0f0f0f0f) << 4);  
    n = ((n & 0xff00ff00 ) >>> 8) | ((n & 0x00ff00ff) << 8);  
    n = ((n & 0xffff0000 ) >>> 16) | ((n & 0x0000ffff) << 16);  
    return n;  
}

利用高地位交换实现逆序
两位一组，高低位互换，方法是（取奇数位，偶数位补0，右移1位）| （取偶数为，奇数位补0，左移1位）
依次四位一组，八位一组，十六位一组，三十二位一组
由于是无符号位，所以注意得是逻辑右移

这个是discussion里面一个人对于Follow-Up给出的答案:

// cache  
private final Map<Byte, Integer> cache = new HashMap<Byte, Integer>();  
public int reverseBits(int n) {  
    byte[] bytes = new byte[4];  
    for (int i = 0; i < 4; i++) // convert int into 4 bytes  
        bytes[i] = (byte)((n >>> 8*i) & 0xFF);  
    int result = 0;  
    for (int i = 0; i < 4; i++) {  
        result += reverseByte(bytes[i]); // reverse per byte  
        if (i < 3)  
            result <<= 8;  
    }  
    return result;  
}  

private int reverseByte(byte b) {  
    Integer value = cache.get(b); // first look up from cache  
    if (value != null)  
        return value;  
    value = 0;  
    // reverse by bit  
    for (int i = 0; i < 8; i++) {  
        value += ((b >>> i) & 1);  
        if (i < 7)  
            value <<= 1;  
    }  
    cache.put(b, value);  
    return value;  
}

就是一个利用cache, 或者memo的思路, 并不是特别复杂, 但是真正面试的时候, 能不能立刻想到又是另外一回事了;

但是底下有人提出质疑:
It seems that HashMap can accelerate the algorithm, but the fact is not as we hope.

If we repeat the function 10,000,000 times, the first algorithm you provide will cost 8,940 ms, the second algorithm you provide will cost 12,454 ms, while the following code will cost only 3,500 ms.

The optimized code runs slower.

I think reasons are as follows:

1.In the following code, the bit operation is QUITE FAST, no if/while/for statment, thus no branch predictions, and the efficiency of every statement will be almost 100%.

2.In the "cache" solution, the function calls、 brach predictions 、read/write-memory operations or even hash collisions will all contribute to the cost of time.

public int reverseBits(int n) {  
        int ret=n;  
        ret = ret >>> 16 | ret<<16;  
        ret = (ret & 0xff00ff00) >>> 8 | (ret & 0x00ff00ff) << 8;  
        ret = (ret & 0xf0f0f0f0) >>> 4 | (ret & 0x0f0f0f0f) << 4;  
        ret = (ret & 0xcccccccc) >>> 2 | (ret & 0x33333333) << 2;  
        ret = (ret & 0xaaaaaaaa) >>> 1 | (ret & 0x55555555) << 1;  
        return ret;  
}

意思还是把算法本身写到最优才能导致最后的速度提升;

不过上面这个cache的思路, 我感觉他这个HashMap好像可以换成一个hash array, 因为他cache的是8bit的byte, 所以最后实际的entry数量很有限;

public class Solution {  
    // you need treat n as an unsigned value  
    Integer[] hash = new Integer[256];  
    public int reverseBits(int n) {  
        int res = 0;  
        for(int i = 0; i < 4; i++){  
            int tmp = n & 0xFF;  
            if(hash[tmp] != null){  
                res = (res << 8) + hash[tmp];   
            } else{  
                res = (res << 8) + reverse8Bits(tmp);  
            }  
            n >>= 8;  
        }  
        return res;  
    }  

    private int reverse8Bits(int n){  
        int res = 0;  
        int tmp = n;  
        for(int i = 0; i < 8; i++){  
            res = (res << 1) + (tmp & 1);  
            tmp >>= 1;  
        }  
        hash[n] = res;  
        return res;  
    }  
}

被AC了, 好像是可以的;

Problem Description

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

LC190 ReverseBits

ReverseBits [source code]

Problem Description

results matching ""

No results matching ""