Самый быстрый способ преобразовать двоичное в десятичное?

Это зависит от того, что еще вы делаете с числами. Вы можете найти компромисс между небольшой потерей эффективности использования пространства и умеренной потерей эффективности арифметики с высокой точностью в обмен на очень эффективное преобразование в десятичную форму и обратно. Ключ состоит в том, чтобы выполнять арифметические операции с высокой точностью с основанием, которое является степенью 10, а не степенью 2.

Например, вы можете использовать основание 10 000, когда вы упаковываете одну цифру в 16-битное слово и выполняете арифметические операции с цифрами в 32-битных целых числах. (Если вы работаете на 64-битной машине, вы можете удвоить это количество и сделать базу 1 000 000 000.) Этот вид кода относительно эффективен во времени, хотя и не так быстр, как использование собственной мощности двойки, потому что вы не можете воспользоваться преимуществами бит переноса на оборудовании. И вы не можете представить столько же целых чисел в одном и том же количестве битов. Но это умение преобразовывать в десятичные числа и обратно, потому что вы можете преобразовывать отдельные цифры без какого-либо деления в столбик.

Если вам нужно представить полный диапазон чисел от нуля до ((1 << 128) - 1), вы все равно можете это сделать, но добавьте дополнительную цифру, чтобы ваши числа были больше.

Если окажется, что вам действительно нужно дополнительное пространство / скорость (возможно, вы делаете много криптографических 128-битных вычислений), тогда метод одновременного div / mod на 10 - самый быстрый из известных мне методов. Единственная уловка заключается в том, что если маленькие целые числа являются обычным явлением, вы можете обрабатывать их особым образом. (То есть, если все три наиболее значимых 32-битных слова равны нулю, просто используйте собственное деление для преобразования.)

Есть ли хитрый способ реализовать эту функцию, которого я не вижу?

В интерфейсах и реализациях C Дэйва Хэнсона есть длинная глава о многоточной арифметике. Разделение большого числа на одну цифру - особый случай, в котором есть такая эффективная реализация:

int XP_quotient(int n, T z, T x, int y) {
    int i;
    unsigned carry = 0;
    for (i = n - 1; i >= 0; i--) {
        carry = carry*BASE + x[i];
        z[i] = carry/y;
        carry %= y;
    }
    return carry;
}

Для полного понимания полезно иметь книгу, но исходный код по-прежнему намного проще для понимания, чем исходный код GNU. И вы можете легко адаптировать его для использования базы 10,000 (в настоящее время она использует базу 256).

Резюме: если ваше узкое место в производительности - это преобразование в десятичные числа, реализуйте арифметику с множественной точностью с основанием, равным 10. Если собственный размер слова вашей машины равен 32, и вы используете код C, используйте 10 000 в 16-битном слове.

Если ваши значения в основном меньше ULLONG_MAX (18446744073709551615), я бы попытался использовать для них sprintf(buf,"%llu",ullong_val). Бьюсь об заклад, это довольно хорошо оптимизировано в стандартной библиотеке, но синтаксический анализ формата займет несколько циклов.

В противном случае я бы создал функцию bigint_divmod1000000000 (или лучше назовите mod10to9) и использовал бы ее. Потребовалось бы в 9 раз меньше делений, чем bigint_divmod10.

Таблица поиска 8 бит. У вас может быть 4 таблицы поиска по 256 чисел. Первая - от 0 до 256 для байтов LSB, вторая таблица - это первая таблица, умноженная на 256 и так далее.

ТАК, когда вам нужен ваш номер, суммируйте числа из таблицы поиска. Когда вы добавляете, вы можете добавить его как bunary и пройти один проход по каждому байту, чтобы исправить потоки переполнения.

Номер примера 0x12345678 В первой таблице поиска находится под адресом (0x78 = 120), поэтому 0x010200 - это первое число во второй таблице под (0x56 = 87), это 0x0202000106 (0x56 в dec - 22016), в третьей таблице у вас будет 0x03040007080702 и под последней с меткой 0x12, у вас есть 0x030001090809080808 (это не подходит для 32-битной арифметики, но это вы все знаете)

Затем просуммируйте эти числа (как двоичные числа) и пройдите один проход, побайтно для кода переполнения в цикле for выглядит что-то вроде

s=carry+val[i];
val[i]=val[i]&10
carry=s/10; 
//you can put last two operations in table

Если посчитать необходимые для этого операции.

1. (просматривая таблицы и добавляя) 4 справочные таблицы. 16 добавлений (имейте в виду, что когда вам не нужно переносить поток, потому что они не могут произойти)
2. один проход на каждом шаге 3 операции 16 шагов, которые нужно пройти.

пассимистическая верхняя граница 6 * 16 = 100 операций.

РЕДАКТИРОВАТЬ:

Вот код на C ++, который на 30% быстрее, чем наивная реализация.

#include <iostream>
#include <stdint.h>
#include <array>

static uint64_t lu[4][256];

constexpr uint64_t lookup_value(uint64_t n) {
  uint64_t r = 0;
  uint64_t t = 1;
  while (n) {
    uint64_t rem = n % 10;
    n /= 10;
    r += rem * t;
    t *= 256;
  }
  return r;
}

void make_lu() {
  uint64_t step = 1;
  for (int j = 0; j < 4; ++j) {
    uint64_t n = 0;
    for (int i = 0; i < 256; ++i) {
      lu[j][i] = lookup_value(n);
      n += step;
    }
    step *= 256;
  }
}

struct DivMod {
  uint8_t div;
  uint8_t rem;
};

static DivMod dm[256];

void make_dm() {
  for (int i = 0; i < 256; ++i) {
    dm[i].div = i / 10;
    dm[i].rem = i % 10;
  }
}

void init() {
  make_lu();
  make_dm();
}

uint64_t b2d(uint64_t n) {
  uint64_t r = 0;
  for (int i = 0; i < 4; ++i) {
    r += lu[i][(n >> (i * 8)) & 0xff];
  }
  uint64_t r2 = 0;
  uint64_t of = 0;
  for (int i = 0; i < 8; ++i) {
    uint64_t v = ((r >> (i * 8)) & 0xff) + of;
    DivMod &x = dm[v];
    of = x.div;
    r2 += uint64_t(x.rem) << (i * 8);
  }
  return r2;
}

int main() {
  init();
  uint64_t n;
  std::cin >> n;
  std::cout << std::hex << b2d(n) << "\n";
  return 0;
}

Для справки в будущем, вместо реализации типа uint128, я просто использовал символы строки напрямую. Это оказалось намного быстрее, чем переход от строки к uint128 и обратно.

Наиболее быстрое ускорение будет происходить за счет встраивания преобразования, а не вызова функций; это может быть просто отметка bigint_divmod10() inline или использование профильной оптимизации, предлагаемой вашим компилятором.

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

#include <iostream>
#include <cmath>
using namespace std;

#define MathBintodec(arr,len)({int dec=0;int ci_;for(ci_=len;ci_--;)dec+=arr[ci_]*pow(2,len-ci_-1);dec;})

int main(){
    int r[]={1,0,0,1,0,0};
    cout<<MathBintodec(r,6)<<endl;
}

Выход: 36