Skip to content

Latest commit

 

History

History
271 lines (212 loc) · 7.58 KB

10.md

File metadata and controls

271 lines (212 loc) · 7.58 KB
Raw

二进制与十进制转化，位运算

正码、反码与补码

模

模：可理解为周期。一个偶数模，一半表示正数，一半表示负数。

正码/原码

十进制数的直接二进制表示。如果是正数第一位0，是负数第一位是1。但是会出现正负数相加不等于0的情况，所以产生了反码。

反码

反码：正数的反码是自己，负数的反码是除了首位外其他位取反。正负数相加等于0了，但是会存在两个0的情况。为了解决两个0，所以产生了补码。

补码：正数的补码是自己，负数的补码是先求反码再加1。

十进制转二进制

整数部分是除2取余，逆序排列

小数部分是乘2取整，顺序排列

function ttwo(num) {
    let str = num + ''
    let dotIndex = str.indexOf('.')
    let intNum = dotIndex > 0 ? str.substr(0, dotIndex)/1 : str/1
    let floatNum = dotIndex > 0 ? str.substr(dotIndex, str.length - dotIndex)/1 : 0
    let intRet = []
    let floatRet = []
    while (intNum > 1) {
        intRet.push(intNum % 2)
        intNum =intNum - Math.floor(intNum / 2) - intNum % 2
    }
    intRet.push(intNum)
    while (floatNum) {
        let _int = floatNum * 2
        if (_int >= 1) {
            floatRet.push(1)
            floatNum = _int - 1
        } else {
            floatNum = _int
            floatRet.push(0)
        }
    }
    if (floatRet.length) {
        return (intRet.reverse().join('') + '.' + floatRet.join(''))/1
    } else {
        return intRet.reverse().join('')/1
    }
}

二进制转十进制

十进制的整数与小数的方法一致：

整数部分：二进制的从右往左为,第一位num*2的0次方，第二位num*2的1次方... 直至最左侧的num*2的0次方

小数部分：小数部分的二进制从左往右为，第一位num*2的-1次方，第二位num*2的-2次方

abcd.efg(2)=d*20+c*21+b*22+a*23+e*2-1+f*2-2+g*2-3（10）

function tten(num) {
    let str = num + ''
    let n = 0
    let dotIndex = str.indexOf('.')
    let intNum = dotIndex > 0 ? str.substr(0, dotIndex) : str
    let floatNum = dotIndex > 0 ? str.substr(dotIndex + 1, str.length - dotIndex) : ''

    for (let i = 0; i < intNum.length; i++) {
        n +=  intNum[i]*Math.pow(2, intNum.length - i - 1)
    }

    for (let i = 0; i < floatNum.length; i++) {
        n +=  floatNum[i]*Math.pow(2, -1 * (i + 1))
    }
    return n
}

位运算

&： 与。都为1时才为1

|：或。只有一个为1才为1

^：异或。相同为0，不同为1

~：取反。0变1，1变0

<<：左移。左移若干位，高位丢弃，低位补0。左移一位其实就是乘以2，左移n位就是乘以2的n次方。需要注意的是左移后依然保持符号位。

：右移。一般>>表示有符号位右移。>>>表示无符号位右移。都等于除以2的n次方，向下取整。

无符号位右移若干位，高位都补0。

若有符号位，整体右移n位，保留符号位。

位运算应用

判断奇偶

与操作，只有都为1才为1。而偶数的最后一位必定0。那么0&1就是1，不等于0。

function fc(num) {
    return num & 1 != 0
}

判断一个数是不是2的n次幂。n为整数。

2的n次幂表示为二进制，必定是1后面m个0，比如1000。那么减去1就是0111，这两个相与，必定结果为0。

function fc(num) {
    return num & (num - 1) == 0
}

求一个整数二进制表示中1的个数。

// 方法1
function fc(num) {
    let ret = 0
    while (num) {
        // 判断最后一位是不是1
        ret += num & 1
        // 右移一位
        // 注意>>>代表有符号位移动
        num >>>= 1
    }
}
// 方法2原理是 每个数与比自己小于1的数中必定存在一个数的最后一位为1，并且相与必定最后一个1会被抹去。

function fc(num) {
    let ret = 0
    while (num) {
        // 判断最后一位是不是1
        num = num & (num - 1)
        // 每次抹除1个1
        ret++
    }
}

在一个数组中，所有数字都出现两次，除了一个之外。找出这个数。要求时间复杂度为O(n),空间复杂度为1。

先需要知道规律：

任何一个数与0异或都是本身，任何数与自身异或都是0，多个数异或遵循交换律。

function fc(arr) {
    let ret = 0
    for (let i = 0; i < arr.length; i++) {
        ret = ret ^ arr[i]
    }
    return ret
}

在一个数组中，所有数字都出现两次，除了两个之外。找出这两个数。

1，第一次完整遍历异或后，得到的值肯定为数组中两个没有重复值的异或结果

2，因为两个数字不一样，所以异或结果一定存在一个位为1，那么找到这个位的索引值。两个不同的数，这个索引值一个为1一个为0.

3，再次遍历数组的每个值，如果一个数该索引值的数字为1，则执行异或。因为相同的数执行完异或都为0，所以必定留下的是，目标两个数中索引值为1的值（为1）的那位。如果为0也执行异或，同理也留下的是目标两个数中索引值为0的值（此时为0）。

function fc(arr) {
    let eo = 0
    let leftArr = []
    let rightArr = []
    for (let i = 0; i < arr.length; i++) {
        eo = eo ^ arr[i]
    }
    let index = 0
    while (eo) {
        if (eo & 1 == 1) {
            break;
        }
        eo = eo >> 1
        index++
    }
    let ret1 = 0
    let ret2 = 0
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] >> index  & 1 == 1) {
            ret1 = ret1 ^ arr[i]
        } else {
            ret2 = ret2 ^ arr[i]
        }
    }
    return [ret1, ret2]
}

在一个数组中，所有数字都出现三次，除了一个之外。找出这一个数。

用二进制表示，则所有数字的二进制每位相加，如果出现3次，则可被3整除，那个出现一次的则不可能被3整除。

function tten(num) {
    let str = num + ''
    let n = 0
    let dotIndex = str.indexOf('.')
    let intNum = dotIndex > 0 ? str.substr(0, dotIndex) : str
    let floatNum = dotIndex > 0 ? str.substr(dotIndex + 1, str.length - dotIndex) : ''

    for (let i = 0; i < intNum.length; i++) {
        n +=  intNum[i]*Math.pow(2, intNum.length - i - 1)
    }

    for (let i = 0; i < floatNum.length; i++) {
        n +=  floatNum[i]*Math.pow(2, -1 * (i + 1))
    }
    return n
}
function add(num1, num2) {
    num1 = num1 + ''
    num2 = num2 + ''
    let len1 = num1.length
    let len2 = num2.length
    let ret = []
    while (len1 > 0 || len2 > 0) {
        let n1 = num1[len1 - 1] || 0
        let n2 = num2[len2 - 1] || 0
        ret.unshift(n1 / 1 + n2 / 1)
        len1--
        len2--
    }
    return ret.join('')
}
function getNum(arr) {
    let tmp = '0'
    for (let i = 0; i < arr.length; i++) {
        tmp = add(tmp, ttwo(arr[i]))
    }
    let ret = []
    for (let i = 0; i < tmp.length; i++) {
        if (tmp[i] == '0') {
            ret.push(0)
        } else {
            if (tmp[i] % 3 == 0) {
                ret.push(0)
            } else {
                ret.push(1)
            }
        }
    }
    return tten(ret.join(''))
}

权限

权限前置条件：每个权限都是二进制表示，为2的n次方。如0001，0010，0100，1000。那么：

1，或，可以添加权限

2，与，可以判断权限

3，异或，可以删除权限。其实本部操作会变成toggle操作，有权限删除，无权限则增加。真正的删除是&(~code)，就是除了权限位其他都为1，然后进行与操作。