将74位整数转换为以31为底的整数

Question

要生成UFI编号，我使用大小为74的bitset。要执行UFI生成的步骤2，我需要转换这个数字：

9 444 732 987 799 592 368 290
(10000000000000000000000000000101000001000001010000011101011111100010100010)

进入：

DFSTTM62QN6DTV1

通过将第一表示转换为基31并从表中获得等效字符。

#define PAYLOAD_SIZE 74
// payload = binary of 9444732987799592368290
std::bitset<PAYLOAD_SIZE> bs_payload(payload);
/*
perform modulo 31 to obtain:
12(D), 14(F), 24(S), 25(T), 25, 19, 6, 2, 22, 20, 6, 12, 25, 27, 1
*/    

有没有一种方法可以在不使用外部BigInteger库的情况下对我的位集执行转换？

编辑：我终于完成了BigInteger课程，即使干杯和ht.-Alf的解决方案就像一个魅力

Answer 1

要得到一个数字的模31，只需要将以32为基数的数字相加，就像计算十进制的模3和9一样

unsigned mod31(std::bitset<74> b) {
unsigned mod = 0;
while (!b.none()) {
mod += (b & std::bitset<74>(0x1F)).to_ulong();
b >>= 5;
}
while (mod > 31)
mod = (mod >> 5) + (mod & 0x1F);
return mod;   
}

您可以通过并行运行加法来加速模计算，就像这里所做的那样。类似的技术可用于计算模3、5、7、15…和2³¹-1

• C-非2次幂数模的逐位运算算法
• 有什么简单的方法可以做2^32-1的模数运算吗
• 检查数字是否可被3整除的逻辑

然而，由于问题实际上是关于基转换，而不是标题所说的模，因此您需要为此进行真正的除法。注意1/b是0。(1(在基础b+1中，我们有

1/31＝0.000010000100001000010000100001…₃₂＝0.(00001(_<32>

，然后N/31可以像这个一样计算

N/31=N×2^-5。。。

uint128_t result = 0;
while (x)
{
x >>= 5;
result += x;
}

由于模和除法都使用移位乘5，所以也可以在一个循环中同时执行这两个操作。

然而，这里棘手的部分是如何正确地舍入商。上述方法适用于大多数值，除了31的倍数和2的下一次幂之间的一些值。我已经找到了一种方法来纠正几千个值的结果，但还没有找到一种通用的方法来纠正所有值

你可以看到同样的shift和add方法被用来除以10和3。在著名的《黑客的喜悦》中，有更多的例子采用了适当的四舍五入。我没有足够的时间通读这本书来了解他们是如何实现结果校正部分的，所以也许我稍后会回到这一点。如果有人有任何想法，我们将不胜感激。

一个建议是在定点进行除法运算。只需将值向左移动，这样我们就有足够的分数部分来舍入稍后的

uint128_t result = 0;
const unsigned num_fraction = 125 - 75 // 125 and 75 are the nearest multiple of 5
// or maybe 128 - 74 will also work
uint128_t x = UFI_Number << num_fraction; 
while (x)
{
x >>= 5;
result += x;
}
// shift the result back and add the fractional bit to round
result = (result >> num_fraction) + ((result >> (num_fraction - 1)) & 1)

请注意，您上面的结果是不正确的。我已经确认，Yaniv Shaked的答案和Wolfram alpha的结果都是CEOPPJ62MK6CPR1，除非你对数字使用不同的符号

Answer 2

这段代码似乎可以工作。为了保证结果，我认为你需要做额外的测试。例如，首先使用小数字，您可以直接计算结果。

编辑：哦，现在我注意到你发布了所需的结果数字，它们匹配。这意味着它总体上是好的，但仍然没有针对角落案例进行测试。

#include <assert.h>
#include <algorithm>            // std::reverse
#include <bitset>
#include <vector>
#include <iostream>
using namespace std;
template< class Type > using ref_ = Type&;
namespace base31
{
void mul2( ref_<vector<int>> digits )
{
int carry = 0;
for( ref_<int> d : digits )
{
const int local_sum = 2*d + carry;
d = local_sum % 31;
carry = local_sum / 31;
}
if( carry != 0 )
{
digits.push_back( carry );
}
}
void add1( ref_<vector<int>> digits )
{
int carry = 1;
for( ref_<int> d : digits )
{
const int local_sum = d + carry;
d = local_sum % 31;
carry = local_sum / 31;
}
if( carry != 0 )
{
digits.push_back( carry );
}
}
void divmod2( ref_<vector<int>> digits, ref_<int> mod )
{
int carry = 0;
for( int i = int( digits.size() ) - 1; i >= 0; --i )
{
ref_<int> d = digits[i];
const int divisor = d + 31*carry;
carry = divisor % 2;
d = divisor/2;
}
mod = carry;
if( digits.size() > 0 and digits.back() == 0 )
{
digits.resize( digits.size() - 1 );
}
}
}

int main() {
bitset<74> bits(
"10000000000000000000000000000101000001000001010000011101011111100010100010"
);
vector<int> reversed_binary;
for( const char ch : bits.to_string() ) { reversed_binary.push_back( ch - '0' ); }
vector<int> base31;
for( const int bit : reversed_binary )
{
base31::mul2( base31 );
if( bit != 0 )
{
base31::add1( base31 );
}
}
{ // Check the conversion to base31 by converting back to base 2, roundtrip:
vector<int> temp31 = base31;
int mod;
vector<int> base2;
while( temp31.size() > 0 )
{
base31::divmod2( temp31, mod );
base2.push_back( mod );
}
reverse( base2.begin(), base2.end() );
cout << "Original     : " << bits.to_string() << endl;
cout << "Reconstituted: ";
string s;
for( const int bit : base2 ) { s += bit + '0'; cout << bit; };  cout << endl;
assert( s == bits.to_string() );
}
cout << "Base 31 digits (msd to lsd order): ";
for( int i = int( base31.size() ) - 1; i >= 0; --i )
{
cout << base31[i] << ' ';
}
cout << endl;
cout << "Mod 31 = " << base31[0] << endl;
}

MinGW g++的结果：

原件：10000000000000000000000000000101000001000001010000011101011111100010100010重组：10000000000000000000000000000101000001000001010000011101011111100010100010以31位为基数(msd到lsd顺序(：12 14 24 25 25 19 6 2 20 6 12 25 27 1Mod 31=1

Answer 3

我没有编译psuedo代码，但您可以了解如何转换数字：

// Array for conversion of value to base-31 characters:
char base31Characters[] = 
{
'0',
'1',
'2',
...
'X',
'Y'
};
void printUFINumber(__int128_t number)
{
string result = "";
while (number != 0)
{
var mod = number % 31;
result = base31Characters[mod] + result;
number = number / 31;
}
cout << number;
}