itoa replacement ALMOST perfect

I'll have to check those out.

You know, I'm thinking about the way this whole thing is being done. Specifically this section:

while(n > 0)
{
--ptr;
*ptr= n%radix+'0';
n /= radix;
}

Isn't it possible to get each number by bit manipulation instead? I was thinking about this and printed out the bit values of int types and I'm confused:

int_max: //31 bit is the negative
01111111111111111111111111111111 //2147483647
int_min: //31 bit is the negative
10000000000000000000000000000000 //-2147483648
uint_max:
11111111111111111111111111111111

How is it that int_min is larger than int_max when the bit count that makes the number is the same?

It's an artifact of 2's-complement binary representation of integers. In 32 bits, you have 2^32 possible values. You'd like to split them up evenly between positive and negative numbers, but you have to set one value aside to represent zero. Therefore, you have (2^32) - 1 possible nonzero values that you can represent with 32 bits. Due to how 2's-complement works, it just so happens that 2^31 of these are negative numbers and (2^31) - 1 are positive numbers. Therefore, there is one negative 32-bit number that can not be represented as a positive 32-bit number: 2^31.

I tried and tried to understand that but no matter how I look at it, it doesn't make sense.

10000000000000000000000000000000 //-2147483648
11111111111111111111111111111110 //-1 I'm assuming
11111111111111111111111111111100 //-3 I'm assuming
11111111111111111111111111111101 //-2 I'm assuming - what you said above does not make sense because the 0 bit is used in negative numbers, otherwise -2 could not be represented.

You're looking at it the wrong way.


-2147483648 (min value)

means 2147483648 NEGATIVE values (staring with -1)



2147483647 (max value)

means 2147483648 POSITIVE values (starting with 0) 0 is NOT negative


Also the following is the wrong assumption:
10000000000000000000000000000000 //-2147483648
11111111111111111111111111111110 //-1 I'm assuming
11111111111111111111111111111100 //-3 I'm assuming
11111111111111111111111111111101 //-2 I'm assuming


10000000000000000000000000000001 // -1
10000000000000000000000000000010 // -2
10000000000000000000000000000011 // -3
11111111111111111111111111111111 //-2147483648

Then why does itoa output (radix of 2)
10000000000000000000000000000000 for -2147483648
and
10000000000000000000000000000001 for -2147483647
and
11111111111111111111111111111110 for -2
and
10 for 2
and
1111111111111111111111111111110 for 2147483646

-2 is the one that stumps me:
11111111111111111111111111111110
shouldn't it be:
11111111111111111111111111111101
?

Actually, you're both incorrect.

-1 = 0xFFFFFFFF = 11111111111111111111111111111111
-2 = 0xFFFFFFFE = 11111111111111111111111111111110
... and so on.
-(2^31) = 0x80000000 = 10000000000000000000000000000000

That's just the way it works. Search Google for 2's-complement binary format and you'll find everything there is to know about this topic. To convert a positive number to a negative number, you don't just flip the sign bit. If you did, then it would be possible to have a negative zero, which doesn't make sense.

To negate a 2's-complement number, you negate all of the bits in the number, then add one to the result. That's it. There's no point in wondering why this results in things that seem unnatural to you; that's just the way that (almost) every digital systems designer decided to implement binary integer representation.

So if you are programming on Windows use those functions.

If you want your code to be portable in C++ only, you can do something like this:

Code:

---

namespace myNamespace
{

template < typename INT_TYPE, typename CHAR_TYPE >
CHAR_TYPE * myItoA( INT_TYPE value, CHAR_TYPE * param, int radix=10 );

#include myItoAImpl.tpp

}

---

(I use .tpp for a template implementation that is in a different file from its declaration). You can have different versions of the implementation file, one for uses on Windows that specialises all the types and calls the already-implemented versions. For users on other systems you can implement it when you need to (or call methods supported by those systems).

If you want to make this portable for C then you'd have to provide different functions, for both character types and for different integral types, and there'd be no version for non-portable types. The types that are portable can be implemented with ostringstream and supports different bases too, so your default implementation could use ostringstream.

It would be nicer to be able to return std::string although that has portability issues across libraries too, i.e. you couldn't write such a function and export in a DLL.

Is there a reason for 2's-complement binary or is that just to make the designers LOOK smarter?

You probably don't come from a computer science background, or taken basic assembly language course in college.

Two's complement binary has been in use for decades. It wasn't just thought up by Microsoft. If you take a computer science course, one of the first things that you're taught is 2's complement binary -- flip bits and add 1 to represent the negative of a number. Flip bits and add 1 again to get the positive number.

It is used for easier basic numeric operations between signed and unsigned numbers.
For example -2 + 1:

-2 = 1110 as 2's complement

so:

1110 + 0001 = 1111 == -1 as a 2's complement number.

Regards,

Paul McKenzie

I see. Does Linux also use this same method?

I would think that most, if not all binary-based hardware (i.e. computers) use 2's complement to represent negative numbers. It's just a basic computer science fundamental.

Regards,

Paul McKenzie

Actually 2-complement makes lot of sense:

A property of a number is that if you add to it its negative counterpart the sum becomes zero. IE:
a + (-a) = 0

This should be true for binary numbers as well.

So if we have the following number in binary:

00001110

If we want find the negative value of the binary number above we should solve the equation:

00001110 + X = 00000000

It turns out that the 2-complement is an elegant solution as no special logic is needed in the logical circuits to deal with negative number because if we choose X = 11110010 the equation above becomes (that is X is the 2-complement of 00001110).

00001110 + 11110010 = (1)00000000

(1) is the ninth bit and therefore sliced of for byte artimetics. Taking that into consideration:

00001110 + 11110010 = 00000000

Or perhaps a more formal way of expressing it

00001110 + 11110010 = 00000000 mod 256

Which is what we wanted.

Hopefully that made some sense.

Thanks for filling in the gaps, marten_range. I only added just the taste of why 2's complement is used, but you've explained it pretty well.

Regards,

Paul McKenzie

This function has now become part of my aStr class that replaces string. My tests have shown that it is alot faster than itoa when radix is 2 and a tiny bit slower than itoa if radix is 10.
Code and Results

Testing code snippet:

PHP Code:

---

void aStrAssignNumbers()
{
    int b= int_min; aStr as;
    ResetAndStartTimer("Mine");
    for(uint i= 0; i< loops; ++i)
    {
        as.Assign(b, 10);
    }
    StopAndLog();
    ResetAndStartTimer("itoa");
    for(uint i= 0; i< loops; ++i)
    {
        const uint bits= sizeof(b)*CHAR_BIT;
        char c[bits+1]; char* cc= itoa(b, c, 10);
        as= cc;
    }
    StopAndLog();
    testInt+= b*b*b+30*b/6;
}

//Above function is called here
else if(&goBut== e.c)
{
    ::SetThreadPriority(::GetCurrentThread(), THREAD_PRIORITY_TIME_CRITICAL); //THREAD_PRIORITY_HIGHEST THREAD_PRIORITY_ABOVE_NORMAL THREAD_PRIORITY_BELOW_NORMAL THREAD_PRIORITY_IDLE THREAD_PRIORITY_LOWEST THREAD_PRIORITY_NORMAL=0
    loops= 0;
    loopsEB.Text.ToInt(&loops);
    if(!loops)
    {
        ::SetThreadPriority(::GetCurrentThread(), THREAD_PRIORITY_NORMAL);
        MB("Invalid entry.  Setting to max."); loopsEB.setText(ToStr(int_max).str());
        return;
    }
    aStr s("Loops: "); s= s<< loops;
    listBox.AddItem(s); listBox.AddItem("");
    
    aStrAssignNumbers(); listBox.AddItem("");
    //Primitives(); listBox.AddItem("");
    ::SetThreadPriority(::GetCurrentThread(), THREAD_PRIORITY_NORMAL);
    DD("");
} 


---

I am using VC++ 2002 building in Release with all optimasations on; /O2.

That's an incomplete example. You haven't shown your aStr class at all. I'm assuming that "as" is an instance of this class. I notice in the itoa() case, you're calling operator= and assigning the character pointer to your object. Your implementation of operator= could be the cause for the measured poor performance in that case. To say anything definitive, we would need to see your whole class, enough that anyone here could compile and run the program. Just as Paul is, I'm very wary of these implementations that "beat" the standard library.