C 中大于 8 个字节的数字

Question

我正在编写一些代码来处理 C 中大于 8 个字节的数字（不适合 unsigned long）。在本例中，我将使用 16 个字节（128 位）作为宽度。这些数字是无符号整数（没有小数位）。它们存储为无符号字符数组，例如：

unsigned char n[16];

我已经设法让加法工作（它像 C 中的无符号数一样工作，所以如果你有一个 0xffffffffffffffffffffffffffffffff (2**128) 的数字并且你要添加 1 你会得到 0。我已经设法使加法起作用，但我无法使减法起作用。我认为它与加法的代码类似，但我似乎无法得到它上班。

附加码：

//a and b are numbers
unsigned char *add(unsigned char *a, unsigned char *b){
    unsigned char *c = malloc(NUM_SIZE);
    //d is the carry and c is the output number
    unsigned short d = 0;

    if(!c){
        return NULL;
    }
    for(int i = 0; i < NUM_SIZE; i++){
        c[i] = 0;
    }
    for(int i = NUM_SIZE * 2 - 1; i >= 0; i--){
        d += a[i % NUM_SIZE] + b[i % NUM_SIZE];
        c[i % NUM_SIZE] = d % 256;
        d >>= 8;
    }
    return c;
}

NUM_SIZE定义为16（字节数的宽度）

我尝试过的：

//changing the signs to minuses
d -= a[i % NUM_SIZE] - b[i % NUM_SIZE];

//changing the some signs to minuses
d -= a[i % NUM_SIZE] + b[i % NUM_SIZE];
//or
d += a[i % NUM_SIZE] - b[i % NUM_SIZE];

//looping through the number backwards
for(int i = 0; i < NUM_SIZE * 2; i++)

Answer 1

可能会有一些__int128_t。但是如果你的编译器不支持它，你可以用你拥有的最大类型定义一个带有 hi 和 lo 的结构。在 C++ 中，您还可以添加类似于您从其他 int_t-s.

了解的运算符的运算符

typedef struct uint128 {
    uint64_t lo, hi; // lo comes first if you want to use little-endian else hi comes first
} uint128_t;

如果你想将大小加倍，你可以在类似的结构中使用 uint128_t。

编辑：增加int128的简单函数：

int128_t& int128_increase(int128_t& value) {
    // increase the low part, it is 0 if it was overflown
    // so increase hi
    if (!(++value.lo)) {
        ++value.hi;
    };
    return value;
};

编辑： ints 的运行时缩放版本，我使用单词，因为它在访问内存方面更快：

typedef struct uint_dynamic {
    // the length as a multiple of the wordsize
    size_t length;
    size_t* words;
} uint_dynamic_t;

uint_dynamic_t& uint_dynamic_increase(uint_dynamic_t& value) {
    size_t* ptr = value.words; size_t i = value.length;
    while(i && !(++*ptr)) { ++ptr; --i; };
    return value;
};

或者，如果您想要一些恒定的大小，请将其清楚地放入结构中。

#define uint_fixed_SIZE (16 / sizeof(size_t))
typedef struct uint_fixed {
    size_t words[uint_fixed_SIZE];
} uint_fixed_t;

uint_fixed_t& uint_fixed_increase(uint_fixed_t& value) {
    size_t* ptr = value.words; size_t i = uint_fixed_SIZE;
    while(i && !(++*ptr)) { ++ptr; --i; };
    return value;
};

这可以重写为 #define 宏，您可以在其中用参数替换特定值。通过定义特定值并包含一个文件，它具有类似的功能：

文件fixed_int.h

// note that here is no #ifndef FILE_H or #pragma once
// to reuse the file

#define _concat1(a, b) a ## b
#define _concat(a, b) _concat1(a, b)
#define _size (-((-fixed_int_size) / sizeof(size_t) / 8))
#ifndef fixed_int_name
    #define _name concat(uint_, fixed_int_size)
#else
    #define _name fixed_int_name
#endif
#define _name_(member) _concat(_concat(_name, _), member)

typedef struct _name {
    size_t words[_size];
} _name_(t);

_name_(t)& _name_(increase)(_name_(t)& value) {
    size_t* ptr = value.words; size_t i = _size;
    while(i && !(++*ptr)) { ++ptr; --i; };
    return value;
};

// undef all defines!
#undef _concat1
#undef _concat
#undef _size
#undef _name
#undef _name_

文件my_ints.h

//...

// the following lines define the type uint128_t and the function uint_128_t& uint128_increase(uint128_t&)
#define fixed_int_name uint128 // is optional
#define fixed_int_size 128
#include"fixed_int.h"
#undef fixed_int_size
#undef fixed_int_name

//...

Answer 2

您可能想要使用 arbitrary-precision arithmetic, a.k.a. as bigint or bignum. You should use a library for that (because bignum algorithms are very clever and use some assembler code). I recommend GMPlib. See also 。

Answer 3

NUM_SIZE * 2 对 malloc(NUM_SIZE); ... for(int i = NUM_SIZE * 2 - 1 没有意义。只需要 NUM_SIZE 次迭代循环。

修复代码

#define NUM_SIZE 8
//a - b
unsigned char *sub(const unsigned char *a, const unsigned char *b) {
  unsigned char *c = malloc(NUM_SIZE);
  if (!c) {
    return NULL;
  }

  // zeroing `c[]` not needed.  Retain that code if desired

  int d = 0;  // Use signed accumulator to save the "borrow"

  // drop *2
  for (int i = NUM_SIZE - 1; i >= 0; i--) {
    d += a[i] - b[i];                // Perform the subtraction
    c[i] = d;                        // Save the 8 least significant bits in c[]
    d = (d - c[i]) / (UCHAR_MAX+1);  // Form the "borrow" for the next loop
  }
  // If d<0 at this point, b was greater than a
  return c;
}

可以进行各种性能改进，但首先要使功能正确。

Answer 4

数字有一个 "base" 来确定每个数字的范围（例如 "base 10" 是十进制）。

一个 uint8_t 是 "base 256" 中的一个数字。一个 uint16_t 是 "base 65536" 中的一个数字。一个 uint32_t 是 "base 4294967296" 中的单个数字。

对于数学运算，性能受位数的影响很大。通过使用更大的基数，相同的数字需要更少的数字，从而提高性能（直到超过 CPU 的本机字长）。

对于无符号数的减法：

#define DIGITS 4

int subtract(uint32_t *result, uint32_t *src1, uint32_t *src2) {
    int carry = 0;
    int oldCarry;
    int i;

    for(i = 0; i < DIGITS; i++) {
        oldCarry = carry;
        if(src2[i] < src1[i]) {
            carry = 1;
        } else if( (src2[i] == src1[i]) && (oldCarry != 0) ) {
            carry = 1;
        } else {
            carry = 0;
        }
        result[i] = src1[i] - src2[i] - oldCarry;
    }
    return carry;
}

Answer 5

只是一个想法（未编译）：

void not( unsigned char* a, unsigned int n )
{
  for ( unsigned int i = 0; i < n; ++i )
    a[i] = ~a[i];
}

void inc( unsigned char* a, unsigned int n )
{
  for ( unsigned int i = 0; i < n; ++i )
    if ( ++a[i] )
      return;
}

void add( unsigned char* c, unsigned char* a, unsigned char* b, unsigned int n )
{
  for ( unsigned int i = 0, r = 0; i < n; ++i )
    c[i] = r = a[i] + b[i] + ( r >> 8 );
}

void sub( unsigned char* c, unsigned char* a, unsigned char* b, unsigned int n )
{
  not( b, n );
  add( c, a, b, n );
  not( b, n ); // revert
  inc( c, n );
}

C 中大于 8 个字节的数字

Numbers bigger than 8 bytes in C

c

numbers

arbitrary-precision