一个数的二进制位反转

2011-09-25

前天参加汇顶科技的笔试,最后一道编程题是求一个数的二进制表示反序后的值,例如10的二进制表示是0000 1010,反序后是0101 0000,十进制值是80。题目给的函数签名是:

unsigned char reverse(unsigned char var){

}

刚开始想到的肯定是用除2余和除2来算出所有位来咯。不过又想了一下,感觉这样做太水了,就想能不能用位运算来实现,想了一段时间后,终于想到可以用”按位与运算”和”移位运算”来求出某一位上是什么。例如要求低位起第二位就可以是:num & (1 << 1)。因为1左移1位就是0000 0010,跟它做按位与运算,得出的就只剩下num的低位起的第二位了。然后再将这一位移到对称位上,即cache << 5(假设上面的运算得到的结果是cache),得出0100 0000(悲剧的是我当初忘记反转了!)。然后对每一位都这样处理就行了。下面给出实现代码(JavaScript实现,假设8位):

function reverse(num) {
    var i, cache, result = 0;
    for (i = 0; i < 8; i++) {
        cache = num & (1 << i);
        if (i < 4) {
            cache <<= 7 - 2 * i;
        } else {
            cache >>= 2 * i - 7;
        }
        result += cache;
    }
    return result;
}

代码很简单,顺便也给出使用除2余和除2方法实现的代码:

function reverse(num) {
    var i, len, numArray, result = 0;
    numArray = [];
    //分解位
    while (num != 0) {
        numArray.push(num % 2);
        num = parseInt(num / 2);
    }
    //下面反转
    for (i = 0, len = numArray.length; i < len; i++) {
        result += numArray[i] * Math.pow(2, 7 - i);
    }
    return result;
}

感觉这道题还是很简单的,就是考试的时候想到了那个求某一位上数的方法,太兴奋导致忘了题目的反转,以后写完代码还是要细心的检查一下!然后如果各位看官有什么更好的解法的话,欢迎留言!