Next hex value excluding 'A'

[theotyflos]

Hi all,

having a string containing 4 hex digits, I need a function that returns the next hex value excluding 'A's. For example:
string = "1999" ==> next value = "199B". This is what i have so far:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* returns the next hex value excluding 'A's */
char *next_code (char *code)
/* code is guaranteed to point to a string containing 4 valid hex chars */
{
static char    hex_code[5];
unsigned short decimal_value;
  decimal_value = (unsigned short)strtol (code, NULL, 16);
  do {
    decimal_value = ++decimal_value & 0xFFFF; /* FFFF's next is 0000 */
    (void)sprintf (hex_code, "%04X", decimal_value);
  } while ( strchr (hex_code, 'A') );
  return hex_code;
}

/*** TEST ***/
#define TEST
#ifdef TEST
int main (void)
{
char code[5];
  (void)printf ("enter hex code : ");
  (void)scanf  ("%s", code);
  (void)printf ("next code is   : %s\n", next_code(code) );
  return 0;
}
#endif

It works, but since I'm not a C expert, I would appreciate any comments and/or improvements.

Thanks all in advance.

Theophilos.

-----------

There are only 10 kinds of people: Those who understand binary and those who don't.

 

[ArkM]

Try (call after strtol):

unsigned NextNoA(unsigned n)
{
  unsigned m;

  do
  {
    ++n;
    for (m = n; m; m >>= 4)
    {
        if ((m & 0xF) == 10)
	{
           m = 10;
	   break;
	}
    }
  } while (m);
  return n;
}

I think it's more (more faster than sprintf (make it inline)...

 

[hoinz]

Hi,

the restriction to exclude 'A's makes me doubt whether a numeric approach is reasonable at all.
I may suggest another idea, which may result in a longer coding, but in a shorter execution time:

Forget that your string is a hex number, even forget that you have a string at all. Just look at four characters X[1], ... X[4].
Set up a loop for them beginning with X[4], that does this:
* if it is in 0,1,...8,B,...E, increment by one and return.
* if it is equal to 9, let it be B and return.
* if it is equal to F, let it be 0 and proceed to your next character.

regards

 

[theotyflos]

ArkM, thank you for the quick response.
I find your solution very elegant.

About the sprintf: Since my function must return a char * and not an int, I can't throw it away (the sprintf). Only the strchr was thrown away. So, do you mean something like this?

char *next_code (char *code)
{
static char  hex_code[5];
unsigned int decimal_value;
  decimal_value=NextNoA((unsigned int)strtol(code,NULL,16));
  (void)sprintf(hex_code,"%04X",decimal_value);
  return hex_code;
}

Another question: Is it more correct to use int instead of short?

Theophilos.

-----------

There are only 10 kinds of people: Those who understand binary and those who don't.

 

[theotyflos]

Hi hoinz,

Thank you too. Nice idea! Some comments: You say x[1] thru x[4]. Shouldn't that be x[0] thru x[3]?
if x[3] = 'F' and increment it to '0' then I have to add 1 to x[2] and so on, right? The same check must be done for the previous 3 digits. Whouln'd that be slower than a simple call to sprintf?

regards.

Theophilos.

-----------

There are only 10 kinds of people: Those who understand binary and those who don't.

 

[hoinz]

Hi Theophilos,

yes, of course you are right, x[0] thru x[3].

And as for speed:
My idea is that you will need many increments to go from 19FF to 1B00, and even more to go from 9FFF to B000. The algorithm I suggested will avoid them.
Usually you have to check just one character; if you have an F, you will have to check at least one more character though.

I don't think that there will be a considerable difference in speed with four characters; but for longer numbers it should; for n characters you will never need more than n comparisons, but it could be, for 9FF..F, I think, more than 16^(n-1) increments.

regards

 

[theotyflos]

Hi hoinz,
Thanks again. Here's what I did:

char *next_code (char *code)
{
static char hex_code[5];
int i;
int carry = 1; /* force addition for the LSB digit */
  for ( i = 3; i >= 0; i--) {
    hex_code[i] = code[i];
	if (carry) {
	  switch (hex_code[i]) {
	    case '0':
	    case '1':
	    case '2':
	    case '3':
	    case '4':
	    case '5':
	    case '6':
	    case '7':
	    case '8':
	    case 'B':
	    case 'C':
	    case 'D':
	    case 'E':
		  hex_code[i] ++;
		  carry = 0;
		  break;
	    case '9':
		  hex_code[i] = 'B';
		  carry = 0;
		  break;
	    case 'F':
		  hex_code[i] = '0';
		  carry = 1;
		  break;
	  }
	}
  }
  hex_code[4] = 0;
  return hex_code;
}

Another question: will it be faster if i use a char * instead of seeing the string as an array?

PS. I forgot to mention that I want the function to return a new string, not changing the one I pass in place.

Theophilos.

-----------

There are only 10 kinds of people: Those who understand binary and those who don't.

 

[hoinz]

looks good to me;
and as for your question regarding char* or array, I am not expert with this;
someone else?

 

[ArkM]

Theotyplus,
1st: yes, of course, the last step is to call of sprintf (to obtain a string). But out of loop body: it's key point.

2nd: using of unsigned (int by default) is a common approach. On modern CPUs short arithmetics (as usually) slower than integer (or may be your compiler uses short == int).

3rd: insert the function body in the loop (for speed). In reality your task is not CPU/time-bounded, so the function call seems to be better.

4th: avoid cumbersome and redundant (void) casts in functions calls. It's the same as a comment like

x += 1; /* now add integer constant one to x variable */

5th: never simulate symbolic arithmetics if you want fast, short and clear codes...

Good luck!

 

[theotyflos]

ArkM,

Thank you very much for your comments. I don't quite understand your 5th quote. Are you refering to hoinz's suggestion?

Theophilos.

-----------

There are only 10 kinds of people: Those who understand binary and those who don't.

 

[ArkM]

Yes (of course - in that case...

 

[theotyflos]

Thanks again both of you.


Theophilos.

-----------

There are only 10 kinds of people: Those who understand binary and those who don't.

 

[ArkM]

Theophilos,
your post signature is in a wonderful accordance with this thread theme (see m >>= 4, strchr(...'A') etc...

 

[hoinz]

ArkM,

I think I see your point.
Symbolic arithmetics helps in finding a solution, I couldn't do without it.
In this case I wanted to get rid of those multiple increments.
Of course now we could translate to a solution without symbolic arithmetics to speed things up.
So, for theotyflos's original version, or for your suggestion, this would be:
Increment just once, if there is an 'A', just replace it with a 'B'.
A bit of symbolic arithmetics will show that this suffices.

regards

 

[SamBones]

Actually, this isn't correct. You can't just change any 'A' to a 'B'. The original specs need to be clarified. If the requirement is that it must be the next the closest following hex number that doesn't have an 'A', then just changing 'A's to 'B's is wrong.

For instance, if the number in question is 0x89AB, then the closest next number that has no 'A's is 0x89B0, NOT 0x89BB (the result of just changing the 'A'). Just listing them...
[tt]
0x89AB <-- Staring Value
0x89AC
0x89AD
0x89AE
0x89AF
0x89B0 <-- Next number without an 'A'
0x89B1
0x89B2
0x89B3
0x89B4
0x89B5
0x89B6
0x89B7
0x89B8
0x89B9
0x89BA
0x89BB <-- Result if just changing 'A' to 'B'
[/tt]
So, I think it makes the algorithm much simpler. Add one to the original hex value, then just convert the resulting number to a string, then examine from left to right and when you hit an 'A', change it to a 'B', and then change all the following characters to '0's.

That is, 0x5A7C would become 0x5B00. 0xABCD would become 0xB000. 0xF3A2 would become 0xF3B0.

Hope that helps.