Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: How to encode/decode string of decimal digits |
| Date | 2015-10-23 13:22 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <87pp05ojtr.fsf@bsb.me.uk> (permalink) |
| References | (10 earlier) <87vb9zez2u.fsf@bsb.me.uk> <eb30863e-a503-42d9-bbc7-b58a196aea0b@googlegroups.com> <n0cq5r$p7v$1@dont-email.me> <871tclq4ck.fsf@bsb.me.uk> <n0d34a$nu6$1@dont-email.me> |
Bartc <bc@freeuk.com> writes: > On 23/10/2015 11:14, Ben Bacarisse wrote: >> pozz <pozzugno@gmail.com> writes: >> >>> Il 22/10/2015 18:31, supercat@casperkitty.com ha scritto: > >>>> A uint64_t handles numbers up to 18446744073709551616 (20 digits) >>>> >>>> Simple approach: Add 2 to the first digit, replacing it with two digits 10 or >>>> 11 if needed. >>>> >>>> After decoding, if the leading digit is 1, subtract 2 from the initial >>>> 2-digit number. >>> >>> I'm sorry, I couldn't get it. Could you make some examples, please? >> >> I'm not the originator but still... >> >> The idea is to split the string into a lead digit and the rest: >> >> 0 => 0| >> 99 => 9|9 >> 0000 => 0|000 >> 123 => 1|23 >> 80 => 8|0 >> >> and then add two to the lead digit and concatenate the result: >> >> 0 => 0| => 2|0 => 20 >> 99 => 9|9 => 11|9 => 119 >> 0000 => 0|000 => 2|000 => 2000 >> 123 => 1|23 => 3|23 => 323 >> 80 => 8|0 => 10|0 => 100 >> >> This gives you a number between 2 (from the string "0") up to >> 11999999999999999999 from 9999999999999999999 (19 9s). That range of >> numbers can be stored in a uint64_t directly. >> >> The neat trick is that by adding two (rather than one) you can always >> decode a leading "1" as being part of a "11" or "10" pair resulting from >> an 8 or 9 in the original. Were you to add only one, both "00" and "9" >> would result in "10". >> >> There are simpler, similar, approaches, such as just putting a "1" on >> the left of the string, but that does not work for 19 digits though it >> does for 18. All of these require decimal conversion where the BCD >> approach does not, but you get two or three more digits in exchange. > > That all sounds clever, but... what's the purpose of it? To find if a > string contains a number that will be fit into 64 bits when converted > to binary? No, to store a 19 digit string (that might have significant leading zero) in 64 bits. The simple scheme gets 16. I thought that 19 would probably be fiddly, but this method is neat, I think. (It's a bit fiddly, but simpler than anything I came up with for 19 digits.) [For context: of course 19-digit decimal all fit in 64 bits. The part that makes this an interesting challenge is to encode leading zeros. I.e. "0001" != "01" != "1".] -- Ben.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
How to encode/decode string of decimal digits pozz <pozzugno@gmail.com> - 2015-10-19 14:28 +0200
Re: How to encode/decode string of decimal digits Bartc <bc@freeuk.com> - 2015-10-19 14:07 +0100
Re: How to encode/decode string of decimal digits pozz <pozzugno@gmail.com> - 2015-10-19 15:58 +0200
Re: How to encode/decode string of decimal digits Bartc <bc@freeuk.com> - 2015-10-19 15:22 +0100
Re: How to encode/decode string of decimal digits Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-19 15:58 +0100
Re: How to encode/decode string of decimal digits Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-19 22:28 +0100
Re: How to encode/decode string of decimal digits Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-10-19 13:30 -0400
Re: How to encode/decode string of decimal digits Robert Wessel <robertwessel2@yahoo.com> - 2015-10-19 16:18 -0500
Re: How to encode/decode string of decimal digits Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-10-19 21:38 -0400
Re: How to encode/decode string of decimal digits Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-10-20 08:00 +0000
Re: How to encode/decode string of decimal digits Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-19 15:50 +0100
Re: How to encode/decode string of decimal digits Keith Thompson <kst-u@mib.org> - 2015-10-19 09:01 -0700
Re: How to encode/decode string of decimal digits Tim Rentsch <txr@alumni.caltech.edu> - 2015-10-19 12:11 -0700
Re: How to encode/decode string of decimal digits pozz <pozzugno@gmail.com> - 2015-10-20 13:51 +0200
Re: How to encode/decode string of decimal digits Bartc <bc@freeuk.com> - 2015-10-20 13:38 +0100
Re: How to encode/decode string of decimal digits glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-20 16:05 +0000
Re: How to encode/decode string of decimal digits pozz <pozzugno@gmail.com> - 2015-10-21 09:29 +0200
Re: How to encode/decode string of decimal digits Bartc <bc@freeuk.com> - 2015-10-21 11:27 +0100
Re: How to encode/decode string of decimal digits pozz <pozzugno@gmail.com> - 2015-10-21 17:55 +0200
Re: How to encode/decode string of decimal digits Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-10-21 08:03 -0400
Re: How to encode/decode string of decimal digits pozz <pozzugno@gmail.com> - 2015-10-21 17:53 +0200
Re: How to encode/decode string of decimal digits supercat@casperkitty.com - 2015-10-21 09:37 -0700
Re: How to encode/decode string of decimal digits David Brown <david.brown@hesbynett.no> - 2015-10-22 11:47 +0200
Re: How to encode/decode string of decimal digits pozz <pozzugno@gmail.com> - 2015-10-22 13:44 +0200
Re: How to encode/decode string of decimal digits Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-22 13:45 +0100
Re: How to encode/decode string of decimal digits Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-22 15:51 +0100
Re: How to encode/decode string of decimal digits supercat@casperkitty.com - 2015-10-22 09:31 -0700
Re: How to encode/decode string of decimal digits Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-22 20:48 +0100
Re: How to encode/decode string of decimal digits pozz <pozzugno@gmail.com> - 2015-10-23 10:14 +0200
Re: How to encode/decode string of decimal digits Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-23 11:14 +0100
Re: How to encode/decode string of decimal digits Bartc <bc@freeuk.com> - 2015-10-23 11:47 +0100
Re: How to encode/decode string of decimal digits Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-23 13:22 +0100
Re: How to encode/decode string of decimal digits David Brown <david.brown@hesbynett.no> - 2015-10-22 15:07 +0200
Re: How to encode/decode string of decimal digits glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-22 22:05 +0000
Re: How to encode/decode string of decimal digits pozz <pozzugno@gmail.com> - 2015-10-23 10:15 +0200
Re: How to encode/decode string of decimal digits glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-19 22:02 +0000
Re: How to encode/decode string of decimal digits supercat@casperkitty.com - 2015-10-20 10:09 -0700
csiph-web