基本256位系统的算术运算 [英] Arithmetic with base 256 number system
问题描述
我现在正在一个项目中，我需要对基数为256的数字进行计算.我正在读取文件的字节并将其存储在uint8_t(也称为unsigned char或BYTE)数组中.支持的最大数字数据类型不能满足我的项目的需求.因此，字节数组的作用类似于自定义的length/size数据类型(BigInt).
I am working on a project right now where I need to perform calculations for numbers with base 256. I am reading bytes of a file and storing it in an array of uint8_t (a.k.a unsigned char or BYTE). The largest supported number data type doesn't satisfy the needs of my project. So the array of bytes is acting like a custom length/size data type (BigInt).
我现在需要对其进行算术运算，例如:-1, /2, %2.
I now need to perform arithmetic on it like: -1, /2, %2.
例如，这是加法的样子，以演示我的数字应如何工作:
For example this is how addition looks like to demonstrate how my numbers should work:
9 + 1 = (10)
99 + 1 = (100)
255 + 1 = (1)+(0)<<8
255 + 2 = (1)+(1)<<8
注意:第一个数字是10，因为10中的1占1位，而第三个数字是1 0，因为10中的2位占1位.另外，我无法将它们转换为整数，因为我必须处理巨大数字.
Note: First one's is 10 as in 10 is occupying 1 digit whereas the third one is 1 0 as in it's occupying 2 digits. Also I cant convert them to integers because I have to deal with huge numbers.
我正在绞尽脑汁，试图思考用C语言实现此方法的方法，但无济于事.
I am racking my brain trying to think of ways to implement this in C but to no avail.
到目前为止，我的代码:
My code so far:
#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));
}
推荐答案
因此，您拥有2个操作的强大功能，可以轻松将其转换为位操作...这样的琐碎性不需要bigint lib.假设您有电话号码
So you have power of 2 operations which can be easily converted to bit operations... no bigint lib is needed for such triviality. Let assume you got 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
mod:
y = x%2 = x&1
这是O(1)
BYTE y = x[0]&1;
结果是一点点，因此无需将其存储为bigint
result is single bit so no need to store it as bigint
div:y = x/2 = x>>1
div: y = x/2 = x>>1
这是O(n)，结果也是bigint，所以
this is O(n) and the result is also bigint so
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
dec: y=x-1
这是O(n)，结果也是bigint，所以
this is O(n) and the result is also bigint so
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
}
希望我没有犯一些愚蠢的语法错误，而是直接将其编码到这里...
Hope I did not make some silly syntax error or something as I coded this directly into here...
这两个O(n)操作都可以就地完成，您只需缓冲x[i]的实际值或在x[i]更改之前计算进位并缓冲旧的进位
Both O(n) operations can be done in-place you just need to buffer actual x[i] value or compute carry before x[i] change and buffer old carry
在您的情况下，我将使用32位(DWORD)或64位(QWORD)而不是8位(BYTE)，这将提高速度，因为大多数计算机上的 ALU 为32或64反正
In your case I would use 32bit (DWORD) or 64bit (QWORD) instead of 8bit (BYTE) that will boost the speed as the ALU on most computers is 32 or 64 bit anyway
如果您对实现更多bigint东西感兴趣，请参见:
If you're interested in implementing more of the bigint stuff see:
- Cant make value propagate through carry
- Fast bignum square computation
- Floating Point Divider Hardware Implementation Details
- Building a logarithm function in C without using float type
- Schönhage-Strassen multiplication using NTT
[Edit1] dec首先用于MSW
dec for MSW first
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位系统的算术运算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
