# How to read an integer one by one?

Discussion in 'C Programming' started by henrytcy@gmail.com, Dec 7, 2005.

1. ### Guest

Hi,

How can I get a digit from integer for example, 12311, one by one for
comparision?

Thanks!

, Dec 7, 2005

2. ### Niklas NorrthonGuest

writes:

> Hi,
>
> How can I get a digit from integer for example, 12311, one by one for
> comparision?

#define BIG_ENOUGH 1000

int main(void)
{
unsigned int x = 12311;

/* If you want the last digit, its simple: */
unsigned int digit = x % 10;

/* Now you can go on and throw away that
* digit from the original number:
*/
x /= 10;

/* And you could put it in a loop to get the
* digits one after one:
while (x > 0) {
digit = x % 10;
/* do something with it */
x /= 10;
}

/* If you want them in the same order as they
* are written it's a little bit more complicated,
* either you do it like above, and save the digits,
* and then use them in reverse order,
* or you could use the formatting output functions
* to create a string and take them from there:
*/

char buf[BIG_ENOUGH]; /* this must be at top in C90 */
char* ptr = buf;
x = 12311;
sprintf(buf, "%d", x); /* also consinder snprintf... */
while (*ptr) {
unsigned int digit = *ptr - '0';
/* do something with digit */
++ptr;
}
return 0;
}

/Niklas Norrthon

Niklas Norrthon, Dec 7, 2005

3. ### Richard BosGuest

Niklas Norrthon <> wrote:

> #define BIG_ENOUGH 1000

How do you know this?

Richard

Richard Bos, Dec 7, 2005

int x = 12311;
char str[10];
sprintf(str, "%d", x);
Now you can use str to access individual digit.

---
regards

Prasad J Pandit, Dec 7, 2005
5. ### Niklas NorrthonGuest

(Richard Bos) writes:

> Niklas Norrthon <> wrote:
>
> > #define BIG_ENOUGH 1000

>
> How do you know this?

I don't, and later I also say consider snprintf.

(But platforms with ints larger than 3000 bits are
not too common yet...)

/Niklas Norrthon

Niklas Norrthon, Dec 7, 2005
6. ### Richard HeathfieldGuest

Richard Bos said:

> Niklas Norrthon <> wrote:
>
>> #define BIG_ENOUGH 1000

>
> How do you know this?

By definition.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

Richard Heathfield, Dec 7, 2005
7. ### Richard BosGuest

Niklas Norrthon <> wrote:

> (Richard Bos) writes:
>
> > Niklas Norrthon <> wrote:
> >
> > > #define BIG_ENOUGH 1000

> >
> > How do you know this?

>
> I don't, and later I also say consider snprintf.
>
> (But platforms with ints larger than 3000 bits are
> not too common yet...)

Platforms on which you don't want to waste 1000 bytes are, though.

There is a good method for getting a reasonable, not too low and only
barely too high, upper bound on the length of a decimally expanded int.
It is, however, left as an exercise for the OP.

Richard

Richard Bos, Dec 8, 2005
8. ### =?iso-8859-1?q?Dag-Erling_Sm=F8rgrav?=Guest

(Richard Bos) writes:
> There is a good method for getting a reasonable, not too low and only
> barely too high, upper bound on the length of a decimally expanded int.
> It is, however, left as an exercise for the OP.

There are several. Which one you choose depends on the relative
scarcity of CPU cycles and memory.

This one is slightly wasteful of memory, but is computed entirely at
compile time:

#include <limits.h>
char number[1+(sizeof(int)*CHAR_BIT)/3+1];

The resulting array will be large enough to store the null-terminated
decimal representation of any integer in the range (INT_MIN,INT_MAX).
Proof of this is left as an exercise for the reader. For extra
credits, show how and why the code can or must be modified to

DES
--
Dag-Erling Smørgrav -

=?iso-8859-1?q?Dag-Erling_Sm=F8rgrav?=, Dec 8, 2005
9. ### SkarmanderGuest

Dag-Erling Smørgrav wrote:
> (Richard Bos) writes:
>> There is a good method for getting a reasonable, not too low and only
>> barely too high, upper bound on the length of a decimally expanded int.
>> It is, however, left as an exercise for the OP.

>
> There are several. Which one you choose depends on the relative
> scarcity of CPU cycles and memory.
>
> This one is slightly wasteful of memory, but is computed entirely at
> compile time:
>
> #include <limits.h>
> char number[1+(sizeof(int)*CHAR_BIT)/3+1];
>
> The resulting array will be large enough to store the null-terminated
> decimal representation of any integer in the range (INT_MIN,INT_MAX).
> Proof of this is left as an exercise for the reader.

Actually, please show why this works, especially why this works for INT_MIN.
It's easy enough to see N / 3 + 1 can approximate ceil(log10(2^N)), but I
can't get the details quite right for signed integers. I'm sure I'm
overlooking something obvious.

> For extra credits, show how and why the code can or must be modified to
> accomodate the range (UINT_MIN,UINT_MAX) instead.

There is no UINT_MIN. It could have been defined simply as 0, but it isn't.

The code needs no modification (it always allocates enough storage) but
easily allows better approximations if we only consider unsigned integers.
For example, (sizeof(int) * CHAR_BIT * 28) / 93 + 1 will give an
approximation that is precise for all integer types smaller than 93 bits
(save that it may still be wasteful insofar as it cannot take into account

If we ignore the possibility of overflow through padding bits (which would
be pathological), the best approximation is (sizeof(int) * CHAR_BIT * 643) /
2136 + 1. This wastes no space for integers with up to 15,436 bits (again,
except for padding bits), which is probably more than we'll ever need.

S.

Skarmander, Dec 8, 2005
10. ### Richard HeathfieldGuest

Skarmander said:

> Dag-Erling Smørgrav wrote:
>> This one is slightly wasteful of memory, but is computed entirely at
>> compile time:
>>
>> #include <limits.h>
>> char number[1+(sizeof(int)*CHAR_BIT)/3+1];

That looks familiar, but... well, enough of that later.

>> The resulting array will be large enough to store the null-terminated
>> decimal representation of any integer in the range (INT_MIN,INT_MAX).
>> Proof of this is left as an exercise for the reader.

>
> Actually, please show why this works, especially why this works for
> INT_MIN. It's easy enough to see N / 3 + 1 can approximate
> ceil(log10(2^N)), but I can't get the details quite right for signed
> integers. I'm sure I'm overlooking something obvious.

I can explain it easily enough, for the simple reason that I invented it.
(I'm quite sure there are other people who've invented it too, and
long before I did, but at any rate I derived it independently, and so I
know why it works.)

An int comprises sizeof(int) * CHAR_BIT bits. Since three bits can always
represent any octal digit, and leaving signs and terminators aside for a
second, it is clear that (sizeof(int) * CHAR_BIT) / 3 characters are
sufficient to store the octal representation of the number (but see below).
Since decimal can represent more efficiently than octal, what's good enough
for octal is also good enough for decimal.

Now we add in 1 for the sign, and 1 for the null terminator, and that's
where the above expression comes from.

BUT: consider the possibility that the integer division truncates (which it
will do if sizeof(int) * CHAR_BIT is not a multiple of 3). Under such
circumstances, you could be forgiven for wanting some bodge factor in
there. That's why I use:

char number[1 + (sizeof(int) * CHAR_BIT + 2) / 3 + 1];

The + 2 is always sufficient to counter the effects of any truncation after
division by 3, but doesn't inflate the result by more than one character at
most.

Now let's look at a typical case, INT_MIN on a 32-bit int system with 8-bit
chars. sizeof(int) on such a system is 4, and CHAR_BIT is 8, which gives us
32 + 2 = 34 for the parenthesised expression. Dividing this by three gives
us 11 (integer division, remember), and then we add 1 for the sign and 1
for the null. That's 12 data bytes and a null byte.

INT_MIN on that system would be no mag-higher than -2147483648 which is just
11 data bytes in length - so it turns out that our fudge factor wasn't
strictly necessary on this occasion. (That's because decimal is, as I said,
a little better than octal at representing numbers concisely.)

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

Richard Heathfield, Dec 8, 2005
11. ### SkarmanderGuest

Richard Heathfield wrote:
> Skarmander said:
>
>> Dag-Erling Smørgrav wrote:
>>> This one is slightly wasteful of memory, but is computed entirely at
>>> compile time:
>>>
>>> #include <limits.h>
>>> char number[1+(sizeof(int)*CHAR_BIT)/3+1];

>
> That looks familiar, but... well, enough of that later.
>
>>> The resulting array will be large enough to store the null-terminated
>>> decimal representation of any integer in the range (INT_MIN,INT_MAX).
>>> Proof of this is left as an exercise for the reader.

>> Actually, please show why this works, especially why this works for
>> INT_MIN. It's easy enough to see N / 3 + 1 can approximate
>> ceil(log10(2^N)), but I can't get the details quite right for signed
>> integers. I'm sure I'm overlooking something obvious.

>
> I can explain it easily enough, for the simple reason that I invented it.
> (I'm quite sure there are other people who've invented it too, and
> long before I did, but at any rate I derived it independently, and so I
> know why it works.)
>
> An int comprises sizeof(int) * CHAR_BIT bits. Since three bits can always
> represent any octal digit, and leaving signs and terminators aside for a
> second, it is clear that (sizeof(int) * CHAR_BIT) / 3 characters are
> sufficient to store the octal representation of the number (but see below).
> Since decimal can represent more efficiently than octal, what's good enough
> for octal is also good enough for decimal.
>
> Now we add in 1 for the sign, and 1 for the null terminator, and that's
> where the above expression comes from.
>

Interesting. Yes, that's probably more straightforward than the brute force
I applied: to represent a number n in a base b, you need ceil(log_b(|n|))
digits (for n != 0). sizeof(int) * CHAR_BIT gives us an upper bound for the
value bits of an integer, and hence an upper bound for (U)INT_MAX: 2^N with
N = sizeof(int) * CHAR_BIT.

Now to represent N-bit integers in decimal, we need at most ceil(log10(2^N))
= ceil(N * log10(2)) = floor(N * log10(2)) + 1 = N / log2(10) + 1 bits. "3"
(log2(8)) is exactly right for octal, and as you say, good enough for
decimal. Better approximations for log2(10) give closer bounds. This does

> BUT: consider the possibility that the integer division truncates (which it
> will do if sizeof(int) * CHAR_BIT is not a multiple of 3). Under such
> circumstances, you could be forgiven for wanting some bodge factor in
> there. That's why I use:
>
> char number[1 + (sizeof(int) * CHAR_BIT + 2) / 3 + 1];
>
> The + 2 is always sufficient to counter the effects of any truncation after
> division by 3, but doesn't inflate the result by more than one character at
> most.
>

<snip>
Yes, and I won't dispute the practicality of this approach as opposed to my
mysterious logarithm approximations, but the challenge is this: prove that
no bodge factor is necessary (it isn't). sizeof(int) * CHAR_BIT / 3 + 1
always gives enough space for all digits and a sign if an integer type is
greater than 11 bits, which it's guaranteed to be (except for char, of
course, and you do need correction for signed char if CHAR_BIT is 8).

If I'm not mistaken, this is the same as proving that ceil((N - 1) *
log10(2) + 1) <= N / 3 for all N >= 12 (one value bit less for signed
integers, but one character more). Like I said, I'm sure I'm overlooking
something simple, some transformation that will highlight this.

I guess I should have paid better attention in math class. I like to stick
to boolean algebra...

S.

Skarmander, Dec 8, 2005
12. ### =?iso-8859-1?q?Dag-Erling_Sm=F8rgrav?=Guest

Skarmander <> writes:
> Dag-Erling Smørgrav wrote:
> > #include <limits.h>
> > char number[1+(sizeof(int)*CHAR_BIT)/3+1];
> > The resulting array will be large enough to store the null-terminated
> > decimal representation of any integer in the range (INT_MIN,INT_MAX).
> > Proof of this is left as an exercise for the reader.

> Actually, please show why this works, especially why this works for
> INT_MIN. It's easy enough to see N / 3 + 1 can approximate
> ceil(log10(2^N)), but I can't get the details quite right for signed
> integers. I'm sure I'm overlooking something obvious.

There are three terms in the addition.

DES
--
Dag-Erling Smørgrav -

=?iso-8859-1?q?Dag-Erling_Sm=F8rgrav?=, Dec 8, 2005
13. ### SkarmanderGuest

Dag-Erling Smørgrav wrote:
> Skarmander <> writes:
>> Dag-Erling Smørgrav wrote:
>>> #include <limits.h>
>>> char number[1+(sizeof(int)*CHAR_BIT)/3+1];
>>> The resulting array will be large enough to store the null-terminated
>>> decimal representation of any integer in the range (INT_MIN,INT_MAX).
>>> Proof of this is left as an exercise for the reader.

>> Actually, please show why this works, especially why this works for
>> INT_MIN. It's easy enough to see N / 3 + 1 can approximate
>> ceil(log10(2^N)), but I can't get the details quite right for signed
>> integers. I'm sure I'm overlooking something obvious.

>
> There are three terms in the addition.
>

So sizeof(int) * CHAR_BIT / 3 is the term supposed to approximate the number
of digits, and the +1 is for the sign? Hm. Crude.

S.

Skarmander, Dec 8, 2005
14. ### =?iso-8859-1?q?Dag-Erling_Sm=F8rgrav?=Guest

Richard Heathfield <> writes:
> I can explain it easily enough, for the simple reason that I
> invented it.

That's a bit presumptive, don't you think? It's an obvious solution
to anyone who understands logarithms.

> An int comprises sizeof(int) * CHAR_BIT bits. Since three bits can
> always represent any octal digit, and leaving signs and terminators
> aside for a second, it is clear that (sizeof(int) * CHAR_BIT) / 3
> characters are sufficient to store the octal representation of the
> number (but see below). Since decimal can represent more
> efficiently than octal, what's good enough for octal is also good
> enough for decimal.

Octal never entered my mind; 3 is simply a good enough approximation
of log2(10).

> BUT: consider the possibility that the integer division truncates
> (which it will do if sizeof(int) * CHAR_BIT is not a multiple of
> 3). Under such circumstances, you could be forgiven for wanting some
> bodge factor in there. That's why I use:
>
> char number[1 + (sizeof(int) * CHAR_BIT + 2) / 3 + 1];

Turns out the bodge factor is never necessary on a two's complement
machine.

DES
--
Dag-Erling Smørgrav -

=?iso-8859-1?q?Dag-Erling_Sm=F8rgrav?=, Dec 8, 2005
15. ### Jordan AbelGuest

On 2005-12-08, Dag-Erling Smørgrav <> wrote:
> Turns out the bodge factor is never necessary on a two's complement
> machine.

two's complement has nothing to do with it.

take 32 bits.

32/3=10

your assertion implies [essentially] that 10 digits is sufficient for
the _octal_ representation of 2^32-1, which is 11 digits: 37777777777.

For n < 9, ceil(log[10](2^n)) exceeds floor(log[8](2^n))

this means if you try it with char rather than int, you'll get screwed.

on an 8-bit char system, CHAR_BIT/3+2=4, which is one fewer byte than
needed for SCHAR_MIN, "-128" (plus null terminator).

Jordan Abel, Dec 8, 2005
16. ### Richard HeathfieldGuest

Dag-Erling Smørgrav said:

> Richard Heathfield <> writes:
>> I can explain it easily enough, for the simple reason that I
>> invented it.

>
> That's a bit presumptive, don't you think?

Yes. Hence the qualification, which you snipped.

> It's an obvious solution to anyone who understands logarithms.

Lots of things are obvious even to people who don't. That doesn't stop
software companies from patenting them.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

Richard Heathfield, Dec 9, 2005
17. ### =?iso-8859-1?q?Dag-Erling_Sm=F8rgrav?=Guest

Jordan Abel <> writes:
> this means if you try it with char rather than int, you'll get screwed.

I never intended it to be used for char. I was relying on the fact
that int cannot be smaller than 16 bits.

DES
--
Dag-Erling Smørgrav -

=?iso-8859-1?q?Dag-Erling_Sm=F8rgrav?=, Dec 9, 2005
18. ### Jordan AbelGuest

On 2005-12-09, Dag-Erling Smørgrav <> wrote:
> Jordan Abel <> writes:
>> this means if you try it with char rather than int, you'll get screwed.

>
> I never intended it to be used for char. I was relying on the fact
> that int cannot be smaller than 16 bits.

well, it still has nothing to do with twos-complement. The extra factor
is still useful if you intend to use the same buffer for octal - and
it's practically free since it gets calculated at compile time

>
> DES

Jordan Abel, Dec 9, 2005