current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 7 down vote favorite
2

I have a function that converts an integer to its binary representation. I am wondering if there is any way I can improve the function.

 public List<string> Conversion(int x)
    {
        var bitConversion = new List<string>();
        var result = x;
        while (result >= 0)
        {
            if (result == 0)
            {
                bitConversion.Add("0");
                break;
            }
            bitConversion.Add((result % 2).ToString(CultureInfo.InvariantCulture));
            result = result / 2;

        }
       bitConversion.Reverse();

       return bitConversion;
    }
share|improve this question

3 Answers 3

up vote 14 down vote accepted

One major improvement would be to just use what is supplied through .NET:

Convert.ToString(int, 2);

where int is your supplied argument.

Convert.ToString Method (Int32, Int32)

Converts the value of a 32-bit signed integer to its equivalent string representation in a specified base.

Note that this returns you a string value like 10000110100001, which is the representation of a binary number. In your code you store them as string representations and in separate entries in your collection, which is not the way a number should be stored. It's like creating an array with values "1" and "2" to represent the number 12.

If this is your intention then you can always work towards that of course but it might be an indication that something else is wrong for needing it like that.

However if you want to stay with your own implementation, there are a few things you could change around:

public List<string> Conversion2(int x)
{
   var bitConversion = new List<string>();
   while (x >= 0)
   {
       if (x == 0)
       {
           bitConversion.Add("0");
           break;
       }
       bitConversion.Add((x % 2).ToString(CultureInfo.InvariantCulture));
       x /=  2;
   }
  bitConversion.Reverse();
  return bitConversion;
}
  • Remove the unnecessary result variable
  • Contract x = x / 2 to x /= 2 (compound assignment operator)
share|improve this answer
    
According to MSDN, List.Add is (amortized) O(1) and List.Insert is O(n). There is no indication for Enumerable.Reverse, but it is supposedly O(n). Performance-wise, your comment about using Insert is not valid. –  Mephy Apr 16 at 16:07
    
@Mephy: thanks, I didn't realize. The more you learn! –  Jeroen Vannevel Apr 16 at 16:15
    
your note is slightly awkward worded now. They won't both run in O(n) because the Insert is already inside a loop. The Add/Revese is O(logn + n) = O(n) and the Insert is O(n logn). Logn because the while loop runs Log(x, 2) times. –  Mephy Apr 16 at 16:18
    
@Mephy: I think I'm following you but to make sure I don't spread any wrong information I removed it. I appreciate the explanation though. –  Jeroen Vannevel Apr 16 at 16:24
up vote 7 down vote

@Jeroen already addressed the main itchy spot, so I'll just add a few meaningless minor points:

  • Indentation is off, the opening brace should line up with the method signature:

    public List<string> Conversion(int x)
{

  • Parameter x would probably have a better, more meaningful name if it were called value.

  • You're returning a List<string>.... and I don't get it. That's violating the Principle of Least Surprise, your user would probably be expecting a string instead.
share|improve this answer
up vote 5 down vote

If you are using lists of strings to represent sequences of bits, the performance does not seem to matter. So if the performance does not matter anyway, one could at least try to make it as simple as possible. One way to make it simple, is to keep it close to the actual mathematical definition. The definition is: 

b(n) := b(n / 2) + (n % 2)        if n > 1
b(n) := (n % 2)                   if n <= 1

Using the neat ternary operator available in C# this becomes:

public static string Convert(int n)
{
    return (n > 1 ? Convert(n / 2) : "") + n % 2;
}

Same can be done with empty list instead of "" and adding list elements instead of "+", but I doubt that this return type is appropriate. Maybe you wanted something like a list of booleans?

Other points that I find suspicious:

1) What do I have to do to my system in order to make the '0' and '1' appear as something else? Is it even possible? If not, why bother adding the internationalization settings?

2) One should require/assert that the input is positive, or treat the negative numbers differently. The current implementation seems to fail silently for negative arguments. Is this intended?

3) All results seem to start with a 0, this is unexpected.

share|improve this answer
    
Welcome to CodeReview, Andrey Tyukin. Nice first post and answer! I hope you enjoy the site. –  Legato Apr 16 at 15:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.