# Implementing my own Integer.toBinaryString(int n) method

Posted on

Problem

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?

Solution

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.