Extract Digits From An Integer Without sprintf() Or Modulo (SOLVED)

Question

The requirements of this are somewhat restrictive because of the machinery this will eventually be implemented on (a GPU).

I have an unsigned integer, and I am trying to extract each individual digit.

If I were doing this in C++ on normal hardware & performance weren't a major issue, I might do it like this:

(Don't hate on me for this code, it's just a sample to illustrate the method)

#define _CRT_SECURE_NO_WARNINGS

#include <cstdlib>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int someVal = 1234;

    char stringVal[256] ={0};
    sprintf(stringVal, "%016d", someVal);

    int digits[16] = {0};
    for( int i = 0; i < strlen(stringVal); ++i )
    {
        digits[i] = stringVal[i] - '0';
    }

    cout << "Integer Value = " << someVal << endl;
    cout << "Extracted Digits = ";
    copy( &digits[0], &digits[16], ostream_iterator<int>(cout, "-") );
    cout << endl;

    return 0;
}

I'm trying to find a method to extract these digits with the following restrictions:

1. Don't convert the integer to a string
2. Don't use the modulus operator (floating point division is fine)
3. The value in question is a 32-bit unsigned integer

I'm looking for an algorithm, not necessarily specific code. But specific code would be great. The languages I'm most familiar with that translate well to my target hardware are C++, C and assembler.

Any ideas?

EDIT: Here's an update with the algorithm I implemented based on the comments & links below. Thanks all.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdlib>
#include <string>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
    unsigned someVal = 12345678;
    static const unsigned numDigits = 10;
    unsigned digits[numDigits] = {0};

    for( unsigned i = 0, temp = someVal; i < numDigits; ++i, temp /= 10 )
    {
        digits[numDigits-i-1] = temp - 10 * (temp/10)      /*temp % 10*/;
    }


    cout << "Integer Value = " << someVal << endl;
    cout << "Extracted Digits = ";
    copy( &digits[0], &digits[numDigits], ostream_iterator<int>(cout, "-") );
    cout << endl;

    return 0;
}

Answer 1

Remember that the modulo operator can actually be implemented as:

mod(a, n) = a - n * floor(a / n)

Hence, you can use your favorite modulo based algorithm. You can simulate floor itself by typecasting.

Answer 2

Have a look around here in Bob Stout's snippets here under the C Archive, and here under the C++ Archive. Not alone that the snippets archive strive to be portable.

Hope this helps, Best regards, Tom.

Answer 3

One worth considering, by Terje Mathisen.