Implementing my own Integer.toBinaryString(int n) method

Question

Our senior developer gave us (trainees/jr. developers) a small exercise and that is to make our own Integer.toBinaryString(int n) implementation. This is the answer I came up with. I would just like to hear comments/suggestions/opinions on this. Especially, if there is a way to optimize my answer.

public static String toBinaryString(int n){
 String binary = "";
 if(n == 0) return "0";
 // I know, I'm desperate :(
 if(n == Integer.MIN_VALUE) return "10000000000000000000000000000000";
 if(n < 0){
 // Get the positive equivalent
 int val = n * -1;
 // Convert into binary
 String initial = toBinaryString(val);
 String inverted = "";
 // Get 1's complement
 for(char chars : initial.toCharArray()){
 inverted += String.valueOf(((chars == '1') ? '0' : '1'));
 }
 int carry = 0;
 /*Check least significant bit.
 If 0, simply change it to 1.
 If 1, perform addition of 0b1*/
 if(inverted.charAt(inverted.length()-1) == '1'){
 boolean carriedOver = false;
 for(char chars : new StringBuilder(inverted).reverse().toString().toCharArray()){
 if(carriedOver){
 binary = chars + binary;
 continue;
 }
 if(carry > 0){
 if(chars == '1'){
 binary = "0" + binary;
 continue;
 }else{
 binary = "1" + binary;
 carriedOver = true;
 continue;
 }
 }
 binary = "0" + binary;
 carry += 1;
 }
 }else{
 StringBuilder sb = new StringBuilder(inverted);
 sb.setCharAt(inverted.length()-1, '1');
 binary = sb.toString();
 }
 return String.format("%32s", binary).replace(" ", "1");
 }
 // Convert to binary
 while(n > 0){
 binary = (n & 1) + binary;
 n /= 2;
 }
 return binary;
 }

If you were our senior developer, would you accept this as a valid answer? Why? Why not?

• Sophie Swett: I think your logic for while (n > 0) will work for negative numbers, too. Have you tried removing your if (n < 0) block and changing while (n > 0) to while (n != 0)?

Answer 1

The exercise calls for bit shifting. Only bit shifting, nothing else, really. Your main tools are:

• checking if the last bit is 0 or 1 with: num & 1
• then shift by one bit to the right: num >> 1

A naive implementation could go like this:

 String result = "";
 while (num > 0) {
 result = (num & 1) + result;
 num >>= 1;
 }
 return result;

But that won't work for negative numbers. A simple tweak can fix that:

 String result = "";
 while (num != 0) {
 result = (num & 1) + result;
 num >>>= 1;
 }
 return result;

Instead of the signed bit shift operator >>, we need to use the unsigned bit shift operator >>>, to shift the negative bit just like all the others. And we changed the condition to != 0 instead of > 0.

But this won't work for 0. But only for 0. So you can add a simple condition to handle that.

Lastly, string concatenation is inefficient. We can do better using a StringBuilder. But a StringBuilder only has an append method, doesn't have prepend. It has an insert method, but that won't be efficient. A simple solution is to append the bits and reverse at the end.

String toBinaryString(int num) {
 if (num == 0) {
 return "0";
 }
 StringBuilder builder = new StringBuilder(32);
 while (num != 0) {
 builder.append(num & 1);
 num >>>= 1;
 }
 return builder.reverse().toString();
}

In any case, the StringBuilder is not a critical piece here. You could use a char[] with 32 elements to store the digits, and transform that to a string to return.

• saluyotamazing: Right! The unsigned shift operator! I always had trouble understanding it. Now, I understand what it does. Thank you!