[Skydiver]

This is a simple C++ challenge to let relative new C/C++ programmers exercise their new found skills.

The problem is to implement the classic hex2bin() function. It takes a string of hexadecimal digits as input and returns an integer as the output. For example, the input string "1F" should return 31. It should try to interpret as many hexadecimal digits as it can.

Below is a small test harness. All you need to do is modify the body of hex2bin(). Remember to post your solutions for the body of hex2bin() with [spoiler] tags to keep the challenge fresh for everybody.

For extra credit, uncomment the call to ExtraCreditTest() to try your hand at handling larger values and invalid input. It assumes a 32-bit integer as the native int type. If an integer overflows, your implementation should return -1.

(We ask that C/C++ experts refrain from responding with their solutions until most of the newbies get a chance to post.)

#include <iostream>

int hex2bin(const char *hexString);

void TestIt(char * inputs[], const int check[] )
{
    for(int i = 0; inputs[i] != nullptr; i++)
    {
        int value = hex2bin(inputs[i]);
        std::cout << "Hex string: " << inputs[i]
                  << " is " << value << " in decimal. "
                  << ( value == check[i] ? "Correct" : "Incorrect" )
                  << std::endl;
    }
}

void BasicTest()
{
    char * inputs[] = { "0", "C", "9A", "71", "FFFF", "bad", "CAFE", "f00d", nullptr };
    int check[] = { 0, 0xC, 0x9A, 0x71, 0xFFFF, 0xbad, 0xCAFE, 0xf00d, -1 };

    std::cout << "Basic tests: " << std::endl;
    TestIt(inputs, check);
}

void ExtraCreditTest()
{
    char * inputs[] = { "", "C0FFEE", "0110 65", "edge", "0x12", "$29", "800000000" nullptr };
    int check[] = { 0, 0xC0FFEE, 0x0110, 0xed, 0, 0, -1, -1 };

    std::cout << "Extra credit tests: " << std::endl;
    TestIt(inputs, check);
}

int main()
{
    BasicTest();
    // Uncomment the line below for an extra challenge.
    // ExtraCreditTest();
    return 0;
}

int hex2bin(const char *hexString)
{
    int value = 0;
    // Write your implementation here.
    return value;
}

[jimblumberg]

If you experts and above can't wait, how about opening/replying to a topic in the Experts/Mentors forum.

Jim

[macosxnerd101]

Or perhaps have everyone post their replies using spoiler tags?

[goodsir]

I guess it's considered cheating because I had to wikipedia how exactly to convert hex into an integer, but it was fun anyway... Also, I'm unsure whether the subtraction scheme I use works with everything, but it worked on my computer. Haven't taken a crack at the extracredit yet.

Spoiler

int hex2bin(const char *hexString)
{

    int Sum = 0;
    int len = strlen(hexString)-1;
    for (int exp = len, count = 0; exp >= 0; exp--, count ++)
    {
        char temp = *(hexString + count);
        int difference = (temp > 57) ? 55 : 48;
        if (temp >= 97)
        {
           difference = 87;      
        }
        Sum += ((int)(temp - difference) * (int)pow((double)16, exp)); 
    }
    return Sum;
}

[GWatt]

I think it makes more sense for bin2hex to return a boolean and take a int *. This way you don't run into the edge case of 0xffffffff. It's a perfectly valid number that doesn't overflow but will look like it does.

[Skydiver]

GWatt, on 26 July 2012 - 10:56 PM, said:

I think it makes more sense for bin2hex to return a boolean and take a int *. This way you don't run into the edge case of 0xffffffff. It's a perfectly valid number that doesn't overflow but will look like it does.

Yup, I agree as well. But I figured I'd phrase the challenge in the way most C/C++ students first encounter atoi() and figuring out how to implement it. This way, it's not too far out of their comfort zone. But yes, we get more experience, we figure out that return values that look like valid return value is not really a good thing.

goodsir, on 26 July 2012 - 10:12 PM, said:

I guess it's considered cheating because I had to wikipedia how exactly to convert hex into an integer, but it was fun anyway... Also, I'm unsure whether the subtraction scheme I use works with everything, but it worked on my computer. Haven't taken a crack at the extracredit yet.

Spoiler

int hex2bin(const char *hexString)
{

    int Sum = 0;
    int len = strlen(hexString)-1;
    for (int exp = len, count = 0; exp >= 0; exp--, count ++)
    {
        char temp = *(hexString + count);
        int difference = (temp > 57) ? 55 : 48;
        if (temp >= 97)
        {
           difference = 87;      
        }
        Sum += ((int)(temp - difference) * (int)pow((double)16, exp)); 
    }
    return Sum;
}

Don't be too down on yourself. Consider that you knew how to do your own research, learned a method, and figured out how to write code to implement that method. Some folks can't even get that first step done.

[jimblumberg]

Quote

I guess it's considered cheating because I had to wikipedia how exactly to convert hex into an integer, but it was fun anyway...

In my opinion that's not cheating at all. Part of becoming a good programmer is researching methods and algorithms to accomplish your requirements.

Edit: That is as long as you took time to understand how and why the algorithm functions.

Glad you had some fun.

Jim

This post has been edited by jimblumberg: 27 July 2012 - 01:06 AM

[Skydiver]

Kudos should go to Jim, by the way, for encouraging me to post this challenge. I hope that it proves interesting and fun for everybody.

Even if you've implemented this code before, it maybe fun to try it again or try a different approach. For full disclosure, I implemented two solutions to the problem taking completely different approaches. In one approach, I completely biffed the "edge" case in the extra credit part and I had to stare at my code for about 3 minutes going "Whiskey Tango Foxtrot?" until I found the off-by-one error.

[seijurojushi]

Here's what I got for the conversion bit:

Spoiler

#include <iostream>
#include <string>
#include <cmath>

int hex2bin(const char* hexString);

int main()
{
    char nulll = '\0';
    char* nullptr = &nulll;
    char* inputs[] = {"0", "C", "9A", "71", "FFFF", "Bad", "CAFE", "f00d", nullptr};
    int check[] = {0, 0xC, 0x9A, 0x71, 0xFFFF, 0xBad, 0xCAFE, 0xf00d, -1};
    
    for( int i=0; inputs[i] != nullptr; i++)
    {
         int value = hex2bin(inputs[i]);
         std::cout<<"Hex string: "<<inputs[i]<<" is "<<value<<" in decimal."<<(value == check[i]? "correct" : "incorrect")<<std::endl;
         
    }
    system("pause");
    return 0;
}

int hex2bin(const char* hexString)
{
    int a = 'a';
    int A = 'Z';
    int zero = '0';
    int binary[16];//array ready for binary representation of a 4 digit hex number
    for( int i=0; i<16; i++)
    {
         binary[i] = 0;    
    }
    int size = 0;
    for ( int i=0; hexString[i] != '\0'; i++)//reading hex characters
    {
        int c = hexString[i];
        if(c >= 48 && c < 58)
        {
             c -= 48;
        }
        else if(c >= 65 && c < 71)
        {
             c -= 55;
        }
        else if(c >= 97 && c < 102)
        {
             c -= 87;
        }
//converting each hex char into 4 binary bits (number will be backwards)
        for( int j=(0+4*i); j<(4*(i+1)); j++)
        {
             binary[j] = c%2;
             c /= 2;
        } 
        size++;
    }
    for( int i=0; i<size; i++)//rearranges binary digits to the right order
    {
         for(int j=0, k=3; j<2; j++, k--)
         {
                 int temp = binary[i*4+j];
                 binary[i*4+j] = binary[i*4+k];
                 binary[i*4+k] = temp;
         }
    }   
    int sum = 0;
    for( int i=0; i<size*4; i++)//calculates the value
    {
         sum += binary[i] * (pow(2, size*4-1-i));
    }
    return sum;
}

Not sure if I was allowed to add string and define nullptr, but could not get it to work otherwise

Thank you for the lesson

[baavgai]

Fun!

Right first version:

Spoiler

int hex2bin2(const char *hexString) {
	int value = 0;
	for(;*hexString!=0; hexString++) {
		value *= 0x10;
		char digit = *hexString;
		if (digit>='0' && digit<='9') { value += (digit-'0');
		} else if (digit>='A' && digit<='F') { value += (digit-'A') + 10;
		} else if (digit>='a' && digit<='f') { value += (digit-'a') + 10;
		} else {
			value = -1;
			break;
		}
	}
	return value;
}

This works well enough, but the extra credit test makes wonky assumptions. Like I'd want a partial parse of a string.

To allow for the test, we make a minor change.

Spoiler

int hex2bin(const char *hexString) {
	int value = 0;
	for(;*hexString!=0; hexString++) {
		char digit = *hexString;
		if (digit>='0' && digit<='9') { digit -= '0';
		} else if (digit>='A' && digit<='F') { digit = (digit-'A') + 10;
		} else if (digit>='a' && digit<='f') { digit = (digit-'a') + 10;
		} else {
			break;
		}
		value = (value * 0x10) + digit;
	}
	return value;
}

There is a hold out. However, I believe it makes an invalid assumption as to the correct result. So, I fixed the test:

int check[] = {0, 0xC0FFEE, 0x0110, 0xed, 0, 0, 0x800000000, -1};

It think that's more fair than imposing logic contrary to the compiler.

Also, because parallel arrays are evil... I compulsively fixed the rest of the test

Spoiler

struct TestItem {
	const char *cstr;
	const int answer;
};

void TestIt(const TestItem &item) {
	int value = hex2bin(item.cstr);
	std::cout << "Hex string: " << item.cstr
		<< " is " << value << " in decimal. "
		<< ((value==item.answer) ? "Correct" : "Incorrect")
		<< std::endl;
}

void TestIt(const char *name, TestItem *items) {
	std::cout << name << " tests: " << std::endl;
	for(; items->cstr!=NULL; items++) { TestIt(*items); }
}

void BasicTest() {
	TestItem items[] = { {"0", 0}, {"C", 0xC}, {"9A", 0x9A}, {"71", 0x71}, 
		{"FFFF", 0xFFFF}, {"bad", 0xbad}, {"CAFE", 0xCAFE}, {"f00d", 0xf00d}, {NULL, 0}};
	TestIt("Basic", items);
}

void ExtraCreditTest() {
	TestItem items[] = { {"", 0}, {"C0FFEE", 0xC0FFEE}, {"0110 65", 0x0110}, 
		{"edge", 0xed}, {"0x12", 0}, {"$29", 0}, {"800000000", 0x800000000}, {NULL, 0}};
	TestIt("Extra credit", items);
}

[goodsir]

seijurojushi, on 27 July 2012 - 04:31 AM, said:

Here's what I got for the conversion bit:

Spoiler

#include <iostream>
#include <string>
#include <cmath>

int hex2bin(const char* hexString);

int main()
{
    char nulll = '\0';
    char* nullptr = &nulll;
    char* inputs[] = {"0", "C", "9A", "71", "FFFF", "Bad", "CAFE", "f00d", nullptr};
    int check[] = {0, 0xC, 0x9A, 0x71, 0xFFFF, 0xBad, 0xCAFE, 0xf00d, -1};
    
    for( int i=0; inputs[i] != nullptr; i++)
    {
         int value = hex2bin(inputs[i]);
         std::cout<<"Hex string: "<<inputs[i]<<" is "<<value<<" in decimal."<<(value == check[i]? "correct" : "incorrect")<<std::endl;
         
    }
    system("pause");
    return 0;
}

int hex2bin(const char* hexString)
{
    int a = 'a';
    int A = 'Z';
    int zero = '0';
    int binary[16];//array ready for binary representation of a 4 digit hex number
    for( int i=0; i<16; i++)
    {
         binary[i] = 0;    
    }
    int size = 0;
    for ( int i=0; hexString[i] != '\0'; i++)//reading hex characters
    {
        int c = hexString[i];
        if(c >= 48 && c < 58)
        {
             c -= 48;
        }
        else if(c >= 65 && c < 71)
        {
             c -= 55;
        }
        else if(c >= 97 && c < 102)
        {
             c -= 87;
        }
//converting each hex char into 4 binary bits (number will be backwards)
        for( int j=(0+4*i); j<(4*(i+1)); j++)
        {
             binary[j] = c%2;
             c /= 2;
        } 
        size++;
    }
    for( int i=0; i<size; i++)//rearranges binary digits to the right order
    {
         for(int j=0, k=3; j<2; j++, k--)
         {
                 int temp = binary[i*4+j];
                 binary[i*4+j] = binary[i*4+k];
                 binary[i*4+k] = temp;
         }
    }   
    int sum = 0;
    for( int i=0; i<size*4; i++)//calculates the value
    {
         sum += binary[i] * (pow(2, size*4-1-i));
    }
    return sum;
}

Not sure if I was allowed to add string and define nullptr, but could not get it to work otherwise

Thank you for the lesson

Yeah, I had a problem with nullptr too. It turns out to be a constant introduced in c++ 11.

Quote

C++11 corrects this by introducing a new keyword to serve as a distinguished null pointer constant: nullptr. It is of type nullptr_t, which is implicitly convertible and comparable to any pointer type or pointer-to-member type. It is not implicitly convertible or comparable to integral types, except for bool. While the original proposal specified that an rvalue of type nullptr should not be convertible to bool, the core language working group decided that such a conversion would be desirable, for consistency with regular pointer types. The proposed wording changes were unanimously voted into the Working Paper in June 2008.[2]
For backwards compatibility reasons, 0 remains a valid null pointer constant.

[seijurojushi]

hehe I did hex>bin>decimal...
the sigbature said hex to bin so i started writing that... oh well now i have both

[GWatt]

I did something very similar to baavgai in that I made an actual test case record but with an additional field for valid conversion. I changed the challenge slightly and pass a int * instead of behaving like atoi.

Spoiler

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <ctype.h>
#include <stdbool.h>

typedef struct {
	const char *str;
	uint32_t hex;
	bool valid;
} testcase;

bool hex2bin(const char *str, uint32_t *hexint);
void runTestCases(const testcase *tests, int count);

int main(int argc, char **argv) {
	
	int i;
	uint32_t hexint;
	
	testcase basic_test[]={{"0", 0, true}, {"C", 0xC, true}, {"9A", 0x9A, true}, {"71", 0x71, true},
							{"FFFF", 0xFFFF, true}, {"bad", 0xbad, true}, {"CAFE", 0xCAFE, true}};
	testcase complex_test[]={{"", 0, true}, {"C0FFEE", 0xC0FFEE, true}, {"0110 65", 0x0110, true},
							{"edge", 0xed, true}, {"0x12", 0, true}, {"$29", 0, false},
							{"800000000", 0, false}, {NULL, 0, false}, {"ffffffff",0xffffffff, true}};
	if (argc==1) {
		runTestCases(basic_test, sizeof basic_test/sizeof *basic_test);
		runTestCases(complex_test, sizeof complex_test/sizeof *complex_test);
	}
	for (i=1; i<argc; i++) {
		if (hex2bin(argv[i], &hexint)) {
			printf("%s=%x\n", argv[i], hexint);
		}
		else {
			printf("not a valid 32 bit hex int: %s\n", argv[i]);
		}
	}
	return EXIT_SUCCESS;
}

void runTestCases(const testcase *tests, int count) {
	int i=0;
	uint32_t hexint;
	bool ret;
	
	for (i=0; i<count; i++) {
		ret=hex2bin(tests[i].str, &hexint);
		if (ret&&tests[i].valid&&hexint==tests[i].hex) {
			printf("Case %02d Success: %s==%x\n", i+1, tests[i].str, hexint);
		}
		else if (!ret&&!tests[i].valid) {
			printf("Case %02d Success: Caught invalid hex number: %s\n", i+1, tests[i].str);
		}
		else if (ret&&!tests[i].valid) {
			printf("Case %02d Failure: Reported success when conversion should have failed\n", i+1);
		}
		else if (!ret&&tests[i].valid) {
			printf("Case %02d Failure: Reported failure when conversion should have succeeded\n", i+1);
		}
		else {
			printf("Case %02d Failure: Expected: %x, Got: %x\n", i+1, tests[i].hex, hexint);
		}
	}
}


bool hex2bin(const char *str, uint32_t *hexint) {
	int i=0;
	int digits=0;
	bool ret=true;
	*hexint=0;
	if (str==NULL) {
		ret=false;
		return ret;
	}
	if (!isxdigit(str[0])&&str[0]!='\0') {
		ret=false;
		return ret;
	}
	while (str[i]=='0') {
		i++;
	}
	while (str[i]) {
		if (!isxdigit(str[i])) {
			break;
		}
		if (digits>=8) {
			ret=false;
			break;
		}
		*hexint<<=4;
		if (isdigit(str[i])) {
			*hexint+=str[i]-'0';
		}
		else {
			*hexint+=toupper(str[i])-'A'+10;
		}
		i++;
		digits++;
	}
	
	return ret;
}

[Skydiver]

baavgai, on 27 July 2012 - 05:53 AM, said:

Fun!

Right first version:

Spoiler

int hex2bin2(const char *hexString) {
	int value = 0;
	for(;*hexString!=0; hexString++) {
		value *= 0x10;
		char digit = *hexString;
		if (digit>='0' && digit<='9') { value += (digit-'0');
		} else if (digit>='A' && digit<='F') { value += (digit-'A') + 10;
		} else if (digit>='a' && digit<='f') { value += (digit-'a') + 10;
		} else {
			value = -1;
			break;
		}
	}
	return value;
}

This works well enough, but the extra credit test makes wonky assumptions. Like I'd want a partial parse of a string.

To allow for the test, we make a minor change.

Spoiler

int hex2bin(const char *hexString) {
	int value = 0;
	for(;*hexString!=0; hexString++) {
		char digit = *hexString;
		if (digit>='0' && digit<='9') { digit -= '0';
		} else if (digit>='A' && digit<='F') { digit = (digit-'A') + 10;
		} else if (digit>='a' && digit<='f') { digit = (digit-'a') + 10;
		} else {
			break;
		}
		value = (value * 0x10) + digit;
	}
	return value;
}

There is a hold out. However, I believe it makes an invalid assumption as to the correct result. So, I fixed the test:

int check[] = {0, 0xC0FFEE, 0x0110, 0xed, 0, 0, 0x800000000, -1};

It think that's more fair than imposing logic contrary to the compiler.

Also, because parallel arrays are evil... I compulsively fixed the rest of the test

Spoiler

struct TestItem {
	const char *cstr;
	const int answer;
};

void TestIt(const TestItem &item) {
	int value = hex2bin(item.cstr);
	std::cout << "Hex string: " << item.cstr
		<< " is " << value << " in decimal. "
		<< ((value==item.answer) ? "Correct" : "Incorrect")
		<< std::endl;
}

void TestIt(const char *name, TestItem *items) {
	std::cout << name << " tests: " << std::endl;
	for(; items->cstr!=NULL; items++) { TestIt(*items); }
}

void BasicTest() {
	TestItem items[] = { {"0", 0}, {"C", 0xC}, {"9A", 0x9A}, {"71", 0x71}, 
		{"FFFF", 0xFFFF}, {"bad", 0xbad}, {"CAFE", 0xCAFE}, {"f00d", 0xf00d}, {NULL, 0}};
	TestIt("Basic", items);
}

void ExtraCreditTest() {
	TestItem items[] = { {"", 0}, {"C0FFEE", 0xC0FFEE}, {"0110 65", 0x0110}, 
		{"edge", 0xed}, {"0x12", 0}, {"$29", 0}, {"800000000", 0x800000000}, {NULL, 0}};
	TestIt("Extra credit", items);
}

The partial parse of a string matches the behavior of atoi() which this hex2bin() is trying to parallel.

Nice job swapping to a test record rather than the array. That would have been my preference as well. I was trying to keep things simple so that a newbie who hasn't encountered struct's yet wouldn't be sidetracked by something new. Unfortunately, I shot myself in the foot by introducing nullptr. *sigh*

I'm curious which compiler you are using that has 64-bit integers as its default.

[Skydiver]

GWatt, on 27 July 2012 - 08:27 AM, said:

I did something very similar to baavgai in that I made an actual test case record but with an additional field for valid conversion. I changed the challenge slightly and pass a int * instead of behaving like atoi.

Spoiler

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <ctype.h>
#include <stdbool.h>

typedef struct {
	const char *str;
	uint32_t hex;
	bool valid;
} testcase;

bool hex2bin(const char *str, uint32_t *hexint);
void runTestCases(const testcase *tests, int count);

int main(int argc, char **argv) {
	
	int i;
	uint32_t hexint;
	
	testcase basic_test[]={{"0", 0, true}, {"C", 0xC, true}, {"9A", 0x9A, true}, {"71", 0x71, true},
							{"FFFF", 0xFFFF, true}, {"bad", 0xbad, true}, {"CAFE", 0xCAFE, true}};
	testcase complex_test[]={{"", 0, true}, {"C0FFEE", 0xC0FFEE, true}, {"0110 65", 0x0110, true},
							{"edge", 0xed, true}, {"0x12", 0, true}, {"$29", 0, false},
							{"800000000", 0, false}, {NULL, 0, false}, {"ffffffff",0xffffffff, true}};
	if (argc==1) {
		runTestCases(basic_test, sizeof basic_test/sizeof *basic_test);
		runTestCases(complex_test, sizeof complex_test/sizeof *complex_test);
	}
	for (i=1; i<argc; i++) {
		if (hex2bin(argv[i], &hexint)) {
			printf("%s=%x\n", argv[i], hexint);
		}
		else {
			printf("not a valid 32 bit hex int: %s\n", argv[i]);
		}
	}
	return EXIT_SUCCESS;
}

void runTestCases(const testcase *tests, int count) {
	int i=0;
	uint32_t hexint;
	bool ret;
	
	for (i=0; i<count; i++) {
		ret=hex2bin(tests[i].str, &hexint);
		if (ret&&tests[i].valid&&hexint==tests[i].hex) {
			printf("Case %02d Success: %s==%x\n", i+1, tests[i].str, hexint);
		}
		else if (!ret&&!tests[i].valid) {
			printf("Case %02d Success: Caught invalid hex number: %s\n", i+1, tests[i].str);
		}
		else if (ret&&!tests[i].valid) {
			printf("Case %02d Failure: Reported success when conversion should have failed\n", i+1);
		}
		else if (!ret&&tests[i].valid) {
			printf("Case %02d Failure: Reported failure when conversion should have succeeded\n", i+1);
		}
		else {
			printf("Case %02d Failure: Expected: %x, Got: %x\n", i+1, tests[i].hex, hexint);
		}
	}
}


bool hex2bin(const char *str, uint32_t *hexint) {
	int i=0;
	int digits=0;
	bool ret=true;
	*hexint=0;
	if (str==NULL) {
		ret=false;
		return ret;
	}
	if (!isxdigit(str[0])&&str[0]!='\0') {
		ret=false;
		return ret;
	}
	while (str[i]=='0') {
		i++;
	}
	while (str[i]) {
		if (!isxdigit(str[i])) {
			break;
		}
		if (digits>=8) {
			ret=false;
			break;
		}
		*hexint<<=4;
		if (isdigit(str[i])) {
			*hexint+=str[i]-'0';
		}
		else {
			*hexint+=toupper(str[i])-'A'+10;
		}
		i++;
		digits++;
	}
	
	return ret;
}

Nice job also adding the null pointer to a string as a test case! I was very tempted to add that as a test case. Modern production code should handle such a case, but most of what is taught at schools and in books seems to skip the parameter checks.

seijurojushi, on 27 July 2012 - 08:04 AM, said:

hehe I did hex>bin>decimal...
the sigbature said hex to bin so i started writing that... oh well now i have both

Maybe the long way around, but you learned new things along the way as well. Sounds like you had fun doing this challenge as well!