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.