C base преобразование из десятичного в троичное

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

Код имеет проблемы.

Возвращение указателя на локальную переменную

Возвращением указателя на локальную (нестатическую) переменную является неопределенное поведение (UB). Не полагайтесь на то, что эта память действительна после завершения функции.

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

Сбой с отрицательными числами

-1 % 3 -> -1, поэтому remainder + '0' не будет генерировать символ цифры.

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

Недостаточно места

buffer[3] слишком мало для строки из "000", поскольку для нулевого символа требуется пространство. buffer[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 2

• Вы должны распределять ваш буфер динамически, используя malloc.
• Вы можете инициализировать массив символов с нулями, используя memset.
• И, наконец, вы можете рассчитать длину массива символов математически. Ceiling to Log [value] base 3 даст вам размер символа вашей строки. И, пожалуйста, имейте в виду, чтобы добавить дополнительный символ для использования null.

Из-за того, что вы спрашиваете предложение, я не предоставляю код. Но, если вам нужна дополнительная помощь, вы можете указать в комментарии.

Answer 3

Вы можете обменять некоторое пространство памяти на время расчета, если вас это интересует, используя простую и небольшую справочную таблицу.

Рассмотрим этот фрагмент кода 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';
    }
}

выводит

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

Answer 4

Я выделяю динамическую память в функции main и передаю указатель на функцию. Таким образом, я могу управлять памятью. Для каждого распределения вам нужно освободить место. Я выделяю на 1 элемент больше длины строки для завершения строки. Ваш алгоритм почти не изменился. Я изменил индекс буфера, чтобы избежать переупорядочения элементов буфера.

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

void get_ternary_str(char* buffer, int value, unsigned int n) {
  int dividend = value;

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

  buffer[i] = 0;
}

int main() {
    int n = 5;
    char* buffer = (char*) malloc(n * sizeof(char));

    int value = 31;
    get_ternary_str(buffer, value, n - 1);

    printf("%s", buffer);
    free(buffer);
    return 0;
}

С идеей от Y.Doktur и здесь тот же код с динамической длиной. Я использую указатель на указатель, чтобы передать и получить указатель.

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

char* get_ternary_str(unsigned int value) {
  int n = value > 2 ? 1 + floor(log(value) / log(3)) : 1;
  char* buffer = (char*) malloc((n+1) * sizeof(char));
  int dividend = value;

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

  buffer[i] = 0;
  return buffer;
}

int main() {

  int value = 31;
  char* buffer = get_ternary_str(value);

  printf("%s", buffer);
  free(buffer);
  return 0;
}