H
henrytcy
Hi,
How can I get a digit from integer for example, 12311, one by one for
comparision?
Thanks!
How can I get a digit from integer for example, 12311, one by one for
comparision?
Thanks!
N
Niklas Norrthon
#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
R
Richard Bos
Niklas Norrthon said:
How do you know this?
Richard
P
Prasad J Pandit
int x = 12311;
char str[10];
sprintf(str, "%d", x);
Now you can use str to access individual digit.
char str[10];
sprintf(str, "%d", x);
Now you can use str to access individual digit.
N
Niklas Norrthon
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
R
Richard Heathfield
Richard Bos said:
By definition.
By definition.
R
Richard Bos
Niklas Norrthon said:
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
?
=?iso-8859-1?q?Dag-Erling_Sm=F8rgrav?=
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
accomodate the range (UINT_MIN,UINT_MAX) instead.
DES
S
Skarmander
Dag-Erling Smørgrav said:
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 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
padding bits).
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.
R
Richard Heathfield
Skarmander said:
That looks familiar, but... well, enough of that later.
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.)
That looks familiar, but... well, enough of that later.
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.)
S
Skarmander
Interesting. Yes, that's probably more straightforward than the brute forceRichard said:Skarmander said:
That looks familiar, but... well, enough of that later.
I can explain it easily enough, for the simple reason that I invented it.
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.
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
not take the sign into account.
<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.
?
=?iso-8859-1?q?Dag-Erling_Sm=F8rgrav?=
Skarmander said:
There are three terms in the addition.
DES
S
Skarmander
So sizeof(int) * CHAR_BIT / 3 is the term supposed to approximate the numberDag-Erling Smørgrav said:
of digits, and the +1 is for the sign? Hm. Crude.
S.
?
=?iso-8859-1?q?Dag-Erling_Sm=F8rgrav?=
Richard Heathfield said:
That's a bit presumptive, don't you think? It's an obvious solution
to anyone who understands logarithms.
Octal never entered my mind; 3 is simply a good enough approximation
of log2(10).
Turns out the bodge factor is never necessary on a two's complement
machine.
DES
J
Jordan Abel
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).
R
Richard Heathfield
Dag-Erling Smørgrav said:
Yes. Hence the qualification, which you snipped.
Lots of things are obvious even to people who don't. That doesn't stop
software companies from patenting them.
Yes. Hence the qualification, which you snipped.
Lots of things are obvious even to people who don't. That doesn't stop
software companies from patenting them.
?
=?iso-8859-1?q?Dag-Erling_Sm=F8rgrav?=
Jordan Abel said:
I never intended it to be used for char. I was relying on the fact
that int cannot be smaller than 16 bits.
DES
J
Jordan Abel
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