将数字字符串转换为以二进制表示的字节数组

Question

我想将只包含整数的字符串转换为字节数组，但要有效地存储(所以没有“digits[digitIndex] = string[digitIndex - ‘0’;”)。我希望它们像存储任何类型一样存储:每个字节有 256 种不同的可能性，而不仅仅是前面的错误示例中的 10 种。它还需要保存很多数字(我使用 8 位参数作为大小，所以我相信至少 100 个数字)。编辑:出于个人原因，我也不想使用任何库。

以下是它在函数中的外观示例:

int8_t *stringToBigInt(char *input) {
    uint8_t digitsBase10 = strlen(input);
    uint8_t bytes = ???; //However many bytes to store the result (max 255 bytes in this case)
    int8_t *result = malloc(sizeof(void *) + bytes);
    ... //Code for setting result to input
    return result;
}

这是一个可能的输入和输出示例:

编辑:这是一个简短的示例，仅为简单起见适合 32 位；输入可能远不止一个 32 位(也可能是 64 位)整数

输入:“1234567890”

输出:{01001001, 10010110, 00000010, 11010010}

Answer 1

这是从 base-10 到 base-256 的基本转换，因此就算法而言，这就是您应该寻找的。对于一个简单的实现，首先在字符串上实现长除以 2 的幂。然后将每个余数转换为一个字节:这些字节形成您的输出。您需要重复划分输入，并且每个 8 位余数的字符串形成 base-256 字节，从最低有效位开始(一个字节是一个 base-256 位)。重复除法意味着您将前一个除法的商作为被除数提供给下一个除法。

有一些很酷的算法可以将基数为 10 的数字除以 2 的幂，比广义长除法运算更快且更简单。作为提示，让我们举个例子:510。我们将每个数字除以二，并将余数 *5 提供给下一个数字。让我们去掉小于 0.5 的小数部分:510 变为 2*100 + 5*10 + 5。然后 1*100 + 2*10 + 2 dot 5。然后 6*10 + 1。然后 3*10 dot 5, 2* 10 + 5，然后 1*10 + 2 点 5，然后 6，然后 3，然后 2 点 5，然后 1，然后 0 点 5。

对于 255，我们将得到 127.5、63.5、15.5、7.5、3.5、1.5、0.5。

除以二的更高​​因子是可能的，但需要重复长加法。例如。 33 格 4 = 0*10 + 7rem1 + 0 rem 0.75(哈哈!)。除以 2 效果更好，因为我们使用了 10=2*5 的事实，并且 base-n 表示法可以很容易地除以基数的因子，而无需执行长加法:所有操作都限于两个相邻的数字，所以它是线性的以位数为单位的成本为 N 的时间过程。但是对于base-256的base转换，你需要重复除法，所以成本是~0.5N^2。易于实现但计算成本高。

当然，还有比这更好的算法。但是上面可以简洁地实现——即使是质量相当好的库函数的形式:

首先，让我们定义一个字节数组类型，以及一种将其转储为人类可读的十六进制输出的方法。为方便起见，对象通过指向其数据的指针来引用，实现细节根本不在接口(interface)中的任何位置。构造函数new_Bytes零初始化数组。还有一种方法可以将数组视为位数组，按 Lest-endian 排序(LSB 优先)，并设置(打开)给定位。

// https://github.com/KubaO/stackoverflown/tree/master/questions/decimal-to-binary-54422895
#include <assert.h>
#include <inttypes.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Bytes Class Interface

typedef uint8_t *Bytes;
typedef const uint8_t *cBytes;

Bytes new_Bytes(size_t size);
size_t Bytes_size(cBytes bytes);
void Bytes_truncate(Bytes bytes, size_t new_size);
void free_Bytes(cBytes bytes);
char *Bytes_to_hex(cBytes bytes);

static inline void Bytes_set_bit(Bytes const bytes, size_t const bit_num) {
   bytes[bit_num / 8] |= 1 << (bit_num % 8);
}

然后，就地执行除以 2，标志提供基本转换所需的附加信息——尤其是余数。从基数 10 到基数 256 的转换使用除法并返回新的 Bytes大批。

// Division and Base Conversion Interface

typedef enum {
   REMAINDER = 1,           /* there is a non-zero remainder */
   ZERO = 2,                /* the quotient is zero or null */
   NULL_DECIMAL = 4,        /* the dividend is null or empty */
   NON_DECIMALS = 8,        /* division was terminated on non-decimal characters */
   LEADING_ZERO_COUNT = 16, /* count of leading zeroes in the quotient */
   LEADING_ZERO_COUNT_MASK = ~(LEADING_ZERO_COUNT - 1),
   CLR_CARRY_MASK = ~REMAINDER,
   CLR_ZERO_MASK = ~ZERO,
} DivFlags;

DivFlags divide_by_2(char *decimal);
Bytes base_10_to_256(const char *decimal);

除法以十进制表示形式进行，从最高有效位到最低有效位。每个数字与前一个数字除法的余数合并，然后除以 2。余数在数字除法之间进行。除最低有效位后，余数在标志中输出。

这些标志大多是不言自明的，但 LEADING_ZERO_COUNT不完全——因此对它的访问是通过访问器函数实现的。 LEADING_ZERO_COUNT是前导零计数的单位。当除法通过十进制表示时，它将计算前导零，将它们乘以该单位，并将其与标志合并。为了提取计数，标志除以单位。

// Division and Base Conversion Implementation

static inline int leading_zero_count(DivFlags const flags) {
   return (flags & LEADING_ZERO_COUNT_MASK) / LEADING_ZERO_COUNT;
}

static inline void saturated_inc_leading_zero_count(DivFlags *flags) {
   if ((*flags & LEADING_ZERO_COUNT_MASK) != LEADING_ZERO_COUNT_MASK)
      *flags += LEADING_ZERO_COUNT;
}

DivFlags divide_by_2(char *decimal) {
   DivFlags flags = ZERO;
   if (!decimal) return flags | NULL_DECIMAL;
   char c;
   while ((c = *decimal)) {
      if (c < '0' || c > '9') return flags | NON_DECIMALS;
      c = c - '0' + ((flags & REMAINDER) ? 10 : 0);
      if (c & 1)
         flags |= REMAINDER;
      else
         flags &= CLR_CARRY_MASK;
      c >>= 1;
      assert(c >= 0 && c <= 9);
      if (c)
         flags &= CLR_ZERO_MASK;
      else if (flags & ZERO)
         saturated_inc_leading_zero_count(&flags);
      *decimal++ = c + '0';
   }
   return flags;
}

然后，base 转换执行重复除以 2，并将余数位移动到字节数组中，如下所示:

首先，基本转换获取十进制表示的副本，并分配适当大小的输出字节数组。

static void base_10_to_256_impl(Bytes const bytes, char *decimal);

Bytes base_10_to_256(const char *const decimal) {
   assert(decimal);
   size_t const dec_len = strlen(decimal);
   char *const dec_buf = malloc(dec_len + 1);
   if (!dec_buf) return NULL;
   memcpy(dec_buf, decimal, dec_len + 1);

   size_t const BASE_RATIO_NUM = 416, /* ceil(log(10)/log(256)*1000) */
       BASE_RATIO_DENOM = 1000;
   assert(dec_len <= (SIZE_MAX / BASE_RATIO_NUM));
   size_t const len = (size_t)(dec_len * BASE_RATIO_NUM / BASE_RATIO_DENOM) + 1;
   Bytes const bytes = new_Bytes(len);  // little-endian
   if (bytes) base_10_to_256_impl(bytes, dec_buf);
   free(dec_buf);
   return bytes;
}

然后，在实现的“肉”中，函数迭代输出位，重复将十进制表示除以 2，并将每个位设置为余数位的值。

static void base_10_to_256_impl(Bytes const bytes, char *decimal) {
   size_t const len = Bytes_size(bytes);
   for (size_t bit_num = 0;; bit_num++) {
      DivFlags const flags = divide_by_2(decimal);
      assert(!(flags & NULL_DECIMAL));
      decimal += leading_zero_count(flags);
      if (flags & ZERO && !(flags & REMAINDER)) {
         size_t const new_len = ((bit_num + 7) / 8);
         Bytes_truncate(bytes, new_len);
         break;
      }
      // here, there are still non-zero bits - in the dec[imal] and/or in the carry
      assert((bit_num / 8) < len);
      if (flags & REMAINDER) Bytes_set_bit(bytes, bit_num);
   }
}

我们现在可以添加一些测试:

// Tests

void check_bytes(const char *const decimal, const char *const bytes_expected,
                 size_t const bytes_len, const char *const hex_expected) {
   cBytes const bytes = base_10_to_256(decimal);
   assert(bytes && Bytes_size(bytes) == bytes_len);
   assert(memcmp(bytes, bytes_expected, bytes_len) == 0);
   char *const hex = Bytes_to_hex(bytes);
   assert(hex && strcmp(hex, hex_expected) == 0);
   printf("%s\n", hex);
   free(hex);
   free_Bytes(bytes);
}

int main() {
   check_bytes("4294967297" /* 2^32+1 */, "\1\0\0\0\1", 5, "01 00000001");
   check_bytes("4294967296" /* 2^32   */, "\0\0\0\0\1", 5, "01 00000000");
   check_bytes("4294967295" /* 2^32-1 */, "\xFF\xFF\xFF\xFF", 4, "FFFFFFFF");
   check_bytes("16777217" /* 2^24+1 */, "\1\0\0\1", 4, "01000001");
   check_bytes("16777216" /* 2^24   */, "\0\0\0\1", 4, "01000000");
   check_bytes("16777215" /* 2^24-1 */, "\xFF\xFF\xFF", 3, "FFFFFF");
   check_bytes("256", "\0\1", 2, "0100");
   check_bytes("255", "\xFF", 1, "FF");
   check_bytes("254", "\xFE", 1, "FE");
   check_bytes("253", "\xFD", 1, "FD");
   check_bytes("3", "\3", 1, "03");
   check_bytes("2", "\2", 1, "02");
   check_bytes("1", "\1", 1, "01");
   check_bytes("0", "\0", 1, "00");
}

Bytes的执行类结束示例:

// Bytes Implementation

struct BytesImpl {
   size_t size;
   uint8_t data[1];
};
static const size_t Bytes_header_size = offsetof(struct BytesImpl, data);
_Static_assert(offsetof(struct BytesImpl, data) == sizeof(size_t),
               "unexpected layout of struct BytesImpl");

Bytes new_Bytes(size_t size) {
   assert(size <= SIZE_MAX - Bytes_header_size);
   if (!size) size++;
   struct BytesImpl *const impl = calloc(Bytes_header_size + size, 1);
   if (!impl) return NULL;
   impl->size = size;
   return &impl->data[0];
}

static const struct BytesImpl *Bytes_get_const_impl_(cBytes const bytes) {
   return (const struct BytesImpl *)(const void *)((const char *)bytes -
                                                   Bytes_header_size);
}

static struct BytesImpl *Bytes_get_impl_(Bytes const bytes) {
   return (struct BytesImpl *)(void *)((char *)bytes - Bytes_header_size);
}

size_t Bytes_size(cBytes const bytes) { return Bytes_get_const_impl_(bytes)->size; }

void Bytes_truncate(Bytes const bytes, size_t new_size) {
   size_t *const size = &Bytes_get_impl_(bytes)->size;
   if (!new_size) {
     new_size++;  // we always leave one byte in the array
     bytes[0] = 0;
   }
   assert(*size);
   if (*size <= new_size) return;
   *size = new_size;
}

void free_Bytes(cBytes const bytes) {
   if (bytes) free((void *)(intptr_t)(const void *)Bytes_get_const_impl_(bytes));
}

char *Bytes_to_hex(cBytes const bytes) {
   size_t n = Bytes_size(bytes);
   size_t spaces = (n - 1) / 4;
   char *const out = malloc(n * 2 + spaces + 1);
   if (out)
      for (char *o = out; n;) {
         uint8_t const c = bytes[n - 1];
         snprintf(o, 3, "%02" PRIX8, c);
         o += 2;
         n--;
         if (n && n % 4 == 0) {
            assert(spaces);
            *o++ = ' ';
            spaces--;
         }
      }
   return out;
}