【位操作笔记】计算奇偶性 使用64位乘法和模除的方法

2024-06-22 04:18

本文主要是介绍【位操作笔记】计算奇偶性 使用64位乘法和模除的方法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

计算奇偶性(Compute parity) 使用64位乘法和模除的方法

计算奇偶性(Compute parity)指的是,计算一个数所包含1的个数是奇数还是偶数,例如一个8位数0x5b = 0b‭0101 1011‬,其中1的个数为5,是奇数;一个8位数0xa3 = 0b‭‭1010 0011‬,其中1的个数为4,是偶数。该算法可以用于奇偶校验位的计算与验证。

算法说明

使用64位乘法和模除,只需要4次操作就能完成对单个字节的计算。实际就是先通过64位的乘法和模除计算出这个数里bit位置1的个数,然后判断个数是奇数还是偶数。

如果设置了奇数位数,返回true,否则返回false。

实现代码

bool computing_parity(unsigned char val)
{return (((val * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF) & 1;
}

算法计算过程

算法分为4个部分

用abcd efgh表示一个8bit数的8个bit位。

一共只需要4次操作。

  1. val * 0x0101010101010101ULL

将数值乘以0x0101010101010101,相当于将8bit的数在64bit中填满
1

  1. (val * 0x0101010101010101ULL) & 0x8040201008040201ULL

再乘以0x8040201008040201
2

  1. ((val * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF

上一步得到的数值再取模运算0x1FF,就是511 = 29 - 1 ,相当于将每9bit的数相加在一起。
3

  1. (((val * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF) & 1

上一步得到了val这个数里bit位置1的总数,然后& 1得到数的奇偶性,完成计算。

例如一个数为0x68,二进制为0b0110 1000

  1. 0b01101000 * 0x0101010101010101ULL
    4

  2. 0x6868686868686868‬ & 0x8040201008040201ULL

第一步得到数值0x6868686868686868‬, 再乘以0x8040201008040201。
5

  1. 0x40200008000000‬ % 0x1FF

上一步得到的数值‭0x40200008000000‬再取模运算0x1FF。
6

4.0x3 & 1

上一步得到了这个数里bit位置1的总数为3,然后& 1得到的值为1,表示奇偶性为奇数。

完成奇偶性计算。


[参考资料]

Bit Twiddling Hacks By Sean Eron Anderson

[Hacker’s Delight] 作者: Henry S. Warren Jr.


本文链接:https://blog.csdn.net/u012028275/article/details/112504023

这篇关于【位操作笔记】计算奇偶性 使用64位乘法和模除的方法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1083265

相关文章

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

使用SecondaryNameNode恢复NameNode的数据

1)需求: NameNode进程挂了并且存储的数据也丢失了,如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2)故障模拟 (1)kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 (2)删除NameNode存储的数据(/opt/module/hadoop-3.1.4/data/tmp/dfs/na

Hadoop数据压缩使用介绍

一、压缩原则 (1)运算密集型的Job,少用压缩 (2)IO密集型的Job,多用压缩 二、压缩算法比较 三、压缩位置选择 四、压缩参数配置 1)为了支持多种压缩/解压缩算法,Hadoop引入了编码/解码器 2)要在Hadoop中启用压缩,可以配置如下参数

Makefile简明使用教程

文章目录 规则makefile文件的基本语法:加在命令前的特殊符号:.PHONY伪目标: Makefilev1 直观写法v2 加上中间过程v3 伪目标v4 变量 make 选项-f-n-C Make 是一种流行的构建工具,常用于将源代码转换成可执行文件或者其他形式的输出文件(如库文件、文档等)。Make 可以自动化地执行编译、链接等一系列操作。 规则 makefile文件

使用opencv优化图片(画面变清晰)

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化,使其看起来更清晰,同时保持尺寸不变,通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多,主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器:相机传

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据,将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

浅谈主机加固,六种有效的主机加固方法

在数字化时代,数据的价值不言而喻,但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露,企业的数据安全面临着前所未有的挑战。为了应对这些挑战,一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案,采用先进的安全容器中间件技术,构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限,即使在管理员权限被恶意利用的情况下,也能确保服务器的安全稳定运行。 普适主机加固措施:

webm怎么转换成mp4?这几种方法超多人在用!

webm怎么转换成mp4?WebM作为一种新兴的视频编码格式,近年来逐渐进入大众视野,其背后承载着诸多优势,但同时也伴随着不容忽视的局限性,首要挑战在于其兼容性边界,尽管WebM已广泛适应于众多网站与软件平台,但在特定应用环境或老旧设备上,其兼容难题依旧凸显,为用户体验带来不便,再者,WebM格式的非普适性也体现在编辑流程上,由于它并非行业内的通用标准,编辑过程中可能会遭遇格式不兼容的障碍,导致操