我想将仅包含整数的字符串转换为字节数组,但要有效存储(因此,没有“ 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}
这是从10到256的基本转换,因此就算法而言,这是您应该寻找的。对于简单的实现,首先对字符串进行2的幂除以长除法。然后将每个余数转换为一个字节:这些字节构成您的输出。您将需要重复分割输入,每个8位余数的字符串组成一个以256为基数的字节,从最低有效位开始(一个字节为一个以256为基数的字节)。重复除法意味着您将前一个除法的商作为下一个除法。
[有些很酷的算法可以将10进制数除以2的幂,比一般的长除法运算要快得多,也更简单。作为提示,让我们举一个例子:510。我们将每个数字除以2,然后将余数* 5馈送到下一个数字。让我们丢弃小于0.5的小数部分:510变为2 * 100 + 5 * 10 +5。然后1 * 100 + 2 * 10 + 2点5。然后6 * 10 +1。然后3 * 10点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 div 4 = 0 * 10 + 7rem1 + 0 rem 0.75(公顷!)因为我们使用10 = 2 * 5的事实,并且以n为基数的符号可以很容易地除以基数的因数,而无需执行长加法,所以以2的除法效果更好:所有运算都限于两个相邻的数字,因此它是线性的成本为N的时间过程。但是对于将基数转换为256的基本操作,您需要进行重复除法,因此成本约为0.5N ^ 2。易于实现,但计算成本很高。
当然,还有比这更好的算法。但是以上内容可以简洁地实现-甚至以质量相当好的库函数的形式实现:
首先,我们定义一个字节数组类型,并将其转储到人类可读的十六进制输出中。为了方便起见,通过指向其数据的指针来引用该对象,并且实现细节在接口的任何地方都没有。构造函数new_Bytes
对数组进行零初始化。还有一种方法可将数组视为位数组,并按顺序排列,以最小尾序(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; }
然后,基本转换执行重复的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;
}