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

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

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

热门问答

域名注册时写了企业,可以转为个人的吗?

滑稽园扛把子

Swoole · PHP开发工程师 (已认证)

As a PHP Developer
推荐
可以的,操作如下 登录控制台 登录 腾讯云控制台。 选择 “云产品 > 域名与网站 > 域名注册”,进入 “域名服务” 页面,查看已购买的所有域名信息。 修改/过户域名信息 在需要修改域名信息的域名行中,单击【更多】,选择【域名信息修改】。如下图所示: 也可直接单击需要修改域名信...... 展开详请

如何按照上传时间顺序,获取cos bucket 中的object信息?

波斯狗儿对象存储产品经理
推荐
对象存储是 KV 有序存储,只能按对象键 UTF-8 字符顺序排。详细了解对象的概念:https://cloud.tencent.com/document/product/436/13324 如果需要按时间列表,需要在上传时就指定好路径,这样列表的时候也是按顺序的。比如 pho...... 展开详请

云开发环境和开发者自己的服务器能连通吗?

李成熙heyli

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

腾讯高级工程师,专注于工程化及性能优化。 https://github.com/lcxfs1991
可以的请参考这份教程: https://github.com/TencentCloudBase/mp-book/blob/master/guide/readme.md#3-%E5%9C%A8%E8%87%AA%E5%B7%B1%E7%9A%84%E6%9C%8D%E5%8A%A1...... 展开详请

腾讯云 COS 怎么才能外链调用 m3u8 到别的网站播放?

滑稽园扛把子

Swoole · PHP开发工程师 (已认证)

As a PHP Developer
推荐
设置公有读私有写:当访问对象时,COS 读取到对象的权限为公有读,此时无论存储桶为何种权限,对象都可以被直接下载 设置步骤 登录 对象存储控制台,选择左侧菜单栏【存储桶列表】,进入存储桶列表页面。单击需要修改对象权限的对应存储桶,进入存储桶。 📷 找到需要设置权限的对象(如 e...... 展开详请

云通信IM 可以发送语音消息吗?

应兆康腾讯云+校园合伙人
可以的哦,在云通信IM的文档中有写 消息类型(文本,图片,语音,表情等自定义消息): 文本:最大 1~2k 字节(支持透传特殊字符); 图片:原图/缩略图/大图(支持格式:png/gif/jpeg/jpg/webp); 语音:异步语音消息(语音支持暂无上限); 表情等自定义消息...... 展开详请

Ubuntu搭建的WordPress如何修改php.ini?

滑稽园扛把子

Swoole · PHP开发工程师 (已认证)

As a PHP Developer
推荐
php新手很多不知道怎么查配置文件在哪,这里提供一个很简单的方法 使用 php -i 命令可以打印php的详细信息,可以把这堆东西输出一下 php -i > outputphp.txt,结合 grep 查找命令 php -i| grep php.ini 打印结果如下 Config...... 展开详请

所属标签

扫码关注云+社区