二进制数中1的个数

算法一：[ 右移统计 ]

一个直接的做法是，通过$n\&1$来统计当前$n$的最低位是否为$1$，同时每次直接对$n$进行无符号右移操作(即右移并高位补0)，直到$n=0$时，表示已经将所有的1统计完成。这样的做法，只会循环到最高位的1。

java代码：

public class Solution {
    public int hammingWeight(int n) {
        int ans = 0;
        while (n != 0) {
            ans += (n & 1);
            n >>>= 1;  // java 中的无符号右移为 >>>
        }
        return ans;
    }
}

算法二：$n\&(n-1)$

观察这个运算：$n\&(n-1)$，其运算结果恰好把$n$的二进制位中的最低位的$1$变为$0$之后的结果。比如：$11\&(11-1)=(1011{)}_2\&(1010{)}_2=(1010{)}_2=10,6\&(6-1)=(110{)}_2\&(101{)}_2=(100{)}_2=4$等等。这样我们就可以利用这个位运算的性质加速我们的检查过程，在下面的代码中，我们不断让当前的$n$与$n-1$做与运算,直到$n$变为$0$即可。因为每次运算会使得$n$的最低位的$1$被翻转，因此运算次数就等于$n$的二进制位中$1$的个数。

java 的代码：

public class Solution {
    public int countOne(int n) {
        int ret = 0;
        while (n != 0) {
            n &= n - 1;
            ret++;
        }
        return ret;
    }
}

复杂度分析

时间复杂度：$O(\log n)$，循环次数等于$n$的二进制位中$1$的个数，最坏情况下$n$的二进制位全部为$1$。我们需要循环$\log n$次。
空间复杂度：$O(1)$，我们只需要常数的空间保存若干变量。

算法三：[ lowbit ]

我们想直接只对位数为$1$的二进制位进行统计处理，设$lowbit=n\&(-n)$($-n$的运算是：先将$n$的各二进制位取反，后再加$1$)，则$lowbit$等于二进制中$n$最低位的$1$的权值(比如$12=(1100{)}_2$，则$lowbit=(0011{)}_2+(0001{)}_2=(0100{)}_2=4$)，于是$n-lowbit$的运算结果就相当于把最低位的$1$消去了，重复这个过程，直到$n$变为$0$即可，消去的次数就是$n$的二进制数中$1$的个数。

java代码：

public class Solution {
    public int countOne(int n) {
        int ans = 0;
        for (int i = n; i != 0; i -= lowbit(i)) ans++;
        return ans;
    }
    int lowbit(int n) {
        return n & -n;
    }
}

算法四：分治法

对于二进制数$num$，注意到：它的位1的个数等于所有位的值相加的结果。 比如$(10110101{)}_2⟹1+0+1+1+0+1+0+1=5$。我们可以将8个位的求和分解成4个相邻的位的求和，然后再将4个中间结果分解成2个相邻的求和，即$(10110101{)}_2⟹(1+0)+(1+1)+(0+1)+(0+1)=((1+0)+(1+1))+((0+1)+(0+1))=5$。下面给出32位数的求解算法。

java代码：

public int countOne(int num) { 
        num = (num & 0x55555555) + ((num >>> 1) & 0x55555555); // 每2个数位1组 , 每组内相加的结果 暂存在 每组的 2位二进制数 中
        num = (num & 0x33333333) + ((num >>> 2) & 0x33333333); // 将上一次每组的运算结果 每2个划分1组 , 新组每组内相加的结果 暂存在 每组的 4位二进制数 中
        num = (num & 0x0F0F0F0F) + ((num >>> 4) & 0x0F0F0F0F); // 将上一次每组的运算结果 每2个划分1组 , 新组每组内相加的结果 暂存在 每组的 8位二进制数 中
        num = (num & 0x00FF00FF) + ((num >>> 8) & 0x00FF00FF); // // 将上一次每组的运算结果 每2个划分1组 , 新组每组内相加的结果 暂存在 每组的 4位二进制数 中
        num = (num & 0x0000FFFF) + ((num >>> 16) & 0x0000FFFF); // // 将上一次每组的运算结果 每2个划分1组 , 新组每组内相加的结果 暂存在 每组的 32位二进制数 中
        return num; // 最后一次运算只有一组 , 组内2个 16位二进制数相加 的结果就是最终的答案
    }

复杂度分析

该算法以上的三种解法的时间复杂度都是$O(k)$的，其中$k$为n的二进制数的数据类型的位数。必须是2的幂。比如如果是int，在java中就是32位。
而该算法的时间复杂度为$O(\log k)$。

二进制数中前导0的个数

可使用二分法快速求解n的二进制数中前导0的数目：
初始时设前导0的数目clz=0，首先判断n前半部分是否全为零，如果是，则将clz加上前半部分的长度，然后将后半部分作为处理对象，否则将前半部分作为处理对象。重复以上操作直到处理的对象长度为1，直接判断是否有零，有则将 clz加1。
下面给出32二进制数的求解算法。

public int lengthClz(int num) {
        int clz = 0;
        if ((num >> 16) == 0) {
            clz += 16;
            num <<= 16;
        }
        if ((num >> 24) == 0) {
            clz += 8;
            num <<= 8;
        }
        if ((num >> 28) == 0) {
            clz += 4;
            num <<= 4;
        }
        if ((num >> 30) == 0) {
            clz += 2;
            num <<= 2;
        }
        if ((num >> 31) == 0) {
            clz += 1;
        }
        return clz;
}

API相关

Linux 平台上的 C++可以用__builtin_clz、 __builtin_ctz 和 __builtin_popcount等这类函数来求出二进制前导0的数目、二进制后导0的数目和二进制1的个数。
Java 中 Integer 的方法 Integer.numberOfLeadingZeros 、Integer.numberOfTrailingZeros 、Integer.bitCount 、Integer.highestOneBit 、Integer.lowestOneBit 分别计算二进制前导0的数目、二进制后导0的数目、二进制1的个数、二进制最高位1所在的权值和二进制最低位1所在的权值。

快速幂算法

这算法来自于leetcode上的题目：50. Pow(x, n)

思路：
  考 虑 将   n   表 示 成 二 进 制 的 形 式 ， 即   n = a m 2 m + a m − 1 2 m − 1 + ⋯ + a i 2 i + ⋯ + a 1 2 + a 0    (   0 ≤ i ≤ m   ,   a i ∈ { 0   , 1 }   )   ， 则   x n = x a 0 ⋅ x a 1 2 ⋅ x a 2 2 2 ⋯ x a i 2 i ⋯ x a m 2 m = ( x ) a 0 ⋅ ( x 2 ) a 1 ⋅ ( x 2 2 ) a 2 ⋯ ( x 2 i ) a i ⋯ ( x 2 m ) a m   ， 其 中   ( x 2 i )   的 形 式 很 容 易 通 过 迭 代 逐 步 算 出 并 叠 加 ，   a i   也 容 易 通 过   n   逐 次 除 以   2   取 整 得 到 ， 于 是 就 有 了 下 面 的 算 法 。 ,考虑将,n,表示成二进制的形式，即,n=a_m2^m+a_{m-1}2^{m-1}+cdots+a_i2^i+cdots+a_12+a_0,,(,0 le i le m,,,a_i in {0,,1},),，\则,x^n = x^{a_0}cdot x^{a_12}cdot x^{a_22^2} cdots x^{a_i2^i} cdots x^{a_m2^m}=(x)^{a_0}cdot (x^2)^{a_1}cdot(x^{2^2})^{a_2}cdots (x^{2^i})^{a_i}cdots (x^{2^m})^{a_m},，\其中,(x^{2^i}),的形式很容易通过迭代逐步算出并叠加，,a_i,也容易通过,n,逐次除以,2,取整得到，于是就有了下面的算法。 考虑将n表示成二进制的形式，即n=am​2m+am−1​2m−1+⋯+ai​2i+⋯+a1​2+a0​(0≤i≤m,ai​∈{0,1})，则xn=xa0​⋅xa1​2⋅xa2​22⋯xai​2i⋯xam​2m=(x)a0​⋅(x2)a1​⋅(x22)a2​⋯(x2i)ai​⋯(x2m)am​，其中(x2i)的形式很容易通过迭代逐步算出并叠加，ai​也容易通过n逐次除以2取整得到，于是就有了下面的算法。

class Solution {
public:
    double quickMul(double x, long long N) {
        double ans = 1.0;
        // 贡献的初始值为 x
        double x_contribute = x;
        // 在对 N 进行二进制拆分的同时计算答案
        while (N > 0) {
            if (N % 2 == 1) {
                // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                ans *= x_contribute;
            }
            // 将贡献不断地平方
            x_contribute *= x_contribute;
            // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
            N /= 2;
        }
        return ans;
    }

    double myPow(double x, int n) {
        long long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
};

事实上，由博客《初等数论》：整除性概念及其性质、质数与合数，该算法也可推广到k进制的情况，并非二进制所独有的。
比如下面就给出了3进制的写法。

class Solution {
public:
    double qpow(double a, long long b){
        double res = 1.0;
        while(b){
            if(b % 3 == 1)res *= a;
            if(b % 3 == 2)res *= a * a;
            a *= a * a;
            b /= 3;
        }
        return res;
    }
    
    double myPow(double x, long long n) {
        if(n == 0) return 1.0;
        if(n > 0) return qpow(x,n);
        if(n < 0) return 1/qpow(x,-n);
        return 1.0;
    }
};

快速乘算法

在快速幂的算法的基础上将 乘法运算 改为 加法运算 即可。
可知，「快速乘」算法与「快速幂」类似，前者通过加法实现乘法，后者通过乘法实现幂运算。

29. 两数相除

矩阵快速幂算法

矩阵快速幂算法 基于 快速幂算法 的思想 ，其中 快速幂算法 中的数值1 相当于 矩阵快速幂算法 中的 单位矩阵 ，快速幂算法中的乘法 相当于 矩阵快速幂算法中 的矩阵乘法。

	public int[][] fastPow(int[][] matrix, int n) { // 矩阵快速幂
        int m = matrix.length;
       	int[][] res = new int[m][m];
        int[][] curr = matrix;

        for (int i = 0; i < m; ++i) {   // 初始化 res 为 单位矩阵
            res[i][i] = 1;
        }
        for (int i = n; i != 0; i >>= 1) {
            if ((i % 2) == 1) {
                res = multiply(curr, res, mod);
            }
            curr = multiply(curr, curr, mod);
        }
        return res;
    }

    public int[][] multiply(int[][] matrixA, int[][] matrixB) {  // 矩阵乘法
        int m = matrixA.length;
        int n = matrixB[0].length;
        int[][] res = new int[m][n];

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                res[i][j] = 0;
                for (int k = 0; k < matrixA[i].length; ++k) {
                    res[i][j] = (res[i][j] + matrixA[i][k] * matrixB[k][j]);
                }
            }
        }
        return res;
    }

1220. 统计元音字母序列的数目

用二进制位来标记状态

在 动态规划 中

题目

• 1994. 好子集的数目
• 1787. 使所有区间的异或结果为零 ( 其中 动态规划中关于状态转移方程的优化 有赞！)
• 78. 子集
• 318. 最大单词长度乘积
• 1723. 完成所有工作的最短时间 ( 其中的 关于二进制数 j 表示的状态的子集的遍历算法 很赞！ )
• 552. 学生出勤记录 II
• 600. 不含连续1的非负整数

在 递归+回溯 中

• 37. 解数独
• 51. N 皇后 ( 其中的 行下标与列下标的关系 、左移和右移操作 很赞！)
• 847. 访问所有节点的最短路径
• 1239. 串联字符串的最大长度

在 遍历 中

• 1707. 与数组中元素的最大异或值
• 187. 重复的DNA序列
• 784. 字母大小写全排列
• 1239. 串联字符串的最大长度
• 526. 优美的排列
• 421. 数组中两个数的最大异或值
• 1601. 最多可达成的换楼请求数目

位运算

• 137. 只出现一次的数字 II
• 260. 只出现一次的数字 III
• 201. 数字范围按位与
• 1310. 子数组异或查询
• 1318. 或运算的最小翻转次数
• 1734. 解码异或后的排列

End

未完待续…

最后

以上就是寂寞金鱼为你收集整理的Leetcode上常见的与二进制有关的算法二进制数中1的个数二进制数中前导0的个数API相关快速幂算法用二进制位来标记状态End的全部内容，希望文章能够帮你解决Leetcode上常见的与二进制有关的算法二进制数中1的个数二进制数中前导0的个数API相关快速幂算法用二进制位来标记状态End所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。