Number Systems

03 Dec 2010. comments

These are some simple code katas to keep you fresh about numbering systems.

atoi (ASCII to Integer)

This is a time tested problem in which you’re asked to convert a string representation of a number to the actual integer. So for example if passed:

"42"

Then you should get out:

42

Here’s what an implementation could look like:

class Numbers {

  private static int atoi(string number) {
    int result = 0;  
    int multiplier = 1;  

    for (int idx = number.Length - 1; idx >= 0; idx--)  
    {  
      int digitValue = number[idx] - '0';  
      result += (digitValue * multiplier);  
      multiplier *= 10;  
    }  

    return result;  
  }

}

The algorithm in plain english:

  1. Inspect each character in the string
  2. For each character subtract it’s ASCII table value (so for example ‘4’ is 52) from ASCII zero (0 is 48).
  3. Take the resulting value and multiply it by the current power (1, 10, 100, 1000, etc).
  4. Add the result of the multiplication to the answer being developed.

Bit Count

This next problem is really great because it helps you understand binary and there are also many different correct implementations. Some algorithms involve bit manipulation, some involve simple math, some involve bit masking.

Here’s a math-based implementation:

class Numbers {

  private static int bitCount(int number)  
  {  
    int bits = 0;  
    while (number > 0)  
    {  
      bits += (number % 2);  
      number /= 2;  
    }  

    return bits;  
  }

}

Again in plain english:

  1. We take the number and continually see if its value is divisible cleanly by 2.
  2. Then we halve the number and check again.
  3. This process gets repeated until the number has been zeroed.

Why does this work? Consider the binary implementation of the number 7:

0111

Here’s what that algorithm would look like visually:

bits == 0
7              (0111)
7 % 2 == 1      add 1 bit
bits == 1
7 /= 2 == 3 
3              (0011)
3 % 2 == 1      add 1 bit
bits == 2
3 /= 2 == 1
1              (0001)
1 % 2 == 1      add 1 bit
bits == 3
1 /= 2 == 0
0

There are 3 bits turned on in the number 7.

Visually you can see that it checks if a bit exists at the right-most position (because if a 1 exists at the right-most position then the number is odd). Then it’s just right-shifting the binary by 1 and repeating the process. As I mentioned earlier you can also achieve this behavior with bit shifting operations but I find this method easier to understand and less language-specific.

comments

Tagged: algorithms Katas

2017 Ben Lakey

The words here do not reflect those of my employer.