7
\$\begingroup\$

I am designing a cipher and need to convert between bases repeatedly in a loop. I have optimized everything else, but I'm not too familiar with C++ code, and and am trying to figure out how to make the conversion faster.

string digits = "0123456789abcdef";
string tohex(string number) {                        // Decimal to Hexadecimal function
    long length = number.length();
    string result = "";
    vector<long> nibbles;
    for ( long i = 0; i < length; i++ ) {
        nibbles.push_back(digits.find(number[i]));
    }
    long newlen = 0;
    do {
        long value = 0;
        newlen = 0;
        for ( long i = 0; i < length; i++ ) {
            value = (value * 10) + nibbles[i];
            if (value >= 16) {
                nibbles[newlen++] = value / 16;
                value %= 16;
            } else if (newlen > 0) {
                nibbles[newlen++] = 0;
            };
        };
        length = newlen;
        result = digits[value] + result;
    } while (newlen != 0);
    return result;
}
\$\endgroup\$
  • \$\begingroup\$ It's probably a bad idea to store text as a string of digits in the first place. \$\endgroup\$ – 200_success Dec 14 '15 at 22:54
  • \$\begingroup\$ The cipher reads that as an input. \$\endgroup\$ – 54 69 6D Dec 14 '15 at 22:55
  • \$\begingroup\$ It might be worth it to post the whole cipher. This looks like a serious code smell, to me at least. \$\endgroup\$ – Nic Hartley Dec 15 '15 at 3:08
  • \$\begingroup\$ Easier to convert it to a number then convert back to a string. \$\endgroup\$ – Martin York Dec 15 '15 at 7:07
6
\$\begingroup\$

Code Review.

If this is a set of constants you want to chech against then it should by marked as constexpr (or const), that way nobody can actually modify it. Also why pollute the global space with another variable; declare it inside the function (as a static so it only gets initialized once).

string digits = "0123456789abcdef";

Also there is a standard function to check if a character is a hex digit std:: isxdigit().

Pass objects by reference to prevent a copy.

string tohex(string number) {

Since you are not modifying number make it a const reference.

Note: You should return by value. The optimizer will remove the need to copy out of the function so you don't need to worry about a copy here.

Declare variables as close to the point of usage as possible. Here result is declared but not used until the next section of code. So When I start seeing result being used I need to scan up the function a long way to find it.

    long length = number.length();
    string result = "";

This is an interesting way to convert characters into digits.

    vector<long> nibbles;
    for ( long i = 0; i < length; i++ ) {
        nibbles.push_back(digits.find(number[i]));
    }

But: 1) You don't check for invalid input as a result you may push back std::string::npos (a big number that is converted is probably converted to -1 when assigned to long). 2) This is O(n) for every digit. it can be done in O(1).

The standard guarantees that the character-set has all the numbers 0 -> 9 in a contiguous range. So you can convert a character (that is a digit) into a number by subtracting the value of 0 from the character.

char d = number[i];
nibbles.push_back((d >= '0' && d <= '9)
                         ? d - '0'
                         : (d >= 'a' && d <= 'f')
                                ? d - 'a' + 10
                                : (d >= 'A' && d <= 'F')
                                     ? d - 'A' + 10
                                     : -1;

PS. Don't write that. Put it in a function.

I see what you are doing. But the functionality could be a lot neater.

    long newlen = 0;
    do {
        long value = 0;
        newlen = 0;
        for ( long i = 0; i < length; i++ ) {
            value = (value * 10) + nibbles[i];
            if (value >= 16) {
                nibbles[newlen++] = value / 16;
                value %= 16;
            } else if (newlen > 0) {
                nibbles[newlen++] = 0;
            };
        };
        length = newlen;
        result = digits[value] + result;
    } while (newlen != 0);
    return result;
}

This is how I would do it.

How about:

template<class T>
string to_string(T t, ios_base & (*f)(ios_base&)) {

  ostringstream oss;
  oss << f << t;
  return oss.str();
}

string tohex(string number) {

    long value = std::stoi(number, null, 10);
    return std::to_string(value, std::hex);
}
\$\endgroup\$
  • \$\begingroup\$ It makes sense to use a to_string function, and it runs faster. \$\endgroup\$ – 54 69 6D Dec 15 '15 at 20:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.