查找表设置位计数算法的提示

2024-01-03

我正在寻找设置位计数问题的解决方案(给定一个二进制数,如何有效地计算设置了多少位)。

Here, http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive,我找到了一些方法。

那么查表法呢?我不明白二进制表示/数字的哪些属性使它起作用。

static const unsigned char BitsSetTable256[256] = 
{
#   define B2(n) n,     n+1,     n+1,     n+2
#   define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
#   define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
   B6(0), B6(1), B6(1), B6(2)
};

unsigned int v; // count the number of bits set in 32-bit value v
unsigned int c; // c is the total bits set in v

// Option 1:
c = BitsSetTable256[v & 0xff] + 
   BitsSetTable256[(v >> 8) & 0xff] + 
   BitsSetTable256[(v >> 16) & 0xff] + 
   BitsSetTable256[v >> 24]; 

// Option 2:
unsigned char * p = (unsigned char *) &v;
c = BitsSetTable256[p[0]] + 
    BitsSetTable256[p[1]] + 
    BitsSetTable256[p[2]] + 
    BitsSetTable256[p[3]];


// To initially generate the table algorithmically:
BitsSetTable256[0] = 0;
for (int i = 0; i < 256; i++)
{
   BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
}

特别是我不明白BitsSetTable256首先定义。为什么要定义这些量 B2、B4...?在我看来,它们之后就不再被使用了。

您能否暗示有关二进制表示的进一步文档?

Thanks!


定义是通过模式形成表格。它们是递归宏,B6 使用 B4,B4 使用 B2。 B6(0) 将被分解为:

B4(0), B4(1), B4(1), B4(2)

B4(0) 将被分解为:

0, 1, 1, 2

序列的前几个数字将是:

// 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11
   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3

正如您所看到的,这些是为表中每个索引设置的位数。

算法的其余部分是将数字分解为 8 位块,并对每个块中设置的位数求和,这就是这些行的内容(您可以根据自己的喜好使用选项 1 或选项 2,而不是同时使用两者) :

// Option 1:
c = BitsSetTable256[v & 0xff] + 
    BitsSetTable256[(v >> 8) & 0xff] + 
    BitsSetTable256[(v >> 16) & 0xff] + 
    BitsSetTable256[v >> 24]; 

// Option 2:
unsigned char * p = (unsigned char *) &v;
c = BitsSetTable256[p[0]] + 
    BitsSetTable256[p[1]] + 
    BitsSetTable256[p[2]] + 
    BitsSetTable256[p[3]];

底部的代码:

// To initially generate the table algorithmically:
BitsSetTable256[0] = 0;
for (int i = 0; i < 256; i++)
{
   BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
}

是生成 BitsSetTable256 的不同方式。它在运行时而不是在编译时生成表(这是宏定义的作用)。

附:如果您的目标是足够新的 (SSE4) x86,您可以使用 POPCNT 指令。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

查找表设置位计数算法的提示 的相关文章

  • 读取和写入二进制文件

    我正在尝试编写代码将二进制文件读入缓冲区 然后将缓冲区写入另一个文件 我有以下代码 但缓冲区仅存储文件第一行中的几个 ASCII 字符 没有其他内容 int length char buffer ifstream is is open C
  • 仅使用 Y 数即可得出小于 X 的所有可能性?

    假设我有这些数字 2 25 37 54 54 76 88 91 99 这些是随机的 我需要找到小于 100 的数字的所有组合 并非所有数字都必须在这些组合中使用 示例 2 2 25 37 54 25 我怎样才能在 JavaScript 中实
  • 二进制文件的结构验证

    我正在研究正式指定各种二进制流格式的方法 并使用工具检查流是否符合规范 类似于 XSD 任何 XML 验证工具 或者就像在二进制级别上工作的极其复杂的 grep 表达式 最好不是 这真的很难阅读 有人知道有用的规范 工具吗 理由 我们每天都
  • 在Windows中比较2个二进制文件的工具[关闭]

    Closed 此问题正在寻求书籍 工具 软件库等的推荐 不满足堆栈溢出指南 help closed questions 目前不接受答案 我需要一个工具来比较两个二进制文件 文件相当大 我在互联网上找到的一些免费软件或试用工具不方便用于大文件
  • 可以匹配具有任意小数位数的非零浮点数的最短正则表达式是什么?

    可以匹配具有任意小数位数的非零浮点数的最短正则表达式是什么 它应该接受像这样的数字 1 5 9652 7 00002 0 8 0 0500 0 58000 0 01 0 000005 0 9900 5 7 5 7 005 但拒绝诸如 02
  • Android 数字格式不知为何是错误的,我得到的不是 3.5,而是 3.499999999,为什么?

    我将一些数据存储在数据库中 然后使用游标读取这些数据 所有数据均为 56 45 3 04 0 03 类型 即小数点后两位 现在我想对它们求和 但这似乎并不容易 我得到这些数字c getDouble 3 然后我将它添加到 sum 变量中 如下
  • 删除最低位

    给定一个二进制数 删除最低位的最快方法是什么 01001001010 gt 01001001000 它将在代码中用于迭代变量的位 伪代码如下 while bits 0 index getIndexOfLowestOrderBit bits
  • Ruby 中的数字运算(需要优化)

    Ruby 可能不是最适合这种情况的语言 但我很乐意在我的终端中使用它 所以这就是我要使用的 我需要处理从 1 到 666666 的数字 因此我找出包含 6 但不包含 7 8 或 9 的所有数字 第一个数字是6 下一个16 then 26等等
  • 列表:Count 与 Count() [重复]

    这个问题在这里已经有答案了 给定一个列表 首选哪种方法来确定内部元素的数量 var myList new List
  • 替代位置基础系统(十六进制、八进制、二进制)如何工作?如何将它们转换为十进制?

    我以前在编程课上没有学过这一点 但现在我需要知道它 有哪些学习这些数字以及如何转换它们的好资源 我几乎会像记住乘法表一样记住这些 在我们日常的十进制系统中 基数或radix http en wikipedia org wiki Radix
  • 如何从 wfstream 读取二进制数据?

    我从文件读取数据时遇到一个小问题 我希望能够读取 wstring 以及任意大小的原始数据块 大小以字节为单位 std wfstream stream file c str std wstring comType stream gt gt c
  • 二进制增量存储

    我正在寻找一种二进制增量存储解决方案来版本化大型二进制文件 数字音频工作站文件 使用 DAW 文件时 与用于存储原始数据 波形 的大量数据相比 大多数更改 尤其是在混音结束时 都非常小 如果我们的 DAW 文件有一个版本控制系统 让我们可以
  • 如何获取列中每个不同值的计数? [复制]

    这个问题在这里已经有答案了 我有一个名为 posts 的 SQL 表 如下所示 id category 1 3 2 1 3 4 4 2 5 1 6 1 7 2 每个类别编号对应一个类别 我将如何计算每个类别出现在帖子中的次数一条 SQL 查
  • 反转二进制网络

    如何反转二元方程 以便找到哪些输入将产生给定的输出 Example Inputs i0 through i8 Outputs o0 through o8 Operators XOR AND 二元方程 1 i0 1 i1 0 i2 1 i3
  • 数学 - 映射数字

    如何将 a 和 b 之间的数字线性映射到 c 和 d 之间 也就是说 我希望 2 到 6 之间的数字映射到 10 到 20 之间的数字 但我需要广义的情况 我的脑子炸了 如果您的数字 X 位于 A 和 B 之间 并且您希望 Y 位于 C 和
  • 对带有空白 NVARCHAR 或 NULL 检查的 VARCHAR 索引进行 Count(*) 会导致返回的行数加倍

    我有一张桌子 上面有VARCHAR列及其上的索引 每当一个SELECT COUNT 是在这张表上完成的 该表检查了COLUMN N OR COLUMN IS NULL它返回双倍的行数 SELECT 与相同的where子句将返回正确的记录数
  • 正则表达式允许零,只要它不是第一个数字[重复]

    这个问题在这里已经有答案了 昨天我在这里发布了一个问题正则表达式允许 null 或 1 到 9 数字 https stackoverflow com questions 40354842 regular expression allow n
  • 瞬态 REST 表示

    假设我有一个 RESTful 超文本驱动的服务 用于模拟冰淇淋店 为了帮助更好地管理我的商店 我希望能够显示每日报告 列出所售每种冰淇淋的数量和美元价值 看来这种报告功能可以作为名为 DailyReport 的资源公开 DailyRepor
  • 从一种数字系统转换为另一种数字系统后会有多少位数字

    主要问题 有多少位数字 让我解释 我有一个二进制数 11000000 十进制数是192 转换为十进制后 它有多少位 以十进制表示 在我的示例中 它是 3 位数字 但是 这不是问题 我在互联网上搜索并找到了一种用于整数部分的算法和一种用于小数
  • 除法和乘法 2 的幂

    我在一篇论文中读到 数字除以 2 的幂并乘以 2 的幂是一个微不足道的过程 我在互联网上搜索了很多解释 但没有得到它 任何人都可以用简单的语言解释一下这实际上意味着什么 从位操作的角度来看 这是微不足道的 乘以2相当于左移1位 除法相当于右

随机推荐

  • 为网站的私人测试版添加安全层的最不显眼的方法是什么?

    假设我有一个 ASP NET 站点 在本例中为 MVC 它使用表单身份验证和典型的会员系统 该网站允许经过身份验证的用户和匿名用户 当我将网站作为私人测试版发布时 我想在应用程序之上添加另一层安全性 例如超级用户的 https superu
  • 组件如何对其子组件进行布局?

    我已经使用 React 几个星期了 所以我还远不 是专家 这就是问题所在 我正在构建一些布局其子组件的组件 这是一个Layout可以这样使用 var SomeComponent React createClass render functi
  • 确定列中 NA 值的数量

    我想数一下有多少个NA数据框列中的值 假设我的数据框被称为df 我正在考虑的列的名称是col 我想出的方法如下 sapply df col function x sum length which is na x 这是一个好的 最有效的方法吗
  • Kendo Grid:在 Angular 中获取小部件实例

    我试图在我的 Angular 控制器中获取 Kendo 网格的实例 因此我可以尝试连接一些事件 并调用方法 我知道这可能不是最佳实践 并且可能应该使用自定义指令 但是根据文档 http docs telerik com kendo ui A
  • 在 Guice 中模仿 Spring 配置文件

    在 Spring 中 如果我想要一组用于生产的对象 另一组用于本地开发 测试 我可以使用 Profile注解来指定不同的类 并通过在启动应用程序时提供系统属性来在它们之间进行切换 Guice 中是否有类似的内容 或者我需要自己手动检查某些属
  • 在 javascript 中访问 ASP HiddenField

    我已经在这里和谷歌搜索了几天 试图找出为什么我无法获取 javascript 中隐藏字段变量的值 访问时 该值返回为未定义 我在 UpdatePanel 中有一个 ASP HiddenField 它是 aspx 网页中自定义用户控件的一部分
  • 使用 Vuelidate 进行条件验证?

    我有一个表单 可以根据参数应用不同的验证action 存储在VUEX存储中 我试试这个 data function const validations sendToProject cardProject required recallToB
  • 如何调整背景颜色的大小并调整其位置?

    我有一个图像 当我将其悬停时 背景颜色会发生变化 但我想更改大小和位置 hoverme hover background color f7b0ee border radius 50 transition initial 0 5s ease
  • 如果没有冲突则自动远程合并

    如果没有冲突 有没有办法让推送自动接受并合并 我知道这是一个不好的做法 但我有一个特殊情况 即外围 git 存储库由机器人更新 如果没有冲突 有没有办法让推送自动接受并合并 推理流程应该颠倒过来 只有在尝试合并之后才能知道不存在冲突 当本地
  • 如何在 HTML 渲染器中对 HTML 内容进行分页

    I have a project where HTML code is converted to a PDF using HTML Renderer The HTML code contains a single table The PDF
  • Python 与 JavaScript 中的 HMAC SHA256

    我想用 JavaScript 重新实现某个用 Python 编写的 API 客户端 我无法复制 HMAC SHA256 签名功能 对于某些键 输出是相同的 但对于某些键 输出是不同的 当密钥在解码其 Base64 表示后由可打印字符组成时
  • Python socket.error: [Errno 111] 连接在 ubuntu 12.04 上被拒绝

    我正在尝试将套接字与 python 一起使用 但我不断收到此错误消息 import socket gt gt gt s socket socket socket AF INET socket SOCK STREAM gt gt gt s c
  • Javascript:检查用户是否通过表单提交或简单的链接单击导航离开

    我需要在用户离开页面时提醒他们一些事情 这可以通过 window onUnload 事件来处理 但我还需要检查用户是否通过提交页面上的表单或单击导航链接来导航离开 我可以使用表单的 onSubmit 事件设置一个标志 然后在 window
  • 在同一个表上使用 join 和 limit 子句删除

    我有一个像这样的 MySql 表 Session Id Subscriber Id Status abc 1234 Started bcd 1235 Started bcd 1235 Finished 仅当后面跟着 已完成 时 我才需要删除
  • 通过环境安全地将密码传递给 subprocess.Popen

    我想安全地向用户询问密码 然后将其传递给 subprocess Popen 以运行需要它的命令 我见过这个question https stackoverflow com questions 52989658 python subproce
  • 向 WinJS.Binding.converter() 函数发送多个参数

    有没有一种方法可以将多个参数发送到WinJS Binding converter 功能 考虑以下数据和输出 contactName Tara Miller mainNumber 555 405 6190 alternateNumber 55
  • toGMTstring() 和 toUTCstring() 有什么区别?

    我正在将数据保存在MongoDB http www mongodb org 服务器来自Node js http nodejs org应用程序 使用Mongoose http mongoosejs com docs api html 考虑以下
  • PHP 命名空间与具有静态函数的类

    我应该使用具有静态函数或命名空间的类来更好地组织规模不断增长的 PHP 项目吗 我有 Java 背景 喜欢使用静态变量 函数 这两个功能完全不同 static 关键字使属性或方法在没有实际类实例的情况下可用 http php net man
  • 通过 AJAX 发布的布尔变量在服务器端被视为字符串

    以下是将类和包添加到会话购物车的 AJAX 功能的一部分 jquery部分 function addClassToCart itemId addItemToCart itemId true function addPackToCart it
  • 查找表设置位计数算法的提示

    我正在寻找设置位计数问题的解决方案 给定一个二进制数 如何有效地计算设置了多少位 Here http graphics stanford edu seander bithacks html CountBitsSetNaive http gr