汉明权重(Hamming Weight)(统计数据中1的个数)VP-SWAR算法

汉明权重(Hamming Weight)(统计数据中1的个数)VP-SWAR算法

定义

汉明重量是一串符号中非零符号的个数。它等于同样长度的全零符号串的汉明距离(在信息论中,两个等长字符串之间的汉明距离等于两个字符串对应位置的不同字符的个数)。
汉明重量在常见的数据位符号串中,它是1的个数。

算法思想

基于分治的算法,将n位二进制进行分组,通过一系列位移和位运算操作,可以在常数时间内计算多个字节的汉明重量,并且不需要使用额外的内存。

简化示例

假设一个8bit的2进制串 x=abcd,efgh其中a-b 属于{0,1}
求解的输出是 ans = a+b+c+d+e+f+g+h

step1. 2bits m1= 0101 0101

x&m1 = 0b0d 0f0h
(x>>1)&m1 = 0a0c 0e0g
求和得到[a+b]_2[c+d]_2 [e+f]_2[g+h]_2,这里[x]_2表示2位二进制中1的个数

step2. 4bits m2 = 0011 0011

x&m2 = 00[c+d]_2 00[g+h]_2
(x>>2)&m2 = 00[a+b]_2 00[e+f]_2
求和得到[a+b+c+d]_4 [e+f+g+h]_4

step3. 8bits m4 = 0000 1111

x&m4 = 0000 [e+f+g+h]_4
(x>>4)&m4 = 0000 [a+b+c+d]_4
求和得到 [a+b+c+d+e+f+g+h]_8
对应的十进制值就是最终的答案

算法实现 variable-precision SWAR算法

const uint64_t m1  = 0x5555555555555555; //binary: 0101...
const uint64_t m2  = 0x3333333333333333; //binary: 00110011..
const uint64_t m4  = 0x0f0f0f0f0f0f0f0f; //binary:  4 zeros,  4 ones ...
const uint64_t m8  = 0x00ff00ff00ff00ff; //binary:  8 zeros,  8 ones ...
const uint64_t m16 = 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...
const uint64_t m32 = 0x00000000ffffffff; //binary: 32 zeros, 32 ones
const uint64_t h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...//This is a naive implementation, shown for comparison,
//and to help in understanding the better functions.
//This algorithm uses 24 arithmetic operations (shift, add, and).
// 朴素算法
int popcount64a(uint64_t x)
{x = (x & m1 ) + ((x >>  1) & m1 ); //put count of each  2 bits into those  2 bits x = (x & m2 ) + ((x >>  2) & m2 ); //put count of each  4 bits into those  4 bits x = (x & m4 ) + ((x >>  4) & m4 ); //put count of each  8 bits into those  8 bits x = (x & m8 ) + ((x >>  8) & m8 ); //put count of each 16 bits into those 16 bits x = (x & m16) + ((x >> 16) & m16); //put count of each 32 bits into those 32 bits x = (x & m32) + ((x >> 32) & m32); //put count of each 64 bits into those 64 bits return x;
}

详细步骤

详细步骤
优化算法

//This is better when most bits in x are 0
//This algorithm works the same for all data sizes.
//This algorithm uses 3 arithmetic operations and 1 comparison/branch per "1" bit in x.
// 适用于0比较多的数
// 数字 n中最低位的 1 总是对应 n - 1 中的 0
// 将 n 和 n - 1 进行与运算总是能把 n 中最低位的 1 变成 0,并保持其他位不变
int popcount64d(uint64_t x)
{int count;for (count=0; x; count++)x &= x - 1;return count;
}// 常用写法
int hammingWeight(uint32_t n) {int count = 0;while( n ){count ++;n &= n-1;}return count;
}// 查表法 用空间换时间 从而得到O(1)的最优算法
// 以4bit的串为例,可以构造一个数组int counts[16]={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4}.
// 对于4bit的x, x的hamming weight为:counts[x].
static unsigned char wordbits[65536] = { bitcounts of ints between 0 and 65535 };
static int popcount(uint32 i)
{return (wordbits[i&0xFFFF] + wordbits[i>>16]);
}

参考

Hamming weight WIKI
汉明权重(hamming weight) ----- 计算数据位中1的个数

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1486290.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

无线麦克风推荐哪些品牌,领夹麦克风哪个品牌好,无线麦克风推荐

​作为消费类电子产品,麦克风随着市场需求和技术进步,每年都有新产品系列涌现,特别是领夹麦克风,近年来经历了显著的市场变革和技术突破。从早期的新闻采访、节目录制和影视后期录音中常用的无线小蜜蜂话筒,到如今在网…

【保姆级讲解C语言中的运算符的优先级!】

🎥博主:程序员不想YY啊 💫CSDN优质创作者,CSDN实力新星,CSDN博客专家 🤗点赞🎈收藏⭐再看💫养成习惯 ✨希望本文对您有所裨益,如有不足之处,欢迎在评论区提出…

创建最佳实践创建 XML 站点地图--SEO

您是否正在努力让您的网站被搜索引擎索引?您想提高您网站的搜索引擎知名度吗?如果是,您可能会错过 XML 站点地图的重要性。XML 站点地图在改善您网站的 SEO 方面发挥着至关重要的作用。‍ XML 站点地图是您网站结构的蓝图,可帮助…

RH436 Managing LVM Shared Volume Groups

RH436 Managing LVM Shared Volume Groups 1. 启动lab环境2. 准备lvm卷组3. 创建逻辑卷4. 配置集群资源启动顺序5. 确认各节点lvs正常6. LVM-HA和LVM-Share使用场景 1. 启动lab环境 [studentworkstation ~]$ lab start lvm-shared2. 准备lvm卷组 所有节点安装依赖包 yum ins…

react中组件间的通信

一、父传子 1.代码展示 import React, { useState } from react;function SonPage(props){ // 子组件const {msg} propsreturn (<div>我是子组件 {msg}</div>) }function App() { // 父组件const [msgText,setMsgText] useState(父传子)return (<div classN…

掌握VR全景技术,需要具备哪些条件?

VR全景技术自从进入市场以来&#xff0c;就在各个行业领域尝试落地运用&#xff0c;包括但不限于广告宣传、学校教育、医疗、工业、农业等领域。随着5G 技术的不断普及&#xff0c;VR全景技术也逐渐被应用到日常生活中的各个方面&#xff0c;从地产中介到车企销售&#xff0c;从…

Electron的入门介绍与使用(1)共30节

Electron是一个使用 JavaScript、HTML 和 CSS 构建桌面应用程序的框架。 嵌入 Chromium 和 Node.js 到 二进制的 Electron 允许您保持一个 JavaScript 代码代码库并创建 在Windows上运行的跨平台应用 macOS和Linux——不需要本地开发 经验。 入门指南​ Electron 是网页应用 …

【北京迅为】《i.MX8MM嵌入式Linux开发指南》-第三篇 嵌入式Linux驱动开发篇-第四十章 Linux用户层和内核层

i.MX8MM处理器采用了先进的14LPCFinFET工艺&#xff0c;提供更快的速度和更高的电源效率;四核Cortex-A53&#xff0c;单核Cortex-M4&#xff0c;多达五个内核 &#xff0c;主频高达1.8GHz&#xff0c;2G DDR4内存、8G EMMC存储。千兆工业级以太网、MIPI-DSI、USB HOST、WIFI/BT…

力扣第二十五题——K个一组反转链表

内容介绍 给你链表的头节点 head &#xff0c;每 k 个节点一组进行翻转&#xff0c;请你返回修改后的链表。 k 是一个正整数&#xff0c;它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍&#xff0c;那么请将最后剩余的节点保持原有顺序。 你不能只是单纯的改变节点内…

Vscode离线下载对应版本的ms-python.vsix

一、查看vscode的版本号和发行时间 vscode界面中Help-About查看版本号和发行时间&#xff0c;ms-python的发行时间需要和这个时间相近&#xff1a; 二、在github仓库中查看ms-python有什么版本&#xff0c;以及发行时间 github仓库路径 https://github.com/microsoft/vsco…

力扣题库合集(2):动态规划(1)

本文将持续更新~~ hello hello~ &#xff0c;这里是绝命Coding——老白~&#x1f496;&#x1f496; &#xff0c;欢迎大家点赞&#x1f973;&#x1f973;关注&#x1f4a5;&#x1f4a5;收藏&#x1f339;&#x1f339;&#x1f339; &#x1f4a5;个人主页&#xff1a;绝命C…

qt中charts图表的使用方法

折线图 #include "widget.h" #include "ui_widget.h" #include <QtCharts/QChart> #include <QtCharts/QChartView> #include <QtCharts/QLineSeries> #include<QVBoxLayout>Widget::Widget(QWidget *parent): QWidget(parent), …

Python解释器:CPython 解释器

一、什么是python解释器 Python解释器是一种用于执行Python代码的程序。 它将Python源代码转换为机器语言或字节码&#xff0c;从而使计算机能够执行。 1.1 Python解释器分类 1、CPython CPython 是 Python 的主要实现&#xff0c;由 C 语言编写。大多数用户在日常开发中使…

“机器说人话”-AI 时代的物联网

万物互联的物联网愿景已经提了许多年了&#xff0c;但是实际效果并不理想&#xff0c;除了某些厂商自己的产品生态中的产品实现了互联之外&#xff0c;就连手机控制空调&#xff0c;电视机和调光灯都没有实现。感觉小米做的好一点&#xff0c;而华为的鸿蒙的全场景&#xff0c;…

MMCV 核心组件分析(一):整体概述

概述 MMCV 是计算机视觉研究的基础库&#xff0c;并提供以下功能。

Go基础编程 - 12 -流程控制

流程控制 1. 条件语句1.1. if...else 语句1.2. switch 语句1.3. select 语句1.3.1. select 语句的通信表达式1.3.2. select 的基特性1.3.3. select 的实现原理1.3.4. 经典用法1.3.4.1 超时控制1.3.4.2 多任务并发控制1.3.4.3 监听多通道消息1.3.4.4 default 实现非堵塞读写 2. …

海康威视综合安防管理平台 detection 前台RCE漏洞复现

0x01 产品简介 海康威视综合安防管理平台是一套“集成化”、“智能化”的平台,通过接入视频监控、一卡通、停车场、报警检测等系统的设备。海康威视集成化综合管理软件平台,可以对接入的视频监控点集中管理,实现统一部署、统一配置、统一管理和统一调度。 0x02 漏洞概述 海康…

k8s中部署nacos

1 部署nfs # 在k8s的主节点上执行 mkdir -p /appdata/download cd /appdata/download git clone https://github.com/nacos-group/nacos-k8s.git 将nacos部署到middleware的命名空间中 kubectl create namespace middleware cd /appdata/download/nacos-k8s # 创建角色 kub…

JavaScript中==和===的区别

&#x1f9d1;‍&#x1f4bb; 写在开头 点赞 收藏 学会&#x1f923;&#x1f923;&#x1f923; 前言 JavaScript 中的相等运算符无疑是新手开发者最容易混淆的知识点之一。 和这两个运算符的细微差别往往会在代码中造成一些令人困惑的行为 在本文中,我们将深入探讨这两个…

Google Chrome 浏览器在链接上点右键的快捷键

如今&#xff0c;越来越多的软件都懒得设个快捷键&#xff0c;就算设置了连个下划线也懒得加了。 谷歌浏览器右键 > 链接另存为... 和 复制链接地址 的快捷键 (如图)