How to get the Nth digit of an integer with bit-wise operations?

Question

Example. 123456, and we want the third from the right ('4') out.

The idea in practise is to access each digit seperately (ie. 6 5 4 3 2 1).

C/C++/C# preferred.

Answer 1

In C you could do something like the following, where n=0 would indicate the rightmost digit

char nthDigitFromRight(int x,int n)
{
    char str[20];
    sprintf(str,"%020d",x);
    return(str[19 - x]);
}

Change [19-x] to [20-x] if you want n=1 for rightmost digit.

Answer 2

The reason that it won't work (easily) with bit-wise operations is that the base of the decimal system (10) is not a power of the base of the binary system (2).

If you were coding in base 8, you'd have pow(2, 3) == 8, and could extract each octal digit as a block of three bits.

So you really have to convert to base 10, which is usually done by converting to a string (with toString (Java) or sprintf (C), as the others have shown in their replies).

Answer 3

A more efficient implementation might be something like this:

char nthdigit(int x, int n)
{
    while (n--) {
        x /= 10;
    }
    return (x % 10) + '0';
}

This saves the effort of converting all digits to string format if you only want one of them. And, you don't have to allocate space for the converted string.

If speed is a concern, you could precalculate an array of powers of 10 and use n to index into this array:

char nthdigit(int x, int n)
{
    static int powersof10[] = {1, 10, 100, 1000, ...};
    return ((x / powersof10[n]) % 10) + '0';
}

As mentioned by others, this is as close as you are going to get to bitwise operations for base 10.

Answer 4

Use base-10 math:

class Program
{
    static void Main(string[] args)
    {
        int x = 123456;

        for (int i = 1; i <= 6; i++)
        {
            Console.WriteLine(GetDigit(x, i));
        }
    }

    static int GetDigit(int number, int digit)
    {
        return (number / (int)Math.Pow(10, digit - 1)) % 10;
    }
}

Produces:

6
5
4
3
2
1

Answer 5

You could try a bitwise shift-left (for N-1) and then read the digit at [0], as this could be an assembler approach.

123456 -> 456 -> read first digit

Answer 6

This works for unsigned ints up to 451069, as explained here:

def hundreds_digit(u): return mod10(div100(u))

def div100(u): return div10(div10(u))
def mod10(u):  return u - mul10(div10(u))
def mul10(u):  return ((u << 2) + u) << 1

def div10(u):
    Q = ((u >> 1) + u) >> 1  # Q = u*0.11
    Q = ((Q >> 4) + Q)       # Q = u*0.110011
    Q = ((Q >> 8) + Q) >> 3  # Q = u*0.00011001100110011
    return Q

# Alternatively:
#   def div100(u): return (u * 0xa3d7) >> 22
# though that'd only work for 16-bit u values.
# Or you could construct shifts and adds along the lines of div10(),
# but I didn't go to the trouble.

Testing it out:

>>> hundreds_digit(123456)
4
>>> hundreds_digit(123956)
9

I'd be surprised if it's faster, though. Maybe you should reconsider your problem.