6

要生成UFI 编号，我使用bitset大小为 74 的 a。要执行 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：即使干杯和hth，我终于完成了一堂课。- Alf的解决方案就像一个魅力

4

3 回答 3

3

要获得一个数字的模 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 31 - 1

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

1/31 = 0.000010000100001000010000100001... 32 = 0.(00001) 32

然后 N/31 可以这样计算

N/31 = N×2 -5 + N×2 -10 + N×2 -15 + ...

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

由于模数和除法都使用移位 5，因此您也可以在一个循环中同时执行它们。

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

您可以看到用于除以 10和除以 3的相同移位加法方法。在著名的 Hacker's Delight中还有更多的适当舍入的例子。我没有足够的时间通读这本书来了解他们是如何实现结果校正部分的，所以也许我稍后会回到这一点。如果有人对此有任何想法，将不胜感激。

一种建议是进行定点除法。只需将值左移，以便我们有足够的小数部分稍后进行舍入

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 ，除非您对数字使用不同的符号

于 2018-07-26T17:06:30.730 回答
1

这段代码似乎有效。为了保证结果，我认为您需要进行额外的测试。例如，首先使用少量数字，您可以直接计算结果。

编辑：哦，现在我注意到您发布了所需的结果数字，并且它们匹配。意味着它通常很好，但仍未针对极端情况进行测试。

#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
重组：100000000000000000000000000000101000001000001010000011101011111100010100010
基数 31 位（msd 到 lsd 顺序）：12 14 24 25 25 19 6 2 22 20 6 12 25 27 1
模 31 = 1
于 2018-07-26T16:36:22.717 回答
0

我没有编译伪代码，但是您可以生成对如何转换数字的理解：

// 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;
}
于 2018-07-26T15:23:44.193 回答