程序员面试金典---7

二进制转字符串

思路;

使用2成十进制小数，可以得到积，将积的整数部分取出，再用2乘余下的小数部分，又得到一个积，再将积的整数部分取出，依次继续。直到积中的整数部分为0，或者整数部分为1，此时0或1为二进制的最后一位。

例：

0.625=(0.101)B

0.625 * 2 = 1.25 -------取出整数部分1
0.25 * 2 = 0.5 ------- 取出整数部分0
0.5 * 2 = 1 ------- 取出整数部分1 
结束

代码：

/**
 * @param {number} num
 * @return {string}
 */
var printBin = function(num) {
    // 结果
    res = ''
    // 循环到31，题目要求
    for(let i = 0;i < 32; i++){
        num *= 2  
        // 等于1 直接返回结果
        if(num == 1) {
            return '0.' + res + '1'
        }
        // 减一，添加1
        else if(num > 1) {
            res += '1'
            num = num - 1
        }else{
            // 添加0
            res += '0'
        }
    }
    return 'ERROR' 

};

翻转数位

1. 维护一个窗口，窗口内的0的个数<=的时候，窗口大小都可以计入结果，取长度的最大值
2. 当窗口内的0的个数>1的时候，收缩窗口，直到满足<=1
3. 窗口边界的取值范围为[0,31]

/**
 * @param {number} num
 * @return {number}
 */
var reverseBits = function(num) {
    // slide window
    let s = 0;
    let c = 0;
    let res = -1;
    for (let f=0; f<32; f++) {
        if ((num & (1 << f)) === 0) c += 1;
        while (c > 1) {
            if ((num & (1 << s)) === 0) c -= 1;
            s += 1;
        }
        res = Math.max(res, f-s+1);
    }
    return res;
};