以 256 为基数的算术

Question

我现在正在做一个项目，我需要对基数为 256 的数字进行计算。我正在读取文件的字节并将其存储在 uint8_t 的数组中（a.k.a unsigned char 或 BYTE）。支持的最大数字数据类型不满足我的项目需要。所以字节数组就像自定义 length/size 数据类型 (BigInt).

我现在需要对其进行算术运算，例如：-1, /2, %2。

例如，这是演示我的数字应该如何工作的加法：

9   + 1 = (10)
99  + 1 = (100)
255 + 1 = (1)+(0)<<8
255 + 2 = (1)+(1)<<8

注意：第一个是10，因为10占1位，第三个是1 0，因为它占2位。我也不能将它们转换为整数，因为我必须处理 huge 数字。

我绞尽脑汁想办法在 C 中实现它，但无济于事。

到目前为止我的代码：

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

typedef uint8_t BYTE;
BYTE buffer[1000000000];

void n(){
    printf("\n");
}

int main()
{
    uint32_t  x;
    x = 0; 
    int _len,y;
    char * test    = "test.bin";
    FILE * inptr = fopen(test,"rb");
    uint32_t i=0;
    while(fread(&buffer[i],1,1,inptr));
}

Answer 1

因此，您拥有 2 次运算的能力，可以轻松转换为位运算...这种琐碎的事情不需要 bigint 库。假设你有 number

const int n=1000000000; // number size in bytes
BYTE x[n]; // number bytes let num[0] be LSW (least signifficant Word)

所以涉及的操作是：

mod: y = x%2 = x&1

这是O(1)
```
BYTE y = x[0]&1;
```
结果是一位，因此无需将其存储为 bigint

div: y = x/2 = x>>1

这是O(n)结果也是bigint所以

int i;
BYTE y[n]; // result
BYTE cy; // carry flag
for (cy=0,i=n-1;i>=0;i--) // process all words from MSW to LSW
 {
 y[i] = ((x[i]>>1)&0x7F) | cy; // bitshifted word + last carry
 cy = (x[i]<<7)&0x80; // carry is shifted out lsb of word shifted to msb position
 }

十二月：y=x-1

这是O(n)结果也是bigint所以

int i;
BYTE y[n]; // result
BYTE cy; // carry flag
for (cy=1,i=0;(i<n)&&(cy);i++) // process all words from LSW to MSW
 {
 y[i] = (x[i]-cy)&0xFF; // y[i] = sbc x[i],0
 cy = (x[i]==0x00); // carry
 }

希望我没有犯一些愚蠢的语法错误或其他什么，因为我将其直接编码到这里...

这两个 O(n) 操作都可以就地完成，您只需要在 x[i] 更改之前缓冲实际 x[i] 值或计算进位并缓冲旧进位

在你的情况下，我会使用 32 位 (DWORD) 或 64 位 (QWORD) 而不是 8 位 (BYTE)，因为大多数计算机上的 ALU 是 32 或 64 位

如果您有兴趣实现更多 bigint 内容，请参阅：

Cant make value propagate through carry
Fast bignum square computation
Floating Point Divider Hardware Implementation Details
Schönhage-Strassen multiplication using NTT

[Edit1] dec 优先使用 MSW

int i;
BYTE y[n]; // result
BYTE cy; // carry flag
for (cy=1,i=n-1;(i>=0)&&(cy);i--) // process all words from LSW to MSW
 {
 y[i] = (x[i]-cy)&0xFF; // y[i] = sbc x[i],0
 cy = (x[i]==0x00); // carry
 }

和就地：

int i;
BYTE cy; // carry flag
for (cy=1,i=n-1;(i>=0)&&(cy);i--) // process all words from LSW to MSW
 {
 x[i] = (x[i]-cy)&0xFF; // y[i] = sbc x[i],0
 if (x[i]==0xFF) cy=1; // carry
 }

以 256 为基数的算术

Arithmetic with base 256 number system

c

algorithm

math

biginteger