草庐IT

c++ - 将 74 位整数转换为基数 31

coder 2024-02-04 原文

生成 UFI number , 我用 bitset大小为 74。要执行 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 的解决方案非常有效

最佳答案

要获得一个数的模 31，你只需要 sum up the digits in base 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;   
}

您可以通过像 how its done here 这样并行运行加法来加速模计算.类似的技术可用于计算模 3、5、7、15... 和 231 - 1

然而，由于问题实际上是关于base conversion 而不是如标题所说的模数，因此您需要为此进行真正的除法。注意 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;
}

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

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

您可以看到相同的移位加法用于 divide by 10和 by 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's answer 的结果都是 CEOPPJ62MK6CPR1和 Wolfram alpha除非你对数字使用不同的符号

关于c++ - 将 74 位整数转换为基数 31，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/51541706/

amp43noreferrernoopenernofollowc++c++11bigintbase-conversionstd-bitset

有关c++ - 将 74 位整数转换为基数 31的更多相关文章

  1. ruby-on-rails - 在 Rails 中将文件大小字符串转换为等效千字节 - 2

    我的目标是转换表单输入，例如“100兆字节”或“1GB”，并将其转换为我可以存储在数据库中的文件大小(以千字节为单位)。目前，我有这个:defquota_convert@regex=/([0-9]+)(.*)s/@sizes=%w{kilobytemegabytegigabyte}m=self.quota.match(@regex)if@sizes.include?m[2]eval("self.quota=#{m[1]}.#{m[2]}")endend这有效，但前提是输入是倍数(“gigabytes”，而不是“gigabyte”)并且由于使用了eval看起来疯狂不安全。所以，功能正常，

  2. ruby - 使用 ruby​​ 将 HTML 转换为纯文本并维护结构/格式 - 2

    我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h

  3. ruby - 将数组的内容转换为 int - 2

    我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值，但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗？ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案 只需将数组映射为整数:@land边注如果你想得到一条线的平均值，你可以这样做:values=@input[x]

  4. ruby - 将散列转换为嵌套散列 - 2

    这道题是thisquestion的逆题.给定一个散列，每个键都有一个数组，例如{[:a,:b,:c]=>1,[:a,:b,:d]=>2,[:a,:e]=>3,[:f]=>4,}将其转换为嵌套哈希的最佳方法是什么{:a=>{:b=>{:c=>1,:d=>2},:e=>3,},:f=>4,} 最佳答案 这是一个迭代的解决方案，递归的解决方案留给读者作为练习:defconvert(h={})ret={}h.eachdo|k,v|node=retk[0..-2].each{|x|node[x]||={};node=node[x]}node[

  5. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  6. ruby-on-rails - Ruby url 到 html 链接转换 - 2

    我正在使用Rails构建一个简单的聊天应用程序。当用户输入url时，我希望将其输出为html链接(即“url”)。我想知道在Ruby中是否有任何库或众所周知的方法可以做到这一点。如果没有，我有一些不错的正则表达式示例代码可以使用... 最佳答案 查看auto_linkRails提供的辅助方法。这会将所有URL和电子邮件地址变成可点击的链接(htmlanchor标记)。这是文档中的代码示例。auto_link("Gotohttp://www.rubyonrails.organdsayhellotodavid@loudthinking.

  7. ruby-on-rails - 使用 ruby​​ 将多个实例变量转换为散列的更好方法？ - 2

    我收到格式为的回复#我需要将其转换为哈希值(针对活跃商家)。目前我正在遍历变量并执行此操作:response.instance_variables.eachdo|r|my_hash.merge!(r.to_s.delete("@").intern=>response.instance_eval(r.to_s.delete("@")))end这有效，它将生成{:first="charlie",:last=>"kelly"},但它似乎有点hacky和不稳定。有更好的方法吗？编辑:我刚刚意识到我可以使用instance_variable_get作为该等式的第二部分，但这仍然是主要问题。

  8. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  9. python ffmpeg 使用 pyav 转换 一组图像 到 视频 - 2

    2022/8/4更新支持加入水印水印必须包含透明图像，并且水印图像大小要等于原图像的大小pythonconvert_image_to_video.py-f30-mwatermark.pngim_dirout.mkv2022/6/21更新让命令行参数更加易用新的命令行使用方法pythonconvert_image_to_video.py-f30im_dirout.mkvFFMPEG命令行转换一组JPG图像到视频时，是将这组图像视为MJPG流。我需要转换一组PNG图像到视频，FFMPEG就不认了。pyav内置了ffmpeg库，不需要系统带有ffmpeg工具因此我使用ffmpeg的python包装p

  10. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

随机推荐