408. 二进制求和

题目

给定两个二进制字符串,返回他们的和(用二进制表示)。

http://www.lintcode.com/zh-cn/problem/add-binary/

分析

二进制加法,主要考虑一下两个字符串长度不等的处理,以及进位。

代码


public class Solution {
    
    int toInt(char c) {
        return c == '1' ? 1 : 0;
    }
    
    char toChar(int i) {
        return i == 0 ? '0':'1';
    }
    /**
     * @param a: a number
     * @param b: a number
     * @return: the result
     */
    public String addBinary(String a, String b) {
        // write your code here
        StringBuffer sb = new StringBuffer();
        
        char[] x = a.toCharArray();
        char[] y = b.toCharArray();
        
        int i = x.length - 1, j = y.length -1;
        
        int inc = 0;
        
        for(; i >= 0 && j >=0; i--, j--) {
            int r = inc + toInt(x[i]) + toInt(y[j]);
            inc = 0;
            if (r >= 2) {
                inc = 1;
                r -= 2;
            }
            sb.insert(0, toChar(r));
        }
        
        if(inc == 1) {
            if( (i < 0) && (j < 0) ) {
                sb.insert(0, '1');
            } else if( (i >= 0) && (j < 0) ) {
                for(; i >=0; i--) {
                    int r = inc + toInt(x[i]);
                    inc = 0;
                    if (r >= 2) {
                        inc = 1;
                        r -= 2;
                    }
                    sb.insert(0, toChar(r));
                }
                
                if(inc == 1) {
                    sb.insert(0, '1');
                    inc = 0;
                }
            } else if( (i < 0) && (j >= 0) ) {
                for(; j >= 0; j--) {
                    int r = inc + toInt(y[j]);
                    inc = 0;
                    if (r >= 2) {
                        inc = 1;
                        r -= 2;
                    }
                    sb.insert(0, toChar(r));
                }
                
                if(inc == 1) {
                    sb.insert(0, '1');
                    inc = 0;
                }
            }
        }
        
        if ( i >= 0) {
            for(; i >= 0; i--) {
                sb.insert(0, x[i]);
            }
        }
        
        if (j >= 0) {
             for(; j >= 0; j--) {
                sb.insert(0, y[j]);
            }
        }
        
        return sb.toString();
    }
}
Show Comments

Get the latest posts delivered right to your inbox.