【位操作笔记】计算奇偶性 使用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

相关文章

Maven pom.xml文件中build,plugin标签的使用小结

《Mavenpom.xml文件中build,plugin标签的使用小结》本文主要介绍了Mavenpom.xml文件中build,plugin标签的使用小结,文中通过示例代码介绍的非常详细,对大家的学... 目录<build> 标签Plugins插件<build> 标签<build> 标签是 pom.XML

JAVA SE包装类和泛型详细介绍及说明方法

《JAVASE包装类和泛型详细介绍及说明方法》:本文主要介绍JAVASE包装类和泛型的相关资料,包括基本数据类型与包装类的对应关系,以及装箱和拆箱的概念,并重点讲解了自动装箱和自动拆箱的机制,文... 目录1. 包装类1.1 基本数据类型和对应的包装类1.2 装箱和拆箱1.3 自动装箱和自动拆箱2. 泛型2

C# 委托中 Invoke/BeginInvoke/EndInvoke和DynamicInvoke 方法的区别和联系

《C#委托中Invoke/BeginInvoke/EndInvoke和DynamicInvoke方法的区别和联系》在C#中,委托(Delegate)提供了多种调用方式,包括Invoke、Begi... 目录前言一、 Invoke方法1. 定义2. 特点3. 示例代码二、 BeginInvoke 和 EndI

JAVA虚拟机中 -D, -X, -XX ,-server参数使用

《JAVA虚拟机中-D,-X,-XX,-server参数使用》本文主要介绍了JAVA虚拟机中-D,-X,-XX,-server参数使用,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有... 目录一、-D参数二、-X参数三、-XX参数总结:在Java开发过程中,对Java虚拟机(JVM)的启动参数进

Java中使用注解校验手机号格式的详细指南

《Java中使用注解校验手机号格式的详细指南》在现代的Web应用开发中,数据校验是一个非常重要的环节,本文将详细介绍如何在Java中使用注解对手机号格式进行校验,感兴趣的小伙伴可以了解下... 目录1. 引言2. 数据校验的重要性3. Java中的数据校验框架4. 使用注解校验手机号格式4.1 @NotBl

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

Python中__new__()方法适应及注意事项详解

《Python中__new__()方法适应及注意事项详解》:本文主要介绍Python中__new__()方法适应及注意事项的相关资料,new()方法是Python中的一个特殊构造方法,用于在创建对... 目录前言基本用法返回值单例模式自定义对象创建注意事项总结前言new() 方法在 python 中是一个

Linux系统之authconfig命令的使用解读

《Linux系统之authconfig命令的使用解读》authconfig是一个用于配置Linux系统身份验证和账户管理设置的命令行工具,主要用于RedHat系列的Linux发行版,它提供了一系列选项... 目录linux authconfig命令的使用基本语法常用选项示例总结Linux authconfi

Windows server服务器使用blat命令行发送邮件

《Windowsserver服务器使用blat命令行发送邮件》在linux平台的命令行下可以使用mail命令来发送邮件,windows平台没有内置的命令,但可以使用开源的blat,其官方主页为ht... 目录下载blatBAT命令行示例备注总结在linux平台的命令行下可以使用mail命令来发送邮件,Win

Python依赖库的几种离线安装方法总结

《Python依赖库的几种离线安装方法总结》:本文主要介绍如何在Python中使用pip工具进行依赖库的安装和管理,包括如何导出和导入依赖包列表、如何下载和安装单个或多个库包及其依赖,以及如何指定... 目录前言一、如何copy一个python环境二、如何下载一个包及其依赖并安装三、如何导出requirem