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

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(使用前将#替换为@)

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

  • 如何使用 LINQ 计算与条件匹配的元素数量

    我尝试了很多事情 但对我来说最合乎逻辑的似乎是这个 int divisor AllMyControls Take p gt p IsActiveUserControlChecked Count AllMyControls是一个集合UserC
  • 读取和写入二进制文件

    我正在尝试编写代码将二进制文件读入缓冲区 然后将缓冲区写入另一个文件 我有以下代码 但缓冲区仅存储文件第一行中的几个 ASCII 字符 没有其他内容 int length char buffer ifstream is is open C
  • 二进制文件的结构验证

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

    这个问题在这里已经有答案了 我认为 我犯了一个非常基本的错误 但我正在使用NSMutableArray这不知何故并没有添加对象 我正在按其方式发送它 我有一个属性 并合成 property nonatomic strong NSMutabl
  • 如何将png二进制数据放入img标签中并将其显示为图像?

    我正在用这个 ajax type GET url template bump1 purse png datatype image png success function data var reader new FileReader rea
  • 如何进行快速但不准确的 InnoDB 行计数?

    PHPMyAdmin常见问题解答有话要说 http www phpmyadmin net documentation faq3 11关于 InnoDB 的大概行数 phpMyAdmin 使用快速方法来获取行数 并且此方法仅在 InnoDB
  • 用 C 将位写入文件

    我有这个字符串 101 我想用 C 语言将其写入文件 而不是文本 101 等 8 位 x 字符 但直接使用字符串作为位 位 1 位 0 和位 1 这样文件将是3位 有可能吗 我在网上搜索并尝试这样做 char c 25 101 FILE b
  • 将 css 宽度字符串转换为常规数字

    在尝试计算隐藏元素的宽度时 我发现 jquery width 对于该元素的宽度返回 0 我发现使用 jquery css width 将通过使用声明的样式宽度返回正确的宽度 即使该值与初始样式表不同 问题是 css width 方法返回一个
  • CakePHP GROUP 和 COUNT 个项目在列表中返回

    我知道这里有一些类似的问题 但它们都是关于使用时的 Model gt find all 但这不是我正在做的 我正在做的 Model gt find list 这就是工作与不工作之间的区别 给定一组产品 我想找到该组中的所有品牌以及每个品牌的
  • 可以匹配具有任意小数位数的非零浮点数的最短正则表达式是什么?

    可以匹配具有任意小数位数的非零浮点数的最短正则表达式是什么 它应该接受像这样的数字 1 5 9652 7 00002 0 8 0 0500 0 58000 0 01 0 000005 0 9900 5 7 5 7 005 但拒绝诸如 02
  • 如何使用 hibernate JPA 2 以二进制形式存储 uuid

    我有一个关于通过休眠持久化 JPA2 在数据库中以二进制形式存储字符串uuid的问题 我现在正在使用这段代码 private UUID id Id Type type uuid char GeneratedValue generator s
  • 将二进制文件转换为图像

    我需要找到一种将二进制文件转换为图像的快速方法 二进制文件由 N 个NN 矩阵 我想将 0 与一种颜色关联 将 1 与另一种颜色关联 我需要对超过 1000 个二进制文件执行此操作 如果可能的话 我想避免使用 MatLab 有没有任何工具
  • 计算数组元素的出现次数/频率

    在 Javascript 中 我试图获取一个初始的数值数组并计算其中的元素 理想情况下 结果将是两个新数组 第一个指定每个唯一元素 第二个包含每个元素出现的次数 不过 我愿意接受有关输出格式的建议 例如 如果初始数组是 5 5 5 2 2
  • Ruby 中的数字运算(需要优化)

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

    这个问题在这里已经有答案了 给定一个列表 首选哪种方法来确定内部元素的数量 var myList new List
  • 是否有将二进制数据打包成 UTF-16 字符串的标准技术?

    在 NET中 我有任意二进制数据存储在byte 例如图像 现在 我需要将该数据存储在string 旧 API 的 注释 字段 有没有标准技术packing将此二进制数据转换为string 我所说的 打包 是指对于任何相当大且随机的数据集 字
  • 具有非常大的数字的除法

    我只是想知道在处理大数字时有哪些不同的除法策略 我所说的大数字是指 50 位数字 例如 9237639100273856744937827364095876289200667937278 82637448262718273966299344
  • 计算包含字母/数字的行数

    我想要实现的目标很简单 但是解释起来有点困难 我不知道在 postgres 中这是否真的可能 我处于相当基础的水平 SELECT FROM WHERE LEFT JOIN ON HAVING 等等基本的东西 我正在尝试计算包含特定字母 数字
  • JavaScript 数字在内存中的大小都相同吗?

    我正在阅读本书的面向 Web 开发人员的专业 JavaScript 似乎所有 ECMAScript 数字都是 binary64 浮点数 这得到了证实这篇 MDN 文章 https developer mozilla org en US do
  • 从 56 位二进制字符串创建 DES 密钥

    我有一个 56 位二进制字符串 我想将其用作 DES 加密的密钥 我在JCA文档网站上找到了以下代码 byte desKeyData byte 0x01 byte 0x02 byte 0x03 byte 0x04 byte 0x05 byt

随机推荐

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

    假设我有一个 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