算法：整数

给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。

输入为 非空 字符串且只包含数字 1 和 0。

示例 1:

输入: a = "11", b = "10"
输出: "101"

示例 2:

输入: a = "1010", b = "1011"
输出: "10101"

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/JFETK5

输入: a = "111", b = "10"

n=3

遍历for循环，i=0，i

（1）i=0     i < a.length()   i

（2）i=1     i < a.length()   i

（3）i=2     i < a.length()    所以是1，但是进位为1，所以1+1=2；个位的结果为2%2=0；向前进的数是2/2=1；

（4）i=3 进位为1，所以此位置是1

其中两个数某一个位置的相加，是 carry=carry+a(i)+b(i),结果这个位置的数是carry%2，向前的进位是 carry/2

class Solution {
    public String addBinary(String a, String b) {
        //确定两个字符串里面最大的长度
        int n=Math.max(a.length(),b.length());
        //carry代表进位，初始值为0，代表第一步计算个位时，carry=carry+ai+bi;
        int carry=0;
        StringBuffer sb=new StringBuffer();
        //经过n次计算
        for(int i=0;ii){
                carry=carry+(a.charAt(a.length()-1-i)-'0');
            }
            //如果b在这个位置有数，则加这个数，没有则不加
            if(b.length()>i){
                carry=carry+(b.charAt(b.length()-1-i)-'0');
            }
            //将计算结果写好  各位上的值=(a(i)+b(i)+carry)%2
            sb.append(carry%2);
            //下一个位置的数进位是carry/2
            carry=carry/2;
        }
        if (carry > 0) {
            sb.append('1');
        }
        sb.reverse();        
        return sb.toString();
    }
}

二.​​​​​​前 n 个数字二进制中 1 的个数

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

例1：

输入: n = 2
输出: [0,1,1]
解释: 
0 --> 0
1 --> 1
2 --> 10

例 2:

输入: n = 5
输出: [0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/w3tCBm
 

将这个规则带入

dp[i]=dp[i-1]+1; i为奇数

dp[i]=dp[i/2];      i为偶数

public class Solution {
    public int[] CountBits(int n) {
        int[] dp=new int[n+1];
        dp[0]=0;
        if(n>0){
            dp[1]=1;
        }
        for(int i=2;i<=n;i++){
            if(i%2==0){
                dp[i]=dp[i/2];
            }else{
                dp[i]=dp[i-1]+1;
            }
        }
        return dp;

    }
}