探索C/C++ 进制转换之美：从原理到应用（二）https://developer.aliyun.com/article/1464272
5.2 复杂进制转换题目
这部分面试题较复杂，测试在实际应用中处理较为复杂的进制转换问题的能力。
面试题4：计算两个二进制字符串的和
问题描述：给定两个二进制字符串 a 和 b，返回它们的和（用二进制表示）。
要求：
- 写一个函数
string add_binary(const string &a, const string &b)，输入为两个二进制字符串 a 和 b，输出为它们的和（二进制表示）。
示例：
输入: a = "1010", b = "110" 输出: "10000"
面试题5：将 IPv4 地址从十进制点分表示法转换为二进制表示
问题描述：给定一个有效的 IPv4 地址 ip，使用点分十进制格式表示。请实现一个函数，将给定的 IPv4 地址从十进制点分表示法转换为 32 位二进制整数表示。
要求：
- 写一个函数
uint32_t ipv4_decimal_to_binary(const string &ip)，输入为一个表示 IPv4 地址的字符串，输出为 32 位二进制整数。
示例：
输入: ip = "192.168.1.1" 输出: 3232235777
面试题6：计算汉明距离
问题描述：给定两个整数 x 和 y，计算它们的汉明距离。汉明距离（Hamming distance）是相应位置上二进制数值不同的位数。
要求：
- 写一个函数
int hamming_distance(int x, int y)，输入为两个整数 x 和 y，输出为它们的汉明距离。
示例：
输入: x = 1, y = 4 输出: 2 原因: 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑
5.3 进制转换与其他技术结合的题目
这部分面试题将进制转换与其他领域（如数据结构、算法等）相结合，测试在实际项目中处理更加负责的问题的能力。
面试题7：二叉树中根到叶路径的二进制求和
问题描述：给定一个由 0 和 1 组成的二叉树，每个根到叶路径表示一个二进制数。从上到下遍历，指定的一个路径构成的二进制数，请计算所有路径的和。
要求：
- 给定树的根结点，请写一个函数
int sum_root_to_leaf(TreeNode* root)，输入为二叉树的根节点，输出为所有二进制路径和。
示例：
输入: 1 / \ 0 1 / \ / \ 1 0 0 1 输出: 22 解释: (100)1 + (101)5 + (110)6 + (111)7 = 22
面试题8：验证 UTF-8 编码
问题描述：UTF-8 是一种变长字节编码，用于表示 Unicode 编码的字符。请验证给定的字节数组是否表示有效的 UTF-8 编码。
要求：
- 写一个函数
bool is_valid_utf8(const vector<int>& data)，输入为表示字节的整数数组，输出为布尔值，表示输入是否为有效的 UTF-8 编码。
示例：
输入: data = [197, 130, 1] 输出: true 解释: 这是有效的 UTF-8 编码，表示字母 "ć"（U+0107）。
面试题9：数字与字母的相互转换
问题描述：给定一个整数，实现整数与字母之间的相互转换。从 1 开始，分别表示字母 A 到 Z。例如，1 对应 A，2 对应 B，…，26 对应 Z。要求不使用任何库函数。
要求：
- 写两个函数
string int_to_alpha(int n)和int alpha_to_int(const string& s)，分别将整数转换为字母字符串和将字母字符串转换为整数。
示例：
输入: 28 输出: "AB" 输入: "AB" 输出: 28
5.4 面试题答案
面试题1：将给定的十进制整数转换为二进制字符串
string decimal_to_binary(int n) { if (n == 0) { return "0"; } string result; while (n > 0) { result = (n % 2 ? '1' : '0') + result; n /= 2; } return result; }
面试题2：将给定的十进制整数转换为十六进制字符串
string decimal_to_hex(int n) { if (n == 0) { return "0"; } const char* hex_digits = "0123456789ABCDEF"; string result; for (int i = 7; i >= 0; --i) { result += hex_digits[(n >> (i * 4)) & 0xf]; } size_t non_zero_pos = result.find_first_not_of('0'); return result.substr(non_zero_pos); }
面试题3：将给定的二进制字符串转换为十进制整数
int binary_to_decimal(const string &s) { int result = 0; for (const char c : s) { result = result * 2 + (c - '0'); } return result; }
面试题4：计算两个二进制字符串的和
string add_binary(const string &a, const string &b) { string result; int i = a.size() - 1, j = b.size() - 1; int carry = 0; while (i >= 0 || j >= 0) { int sum = carry + (i >= 0 ? a[i--] - '0' : 0) + (j >= 0 ? b[j--] - '0' : 0); result = (sum % 2 ? '1' : '0') + result; carry = sum / 2; } if (carry) { result = '1' + result; } return result; }
面试题5：将 IPv4 地址从十进制点分表示法转换为二进制表示
uint32_t ipv4_decimal_to_binary(const string &ip) { uint32_t result = 0; int num = 0, count = 0; for (const char c : ip) { if (c == '.') { result = (result << 8) | num; num = 0; ++count; } else { num = num * 10 + (c - '0'); } } result = (result << 8) | num; return result; }
面试题6：计算汉明距离
int hamming_distance(int x, int y) { int xor_result = x ^ y; int distance = 0; while (xor_result) { distance += xor_result & 1; xor_result >>= 1; } return distance; }
面试题7：二叉树中根到叶路径的二进制求和
int sum_path(TreeNode* node, int path_val) { path_val = (path_val << 1) | node -> val; if (!node -> left && !node -> right) { return path_val; } int total_sum = 0; if (node -> left) { total_sum += sum_path(node -> left, path_val); } if (node -> right) { total_sum += sum_path(node -> right, path_val); } return total_sum; } int sum_root_to_leaf(TreeNode* root) { if (!root) { return 0; } return sum_path(root, 0); }
面试题8：验证 UTF-8 编码
bool is_valid_utf8(const vector<int>& data) { int n_bytes = 0; for (int byte : data) { if (n_bytes == 0) { if (byte >> 5 == 0b110) n_bytes = 1; else if (byte >> 4 == 0b1110) n_bytes = 2; else if (byte >> 3 == 0b11110) n_bytes = 3; else if (byte >> 7 != 0) return false; } else { if (byte >> 6 != 0b10) return false; n_bytes--; } } return n_bytes == 0; }
面试题9：数字与字母的相互转换
string int_to_alpha(int n) { if (n <= 0) { return ""; } string result; while (n > 0) { result = char('A' + (n - 1) % 26) + result; n = (n - 1) / 26; } return result; } int alpha_to_int(const string& s) { int result = 0; for (const char c : s) { result = result * 26 + (c - 'A' + 1); } return result; }
六、结论与展望
经过前五章的学习，我们发现进制转换不仅是编程领域中的基础知识，而且对提高逻辑思维能力和解决实际问题具有很大的帮助。从心理学的角度来看，掌握进制转换原理以及相关应用不仅有助于提升对数学思维的理解，还有利于培养求知欲和语言表达能力。
通过本博客所涉及的实例和面试题，我们可以看到进制转换在计算机科学领域中具有广泛的应用，涉及数据结构、网络编程、编码等多个方面。不论是用于工作还是面试，这些知识点都会为你带来独特的优势。同时，编程面试中出现的进制转换相关问题往往需要在有限的时间内找到合适的解决方案，因此从心理学的角度来说，这些问题具有挑战性，有助于锻炼思维能力和建立心理承受压力的机制。
在未来的工作与学习中，我们相信掌握好进制转换技能将在各个领域产生深远的影响。在本博客的学习过程中，希望大家积极参与讨论，增进共同的理解，并将所学应用到实际问题中。同时，我们期待你将所学到的知识和面试题应用于实际项目中，为计算机科学发展做出更多的贡献。
感谢你的阅读与支持！如果你觉得这篇博客对你的学习有所帮助，欢迎点击收藏并点赞。期待我们在学习的道路上相互激励，共同成长！如有任何问题和建议，欢迎在评论区留言讨论，我们将尽快回复。再次感谢！
