关于位运算的一些算法

位运算是把数字用二进制表示之后,对每一位上 0或者1的运算。位运算相关的题目一般也经常出现在面试中。下面我们来介绍一些关于位运算的题目

说明本章同时使用了python和 js代码

位运算介绍

平时的数值操作,其实是要先转换为二进制,计算机才能知道你输入的是什么的？位运算是底层的运算操作,所以速度往往是最快的(相比四则运算),位运算大概分两类 : ** 位逻辑运算符 ** 位移运算符

位逻辑运算符

& 与
| 或
~ 取反
^ 异或

位移动运算符

<< 右移
>> 左移
>>> 无符号右移

好,show me code ,让我们进入实战

出现一次的数

题目：在其他数都出现两次的数组中找到只出现一次的那个数要求:时间复杂度 O(N) 空间复杂度O(1)

要求空间复杂度为O(1) 也就是说,只能用有限的变量,那该怎么做呢？在不知道位运算之前可能已经把循环遍历写出来了,但题目要去空间复杂度为 O(1),所以不能用额外的空间记录出现的次数。
仔细看题目,其他数都是出现两次,只有一个数出现一次
在解决这问题前,我们先了解一下异或^ 运算

异或运算

二进制中两个位相同为 0 , 相异为 1
规律1:任何整数 n 与 0 异或总等于其本身
规律2:多个数异或操作,遵循交换律和结合律
规律3:任何整数 n 与其本身异或为0

假设一个数组
Arr = [3,2,4,2,4,3,5,1,5] 如果把数组中所有元素都有异或 3 ^ 2 ^ 4 ^ 2 ^ 4 ^ 3 ^ 5 ^ 1 ^ 5 由于遵循交换律会等于
3 ^ 3 ^ 4 ^ 4 ^ 2 ^ 2 ^ 5 ^ 5 ^ 1 == 1 这样我们就找到了那个数了

function OnlyAppearOnce (arr) {
 let start = 0 ;
 for(let item of arr) {
     start = item ^ start ;
 }
 return start ;

}

出现一次的两个数

是不是还挺简单的?热身结束,来一点升级版呗
题目和上一题很像
题目: 一个整形数组除了两个数字之外 , 其他的数字都出现了两次 , 设计程序找出这两个只出现一次的数字要求 : 时间复杂度是 O(n) 空间复杂度 O(1)

只是把找一个数变成了找两个。好的,我们用一下上题的思路假设一个数组
Arr = [3,2,4,2,4,3,5,1,5,7]
异或一下
res = 3 ^ 3 ^ 4 ^ 4 ^ 2 ^ 2 ^ 5 ^ 5 ^ 1 ^ 7 == 1 ^ 7
得到的结果是我们要找的两个数的异或结果 1 ^ 7 , 好像没什么用啊 , 我咋知道具体哪两数异或成它的
我们分析一下, 既然是两个不同的数,那么异或结果一定不是 0, 也就是说 res 一定不为 0 , 我们把这个数转为二进制 , 一定有些位是 1 , 我们可以找到其中一个1的位置(就找最靠近右边的1吧),这很重要！
1 : 0001
7 : 0111
6 : 0110 我们找到最右边的 index = 1
那么我们是不是可以以这个为依据 , 来分辨这两个数 , 第1位为 0 是1那个数 , 第1位为1 是7那个数 , 至于其他数会被自己都异或为 0
OK,show me code

function FindNumsAppearOnce (data) {
 let len = data.length ;
if(len < 2) return ;

// get num1 ^ num2 
let res = 0 ;
for(let i = 0 ; i < len ; i++) {
    res = res ^ data[i]
}

// get index of the first bit , which is 1 in res
let indexOf1 = FindFirstBitIs1(res) ;

let num1 = num2 = 0 ;
for(let j = 0 ; j < len ; j++) {
    // divide the numbers in data into two groups
    // the indexOf1 bit of numbers in the first group is 1
    // while in the second group is 0
    if(IsBit1(data[j] ,indexOf1)) {
        num1 ^= data[j]
    } else {
        num2 ^= data[j]
    }
}
return [num1 , num2]
}
 // Find the index of first bit which is 1 in num 
function FindFirstBitIs1(num) {
 let indexBit = 0 ;
 while ((num & 1) == 0) {
     num >>= 1 ;
     indexBit ++ ;
 }
 return indexBit ;
}
// Is the indexBit of num 1 ?
function IsBit1(num , indexBit) {
    num = num >> indexBit ;
    return (num & 1) ;
}

二进制中1的个数(剑指offer原题)

输入一个整数 , 输出该二进制表示中 1 的个数 .
其中负数用补码表示
好吧,我承认我忘记什么是补码了 , 哈哈哈
在解决这个问题之前,我们可以大致的了解一下啥是补码。

负数用二进制是怎么表示的?

在二进制码中,为了区分正负数,采用最高位是符号位的方法来区分,正数的符号位 0 ,负数的符号位为 1,剩下的就是这个数的绝对值部分。可以采用原码,反码,补码3种形式来表示绝对值部分
原码最简单，也最好理解。原码就是绝对值的二进制数形式 , 例如 +7的 8位二进制原码是 0000 0111
补码: 但对于二进制运算而言 , 原码的运算不够方便 ,在计算机中 , 通常都是采用补码形式 补码表示就是在原码表示的基础上取反然后加 1 。

-1: 1 的原码表示是 0000 0001 ,>取反是 1111 1110 , 然后再加 1 , 就是 1111 1111

负整数为什么采用补码呢

如果是补码表示 : 
1 -> 00000001
-1 -> 11111111
+
0 -> 00000000

OK,扯了这么多,该回到题目了,其实仔细思考一下,我们很快能形成一个思路:先判断整数二进制表示中最右边是不是1。接着把输入的整数右移一位,此时原来处于从右边数起的第二位被移到最右边了,再判断是不是1,这样每一次移动一位,直到整个整数变为 0 为止,那么怎么判断一个整数最右边是不是1.很简单,只要把整数和 1 做 与运算看结果是不是0 就直到了
好的,show me code

//解法1
function NumberOf1_updata (n) {
//计数器
let count = 0 ;
while(n) {
    if(n & 1) {
        count ++ ;
    }
    n >>= 1 ;
}
return count ;

}

但是如果我们输入的是负数的话,就很有问题了。这是因为位移前是个负数的话,仍然要保证位移后是个负数,因此位移后的最高位会设为1,这样 n 最终会变为 -1 ,而陷入死循环
来看看升级版本

//解法2
function NumberOf1 (n) {
 // 计数器
 let count = 0 ;
 let flag = 1 ;
while (flag) {
    if(n & flag) {
        count ++ ;
    }
    flag <<= 1  ; 
}
return count ;

}

我们不移动 n ,而是左移 flag , 这样判断 n 中有多少个 1,必须提醒一下,flag 不会一直大下去, 这个循环会执行 32次

如果知道了这种写法其实也差不多了,不过下面还有好的一些解法,可以瞧一瞧啊

//解法3
function NumberOf1_updata (n) {
//计数器
let count = 0 ;
while(n) {
    if(n & 1) {
        count ++ ;
    }
    n >>>= 1 ;
}
return count ;

}

与解法1唯一的区别是: 我们采用的是无符号右移 ,这样位移后的最高位就会被设为0

还有一种哦!
我们考虑,把一个整数最右边一个1变为0,还可以怎么做呢?
如果我们把一个整数减去1, 再和原整数做与运算, 会把该整数最右边一个 1 变成0 。那么一个整数的二进制表示中有多少个1 , 就可以进行多少次这样的操作。

//解法4 (最优解)
function NumberOf1_best (n) {
    let count = 0 ;
    while(n) {
        count ++ ;
        n = n & (n - 1)
    }
    return count ;
}

被去掉的两个数(个人感觉是最难的)

最后再来一个
似乎是腾讯的面试题
题目: 给你 1 到 10w 自然数 , 然后从中随机取掉两个 , 再打乱顺序。要求只遍历一次,求出被去掉的两个数

首先,我们为了方便, 我们就假设我们的数据在
1 - 10 之间吧 , 也就是给你这样一个数组
[1 ,2 ,3, 4, 5, 6, 7, 8, 9, 10] 随机去掉两个数 , 遍历一次 , 把两个数求出来

其实,应该有更好的解法,不过我就标题既然是位运算,那么证明我是用位运算来求解的
思路:假设我们随机去掉了 5 , 6 , 那么数组就变成这样 :
[1 ,2 ,3, 4, 7, 8, 9, 10]
其实,如果我们把 1 - 10 全部异或一下
res1 = 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10
再把另一个数组全部异或一下
res2 = 1 ^ 2 ^ 3 ^ 4 ^ 7 ^ 8 ^ 9 ^ 10
然后再把 res1 与 res2 异或一下
res3 = res1 ^ res2 ;
我们发现 res3 == 5 ^ 6, 然后从这里开始,就与第2题有点像了 ,我们先找出 res3 二进制表示最靠右边的 1的位置 , 然后我们要做的就是这样的事情 :
(res1 ) 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^
( res2) 1 ^ 2 ^ 3 ^ 4 ^ 7 ^ 8 ^ 9 ^ 10
把 res1 异或遍历完后 , 继续异或遍历 res2 ,到这样,其实我们可以看出来 , 这和第二题(出现一次的两个数)其实一样的,有两个数出现一次 , 其他数出现两次