位运算基础：程序中的所有数据在计算机内存中都是以二进制形式存储的，而位运算就是直接对内存中整数的二进制进行运算，由于运算直接在内存中进行，不需要转成十进制，所以处理速度非常快。普通位操作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;};389.给定两个仅包含小写字母的字符串s和t，找出差异（简单）。字符串t是从字符串s中随机重新排列的，并在随机位置添加了一个字母。请找到在t中添加的字母。示例1：输入：s="abcd",t="abcde"输出："e"解释：'e'是添加的字母。示例2：输入：s="",t="y"输出："y"提示：0<=s.length<=1000t.length==s.length+1sandt仅包含小写字母方法1。计数思路：循环字符串s，统计每个字符的个数。循环串t中每出现s中的一个字符，对应的字符数就会减1，如果减到小于0，那么这个字符就是答案。Complexity：时间复杂度O(n)，其中n为字符串的长度。空间复杂度O(k)，k是字符集的大小js:varfindTheDifference=function(s,t){constcnt=newArray(26).fill(0);for(constchofs){//循环字符串s统计每个字符的个数cnt[ch.charCodeAt()-'a'.charCodeAt()]++;}for(constchoft){//循环字符串t在s中出现一次将对应的字符数减1cnt[ch.charCodeAt()-'a'.charCodeAt()]--;if(cnt[ch.charCodeAt()-'a'.charCodeAt()]<0){//如果字符减到小于0，这个字符就是答案returnch;}}返回'';};方法二、求和思路：统计字符串s和t中Unicode字符的总和，两个总和的差为不同的字符复杂度：时间复杂度O(n)。空间复杂度O(1)js:varfindTheDifference=function(s,t){letas=0,at=0;for(leti=0;i01-->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;}返回位;};视频讲解：传送门
