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

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

  • 回答 (2)
  • 关注 (0)
  • 查看 (32)
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

热门问答

对象存储COS有没有日志功能?

Hyman Wang

腾讯云 · 高级产品经理 (已认证)

推荐已采纳

你的cos 是否开通了 CDN 加速,如果开通了CDN 加速,可以去 CDN 的控制台下: (统计分析 --- 监控 )页面下拉到底部,可以通过 URL 查看流量情况。

对象存储里的视频能在线播放么?

Jinqn

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

腾讯云COS前端开发
推荐

购买的云数据库里面有什么类型的数据库?有SQLserver吗?可以自己安装SQLserver吗?

帅的惊动我国计算机大神
推荐已采纳
云关系型数据库让您在云中轻松部署、管理和扩展的关系型数据库,提供安全可靠、伸缩灵活的按需云数据库服务。腾讯云关系型数据库提供 MySQL、SQL Server、MariaDB、PostgreSQL 数据库引擎,并针对数据库引擎的性能进行了优化。云关系型数据库是一种高度可用的托管服...... 展开详请

linux如何限制单一ip对服务器的日访问量?

小爱同学

腾讯云 · 技术支持 (已认证)

推荐
您根据当前网站规模和业务了解下【网站管家 WAF】,企业站点可有效抵御恶意攻击,垃圾访问。 图片.png 您反馈网站短信验证码被盗刷,也可结合自己业务,可自行部署iptables进行手动拦截。或其他方式 例如您的网站是nginx,在web配置文件中开启配置HttpLimitR...... 展开详请

兼容性测试只能上传apk测试的吗?

WeTest质量开放平台团队专注游戏,提升品质
推荐

目前不支持公众号的兼容测试,还请知晓

关于群自动解散的问题?

安稳

腾讯科技 · 工单技术支持 (已认证)

推荐
您好,临时群是没有的。云通信的群组只有私有群(Private)、公开群(Public)、聊天室(ChatRoom)、音视频聊天室(AVChatRoom)和在线成员广播大群(BChatRoom)这五种。 您说的这个需求,思路:创建群组时,服务端记录一下时间,到达约定解散的时间以后,...... 展开详请

所属标签

扫码关注云+社区