题目描述

给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用补码运算方法。

注意:

十六进制中所有字母(a-f)都必须是小写。
十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符’0’来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。
给定的数确保在32位有符号整数范围内。
不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。

示例 1：

输入:
26
输出:
"1a"

示例 2：

输入:
-1
输出:
"ffffffff"

自己思路

判断当前数是否是负数
- 是则把他转成正数（补码方式）
  
  这里发现一个问题，我的计算机是 64 位的，-1 的补码得到是 FFFF FFFF FFFF FFFF，最终打印出来的结果是 0，在 32 位计算机中的补码是 FFFF FFFF，如果把这个结果放在 64 位机器上打印就是 4,294,967,295，其实这两个结果是等价的，只是忘记了前提
  
  java.lang.Integer#MAX_VALUE = 0x7fffffff; 这个是利用 32 位数字表示正负数所代表 Int 类型最大值的结果，而 32 机器 -1 的补码应该是所有位置都参与，没有负数，所以最大值应该是 232，因此 N 位机器上一个数 + 这个数的补数 = 2N

采用短除法计算十六进制（循环）

代码实现

  /**
   * 计算十六进制
   *
   * @param num num
   * @return String
   */
  public String toHex(int num) {
      long changeNum = num;
      // 是否小于 0
      if (changeNum == 0) {
          return "0";
      } else if (changeNum < 0) {
          // 判断当前数是否是负数，是则把他转成正数（补码方式）
          changeNum = toComplement(changeNum);
      }
      // 采用短除法计算十六进制（循环）
      return getHex(changeNum);
  }
  /**
   * 将正数转成十六进制
   *
   * @param num num
   * @return string
   */
  private String getHex(long num) {
      String[] locations = new String[]
              {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "a", "b", "c", "d", "e", "f"};
      StringBuilder sb = new StringBuilder();
      while (num > 0) {
          sb.insert(0, locations[(int) (num % 16)]);
          num /= 16;
      }
      return sb.toString();
  }
  /**
   * 把负数变成补数（十进制）
   *
   * @param num num
   * @return return
   */
  private long toComplement(long num) {
      return (long) (Math.pow(2, 32) + num);
  }

执行结果

答案思路

位运算

题目要求将给定的整数 num转换为十六进制数，负整数使用补码运算方法。

在补码运算中，最高位表示符号位，符号位是 0 表示正整数和零，符号位是 1 表示负整数。32 位有符号整数的二进制数有 32 位，由于一位十六进制数对应四位二进制数，因此 32 位有符号整数的十六进制数有 8 位。将 num的二进制数按照四位一组分成 8 组，依次将每一组转换为对应的十六进制数，即可得到 num 的十六进制数。

假设二进制数的 8 组从低位到高位依次是第 0 组到第 7 组，则对于第 i 组，可以通过(nums>>(4×i)) & 0xf得到该组的值，其取值范围是 0 到 15（即十六进制的 f ）。将每一组的值转换为十六进制数的做法如下：

对于 0 到 9，数字本身就是十六进制数；
对于 10 到 15，将其转换为 a 到 f 中的对应字母。

对于负整数，由于最高位一定不是 0，因此不会出现前导零。对于零和正整数，可能出现前导零。避免前导零的做法如下：

如果 num=0，则直接返回 0；
如果 num>0，则在遍历每一组的值时，从第一个不是 0 的值开始拼接成十六进制数。

复杂度分析

代码实现

public String toHex(int num) {
    if (num == 0) {
        return "0";
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 7; i >= 0; i--) {
        int val = (num >> (4 * i)) & 0xf;
        if (sb.length() > 0 || val > 0) {
            char digit = val < 10 ? (char) ('0' + val) : (char) ('a' + val - 10);
            sb.append(digit);
        }
    }
    return sb.toString();
}

复杂度分析

时间复杂度：O(k)，其中 k 是整数的十六进制数的位数，这道题中 k=8。无论 num 的值是多少，都需要遍历 num 的十六进制表示的全部数位。
空间复杂度：O(k)，其中 k 是整数的十六进制数的位数，这道题中 k=8。空间复杂度主要取决于中间结果的存储空间，这道题中需要存储 num 的十六进制表示中的除了前导零以外的全部数位。

反思

看了官方的解法，感觉自己的像脱裤子放屁

数据结构与算法

405. 数字转换为十六进制数

题目描述

自己思路

代码实现

答案思路

位运算

代码实现

复杂度分析

反思