位运算基础：程序中的所有数据在计算机内存中都是以二进制形式存储的，而位运算就是直接对内存中整数的二进制进行运算，由于运算直接在内存中进行，不需要转成十进制，所以处理速度非常快。普通位操作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;}返回位;};视频讲解：传送门
