C十进制到三进制的基数转换

Question

我正在将整数值转换为三元数（即字符串）。我怀疑应该有一种更好的方法来实现这一点，只需较少的计算工作量。

我的算法直接实现了长除法，可以在十进制和任意基数之间转换数字。

char *get_ternary_str(int value) {
  char buffer[3] = { "000" };
  int dividend = value;

  int i = 0;
  do {
    int remainder = dividend % 3;
    dividend = dividend / 3;
    buffer[i] = ((char)remainder + '0');
    i++;
  } while(dividend >= 1 && i < 3);

  char temp = buffer[2];
  buffer[2] = buffer[0];
  buffer[0] = temp;

  return buffer;
}

即使在这个例子中，三元数是3位长，我的目标是使它成为n位长。也欢迎就如何对n位三元数执行此操作提出建议。

Answer 1

如果您关心的是计算时间，您可以使用一个简单而小的查找表来交换一些内存空间。

把这个C（你的问题的早期版本也是用这种语言提出想法的）片段作为我提出的算法的一个例子。

#include <iostream>
#include <array>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
#include <limits>

std::string ternary_from(int value)
{ 
    // The idea is to elaborate three figures (in base 3) at a time
    constexpr int dim = 3 * 3 * 3;

    // Note the values, are "reversed"
    static const std::array<std::string, dim> inner_parts {
        "000", "100", "200", "010", "110", "210", "020", "120", "220", 
        "001", "101", "201", "011", "111", "211", "021", "121", "221", 
        "002", "102", "202", "012", "112", "212", "022", "122", "222" 
    };

    static const std::array<std::string, dim> parts {
        "", "1", "2", "01", "11", "21", "02", "12", "22", 
        "001", "101", "201", "011", "111", "211", "021", "121", "221", 
        "002", "102", "202", "012", "112", "212", "022", "122", "222" 
    };

    if ( value == 0 )
        return std::string{"0"};

    std::string result;

    // Thanks @Chux for recalling that -INT_MIN is UB
    unsigned tmp = value;
    if ( value < 0 )
        tmp = -tmp;

    // note that 'dim' = 27, so you are performing a third of the calculations
    while (tmp >= dim)
    {
        unsigned remainder = tmp % dim;
        // concatenating a string at the end is easier...
        result += inner_parts[remainder];
        tmp = tmp / dim;
    }
    result += parts[tmp];

    if (value < 0)
        result += '-';

    // now the string needs to be reversed. e.g. 3 -> 10(3), not 01 
    std::reverse(result.begin(), result.end());
    return result;
}

int main()
{
    std::vector<int> tests {
        42, -8, 0, 81, 27, -28, std::numeric_limits<int>::max(), std::numeric_limits<int>::min()
    };

    std::cout << "   decimal           ternary\n";
    for (int i : tests)
    {
        std::cout << std::setw(12) << i << std::setw(23) << ternary_from(i) << '\n';
    }
}

It输出

   decimal           ternary
          42                   1120
          -8                    -22
           0                      0
          81                  10000
          27                   1000
         -28                  -1001
  2147483647   12112122212110202101
 -2147483648  -12112122212110202102

Answer 2

代码有问题。

返回指向局部变量的指针

返回指向本地（非静态）变量的指针是未定义行为（UB）。不要依赖该内存在函数完成后有效。

char *get_ternary_str(int value) {
  char buffer[3] = ...
  ...
  return buffer;  // UB
}

以负数失败

-1%3--

int remainder = dividend % 3;
...
buffer[i] = ((char)remainder + '0');

空间不足

缓冲区[3]对于字符串“000”来说太小，因为空字符需要空间<代码>缓冲区[3]对于一个3位字符的数组来说足够大，但肯定需要一个字符串。

// char buffer[3] = { "000" };
char buffer[3+1] = { "000" };

从未分配过空字符

当然，结果应该是需要空字符“\0”的字符串。为了确保这一点，需要对法规进行修订。

我的目标是使其具有n位数的长度，也欢迎您就如何对n位数的三元数执行此操作提出建议。

需要一个char缓冲区来处理形成的字符串。一个简单的解决方案是传入一个足够大的缓冲区指针，以应对最坏的情况。我建议也传入缓冲区的大小。

下面是处理任意基数2-36的解决方案。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// Maximum buffer size (worst case: INT_MIN and base 2)
#define ITOA_BASE_N (1 + sizeof(int)*CHAR_BIT + 1)

char *itoa_base(char *dest, size_t sz, int i, unsigned base) {
  char buf[ITOA_BASE_N];
  char *s = &buf[sizeof buf - 1];  // set to last character.
  *s = '\0';
  unsigned u = (unsigned) i;  // Use unsigned to cope with INT_MIN ...
  if (i < 0) {
    u = -u;                   // ... as -INT_MIN is UB
  }
  do {
    *(--s) = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[u % base];
    u /= base;
  } while (u);
  if (i < 0) {
    *(--s) = '-';
  }
  size_t size_used = &buf[sizeof buf] - s;
  if (size_used > sz) {
    return NULL;  // or some other error handling.
  }
  return memcpy(dest, s, size_used);
}

该测试使用复合文本进行临时存储，但如果需要，可以传入固定缓冲区。

#define TO_BASE3(x) itoa_base((char [ITOA_BASE_N]){0}, ITOA_BASE_N, (x), 3)

void test3(int x) {
  char *s = TO_BASE3(x);
  // do stuff with `s`, it is valid for until the end of this block
  printf("base10:%11d base3:'%s'\n", x, s);
}

int main(void) {
  test3(0);
  test3(1);
  test3(42);
  test3(-81);
  test3(INT_MAX);
  test3(INT_MIN);
}

输出

base10:          0 base3:'0'
base10:          1 base3:'1'
base10:         42 base3:'1120'
base10:        -81 base3:'-10000'
base10: 2147483647 base3:'12112122212110202101'
base10:-2147483648 base3:'-12112122212110202102'

Answer 3

• 您应该使用malloc动态分配缓冲区。
• 您可以使用memset使用零初始化char数组。
• 最后，您可以数学计算char数组长度。上限为Log[value]base 3将为您提供字符串的字符大小。请记住添加一个额外的char以使用null。

因为您需要建议，所以我不提供代码。但是，如果您需要进一步的帮助，您可以在评论中指出。