位运算基础：程序中的所有数据在计算机内存中都是以二进制形式存储的，而位运算就是直接对内存中整数的二进制进行运算，由于运算直接在内存中进行，不需要转成十进制，所以处理速度非常快。普通位操作x&1===0//判断奇偶校验x&(x-1)//清空最右边的1x&-x//得到最右边的1191.1的位数(easy)写一个函数，输入为无符号整数（二进制字符串形式），返回其二进制表达式中为'1'数的位数（也称为汉明权重）。提示：请注意，在某些语言中，例如Java，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为整数的内部二进制表示形式是相同的，无论它是有符号的还是无符号的。在Java中，编译器使用二进制补码表示有符号整数。因此，在上面的示例3中，输入表示有符号整数-3。示例1：输入：00000000000000000000000000001011输出：3解释：在输入的二进制串00000000000000000000000000001011中，共有三位为'1'。示例2：输入：00000000000000000000000010000000输出：1解释：在输入的二进制串00000000000000000000000010000000中，共有一位为'1'。示例3：输入：11111111111111111111111111101输出：31解释：在输入的二进制串111111111111111111111111111101中，共有31位为'1'。提示：输入必须是长度为32的二进制字符串。进阶：如果这个函数被多次调用，你会如何优化你的算法？方法一：循环每个二进制位思路：直接循环二进制中的每个位，判断是否为1，统计1的个数。复杂度分析：时间复杂度O(k)，k=32。空间复杂度为O(1)Js：varhammingWeight=function(n){letret=0;for(leti=0;i<32;i++){if((n&(1<0，同时剔除唯一1，则为0。复杂度：时间复杂度O(1)。空间复杂度O(1)Js:varisPowerOfTwo=function(n){returnn>0&&(n&(n-1))===0;};方法二、是否是2的最大幂的约数思路：2的最大幂为2^30=1073741824，判断n是否是2^30的约数即可。复杂度：时间复杂度O(1)。空间复杂度O(1)js:varisPowerOfTwo=function(n){constMAX=1<<30;返回n>0&&MAX%n===0;};338.Bitcount(easy)foryou一个整数n，对于0<=i<=n中的每个i，统计其二进制表示中1的个数，返回一个长度为n+1的数组ans作为答案。示例1：输入：n=2输出：[0,1,1]解释：0-->01-->12-->10示例2：输入：n=5输出：[0,1,1,2,1,2]解释:0-->01-->12-->103-->114-->1005-->101Tips:0<=n<=105Advanced:很容易实现时间A复杂度为O(nlogn)的解，你能用一次线性时间复杂度O(n)解决这个问题吗？你能在不使用任何内置函数的情况下解决这个问题吗？（比如C++中的__builtin_popcount）方法一、循环思路：循环0-n，计算二进制中每个数中1的个数。复杂度：时间复杂度O(nk)，k为整数，统计二进制1的复杂度，最坏情况下k=32。空间复杂度为O(1)js：varcountBits=function(n){constbits=newArray(n+1).fill(0);for(leti=0;i<=n;i++){bits[i]=countOnes(i);}返回位};constcountOnes=(x)=>{让ones=0;while(x>0){x&=(x-1);一个++；}返回的；}方法二、动态规划思想：bits[i]表示i的二进制中1的个数，则bits[i-1]为bits[i]去掉一个1后的值，i&(i-1)为去掉1的最低位。所以状态转移方程为bits[i]=bits[i&(i-1)]+1，可以连续计算出1-n中每个二进制数中1的个数复杂度：时间复杂度O(n)。空间复杂度为O(1)Js：varcountBits=function(n){constbits=newArray(n+1).fill(0);for(leti=1;i<=n;i++){bits[i]=bits[i&(i-1)]+1;}返回位;};2??68。缺失数字（简单）给定一个数组nums，其中包含[0,n]中的n个数字，找出[0,n]数组中没有出现在该范围内的数字。示例1：输入：nums=[3,0,1]输出：2解释：n=3，因为有3个数，所有数都在[0,3]范围内。2是缺失的数字，因为它没有出现在nums中。示例2：输入：nums=[0,1]输出：2解释：n=2，因为有2个数字，所有数字都在[0,2]范围内。2是缺失的数字，因为它没有出现在nums中。示例3：输入：nums=[9,6,4,2,3,5,7,0,1]输出：8解释：n=9，因为有9个数字，所有数字都在[0,9]里面。8是缺失的数字，因为它没有出现在nums中。示例4：输入：nums=[0]输出：1解释：n=1，因为有1个数字，所以所有数字都在[0,1]范围内。1是缺失的数字，因为它没有出现在nums中。提示：n==nums.length1<=n<=1040<=nums[i]<=nnumsnnums中的所有数字都是唯一的进阶：你能实现一个在线性时间内只使用额外常数空间的算法来解决这个问题吗？方法一、排序：在循环数组中，看下一个数是否比前一个数大1。方法二、哈希表：将数组中的元素插入到哈希表中，然后循环遍历0~nums.length-1就是哈希表中的所有数字方法三、求和：0～nums.length-1求和减去nums中的和方法四：位运算思路：同数异或为0复杂度：时间复杂度O(n)，空间复杂度O(1)js://nums=[3,0,1]//index=0,1,2varmissingNumber=function(nums){letmissing=nums.lengthfor(leti=0;i
