二进制的的加法

二进制加法

分析：

这道题目当中的二进制数字是以字符串的形式来保存的，如果将字符串转化为位int类型或者long long 类型，string 的长度特别长的时候，那么就会超出时间限制

参考解法

加法操作只能针对两个字符串进行。可以参照十进制的加法来完成。回忆一下小学学习的十进制加法，首先将字符的右端对齐，然后从他们个位开始从右向左相加同一位置的两个数字，如果有进位要进一位。

二进制加法

1. 获取字符串的长度-从字符串的右边开始相加
2. 逢二进1
3. 当两个数位加起来等于2时就要产生进位

超级小白思路代码

class Solution {
public:
    string addBinary(string a, string b) {
        int lena=a.length()-1;
        int lenb=b.length()-1;
        string s;
        //记录当前是否有进位
        int current=0;
        while(lena>=0||lenb>=0){
            //由于是以字符的形式，所以要减去字符0来获取数字再进行相加，同时还要记录进位
            int recordA= lena>=0? a[lena--]-'0':0;
            int recordB= lenb>=0? b[lenb--]-'0':0;
            int sum=recordA+recordB+current;
            current=sum>=2?1:0;
            sum=sum>=2?sum-2:sum;
            //上面减去的是0字符串，所以要在下面加'0' 变成字符串形式
            s.push_back(sum+'0');
        }
        //如果最后产生了进位的话，然后再把进位加进去
        if(current==1){
            s.push_back('1');
        }
        //因为我们是从最右边开始计算的，所以要对其进行反转
        reverse(s.begin(),s.end());
        return s;
        
    }
};

前n个数字中二进制中的个数

剑指 Offer II 003. 前 n 个数字二进制中 1 的个数

分析

高效方法

i&（i-1）将整数最右边的1变成0
整数减去1，即其最右边的1变成0
如果右边还有0，则右边所有的0都变成1
其左边的值不发生变化
比如 1000
1000-1=0111
1000&0111=0000
那么其1的个数就等于 其 i&(i-1)+1
可以再举一个例子
101
101-1=100
101&100=100
101中的个数就等于 100当中1的个数加上1

所以在这里我们就得到了一个方程其
i当中1个个数=i&(i-1)+1
那这样以来我们就可以利用这个方程来进行求解

思路清晰上代码

class Solution {
public:
    vector<int> countBits(int n) {
        //同时在定义arr的时候要给长度
        vector<int>arr(n+1);
        //在这里要注意i==0得时候是0,所以在for 循环得时候要从1开始
        arr[0]=0;
        for(int i=1;i<=n;i++){
            arr[i]=arr[i&(i-1)]+1;
        }
        return arr;
    }
};

最后

以上就是大方香水为你收集整理的剑指Offer专项突破版-二进制加法&&前n个数字中二进制中1的个数二进制的的加法前n个数字中二进制中的个数的全部内容，希望文章能够帮你解决剑指Offer专项突破版-二进制加法&&前n个数字中二进制中1的个数二进制的的加法前n个数字中二进制中的个数所遇到的程序开发问题。

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