这个算法是如何计算32位整数中的集合位数的?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (20)
int SWAR(unsigned int i)
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

有人能详细解释一下这段代码是如何工作的吗?

提问于
用户回答回答于

逐行查看代码:

第1行:

i = i - ((i >> 1) & 0x55555555);

首先,常数的意义0x55555555是使用Java/gcc样式编写的吗?

0x55555555 = 0b01010101010101010101010101010101
    i           j         i - j
----------------------------------
0 = 0b00    0 = 0b00    0 = 0b00
1 = 0b01    0 = 0b00    1 = 0b01
2 = 0b10    1 = 0b01    1 = 0b01
3 = 0b11    1 = 0b01    2 = 0b10

第2行:

i = (i & 0x33333333) + ((i >> 2) & 0x33333333);

与第一行相比,这句话很简单。首先,注意

0x33333333 = 0b00110011001100110011001100110011

因此,i & 0x33333333取上面计算的两位数,每秒钟扔掉一次

第3行:

return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;

既然0x01010101 = (1 << 24) + (1 << 16) + (1 << 8) + 1,我们有:

k * 0x01010101 = (k << 24) + (k << 16) + (k << 8) + k

热门问答

腾讯云广州一区DNS变更,需要怎么操作?

思潮澎湃轻描淡写的生活,但思潮澎湃
推荐
我也收到相关的通知了,这里分享下~ 2019年1月31日,腾讯云将对广州地区旧的基础网络DNS服务器(10.225.30.181、10.225.30.223)进行下线。在此期间,腾讯云提供最新的DNS服务器供您更新使用。 我们建议您尽快将DNS服务器配置进行更新,并且我们为您提供...... 展开详请

快照容量与费用的比例?如何关闭停用?

帅的惊动我国计算机大神
推荐已采纳
快照已于2019年1月22日0时启动正式商业化进程,商业化后所有存量快照和新产生的快照将根据快照使用的存储容量进行收费。 在快照商业化后,腾讯云仍旧会在国内主要地域为用户提供一定量的免费额度。免费额度策略如下: 免费额度覆盖范围为中国大陆地域,中国香港及海外地域暂无免费快照额...... 展开详请

无服务器云函数的cron表达式问题?

腾讯云serverless团队

腾讯云 · 产品团队 (已认证)

腾讯云无服务器云函数SCF产品
推荐
https://cloud.tencent.com/document/product/583/9708#cron-.E8.A1.A8.E8.BE.BE.E5.BC.8F.E8.AF.AD.E6.B3.95.E4.B8.80.EF.BC.88.E6.8E.A8.E8.8D.90.E...... 展开详请

云服务器-intelS2 标准入门型 带独立ip么?

Eli Qiao

腾讯 · 高级工程师 (已认证)

腾讯云CVM后台高级研发工程师
推荐

购买时,可以配置wan网ip,也可以之后添加eip

购买云服务器后上面的是否配套有数据库(mysql, sql server)和Web服务器等?

西风

renzha.net · 站长 (已认证)

www.renzha.net
推荐已采纳

买了服务器自己安装配置数据库即可,也可以另外选购性能更高,更安全可靠的云数据库。

无服务器云函数添加触发方式以错误码9000失败?

腾讯云serverless团队

腾讯云 · 产品团队 (已认证)

腾讯云无服务器云函数SCF产品
推荐

实在抱歉,最近这两天由于广州区 api 网关集群的配置量已超上限,导致 api 网关无法新增服务。目前 api 网关的研发同学已经在紧急扩容广州区集群了。

所属标签

扫码关注云+社区