java Bitset solution


  • 0
    Z
    /**
     * Use BitSet to repersent bit strings.
     * 1. Make reversed string -> Bitset
     * 2. Add 2 bit sets, with carry.
     * 3. Bitset -> String : mind corner case "0" bitset .toString returns ""
     */
    public class Solution {
        public String addBinary(String a, String b) {
            BitSet aa = toBitSet(a);
            BitSet bb = toBitSet(b);
            
            return toString(add(aa, bb));
        }
        
        String toString(BitSet s){
            /* To handle corner case: "0" + "0" == "0", bit set does not differenciate empty set "" and "0" when stringfying*/
            int length = s.length() == 0 ? 1: s.length();
            char[] cs = new char[length];
            
            for(int i = 0; i < cs.length; i ++){
                cs[i] = s.get(i) ? '1': '0';
            }
            
            return new StringBuilder(new String(cs)).reverse().toString();
        }
        
        // add two bitsets
        BitSet add(BitSet a ,BitSet b){
            BitSet ret = new BitSet();
            int carry = 0;
            int max = Math.max(a.length(), b.length());
    
            for(int i =0; i < max; i ++){
                int sum = carry + (a.get(i) ? 1:0) + (b.get(i) ? 1:0);
                ret.set(i, 1 == sum % 2);
                carry = sum/2;
            }
            if(carry > 0)
                ret.set(max);
            
            return ret;
        }
        
        // reserve string and convert to bitset.
        BitSet toBitSet(String s){
            String rev = new StringBuilder(s).reverse().toString();
            BitSet ret = new BitSet();
            
            for(int i =0; i < rev.length(); i++){
                ret.set(i, rev.charAt(i) == '1');
            }
            return ret;
        }
    }```

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.