public static String twosComplete(String bits) { String newBits = ""; for (int i = 0; i < bits.length(); i++) { if (newBits.charAt(i) == '0') { newBits += "1"; } else { newBits += "0"; } } String res = ""; int carry = 1; for (int i = bits.length() - 1; i >= 0; i--) { int num = Integer.valueOf(bits.charAt(i)); int sum = num + carry; if(sum == 2){ res = "0" + res; carry = 1; } else { res = "1" + res; carry = 0; } } return res; }

O(n)