MiddleCodeOccasionalNot answered yet
Add two hexadecimal numbers given as strings
Two hex numbers are given as strings, most-significant digit first, with no leading zeros and only characters 0–9 and a–f. Return their sum as a hex string. Example: sum("fed","13") == "1000".
Requirements:
- Schoolbook addition from the least-significant end with carry.
- Handle a final carry that grows the result by one digit (e.g.
ff + ff).
std::string addHex(const std::string& l, const std::string& r) {
// your code here
}Write the implementation.
Walk both strings from the last character toward the first, converting each hex digit to 0–15, summing with a carry. Store sum % 16 as the next output digit and keep sum / 16 as carry. After both ends, emit any remaining carry, then reverse the built string. O(max length).
- ✗Forgetting to emit the final carry, dropping the leading digit of
ff + ff - ✗Padding on the wrong side and misaligning the place values
- ✗Mishandling the a–f digit to value conversion (off by the 10 offset)
- →How would you generalize this to an arbitrary base?
- →Why is processing from the least-significant end necessary for the carry?
Contents
Task
Add two hex numbers given as strings, schoolbook style with carry.
Solution
static int hexVal(char c) { return c <= '9' ? c - '0' : c - 'a' + 10; }
static char hexChar(int v) { return v < 10 ? '0' + v : 'a' + (v - 10); }
std::string addHex(const std::string& l, const std::string& r) {
std::string out;
int i = l.size() - 1, j = r.size() - 1, carry = 0;
while (i >= 0 || j >= 0 || carry) {
int sum = carry;
if (i >= 0) sum += hexVal(l[i--]);
if (j >= 0) sum += hexVal(r[j--]);
out.push_back(hexChar(sum % 16));
carry = sum / 16;
}
std::reverse(out.begin(), out.end());
return out;
}Key points
- Add from the least-significant end, carrying as you go.
- A final carry yields a new most-significant digit (
ff + ff). - Build the result backward and reverse it.
Contents
