C#,二进制数的非0位数统计(Bits Count)的算法与源代码

计算一个十进制数的二进制表示有多少位1?

1 遍历法(递归或非递归)

使用循环按位统计1的个数。

2 哈希查表法

利用一个数组或哈希生成一张表,存储不同二进制编码对应的值为1的二进制位数,那么在使用时,只需要去进行查询,即可在O(1)的时间复杂度内得到结果。
但是,此算法有个弊端,由于算法是采用空间换取时间的方法,当一个二进制数的位长超过一定限度时,对应的表也就会占据很大的空间,也就是说节约时间越多,花费的存储越多。另外此方法还会收到CPU缓存的限制,如果表太大,表在缓存的上下文切换也就越多,可能会导致性能没有想象中那么高。
所以,为了解决此问题,一般情况下,采用适当的二进制位长度来建表,比如8位、16位,这样情况下,可以对上述问题得到一个平衡,不仅可以享受到优越的性能,而且时间开销也没有遍历法高。

3 Variable-precision SWAR算法

在数学上,我们一般称上述问题为“计算汉明重量”,而当前一直效率最好的通用算法为variable-precision SWAR算法,该算法不仅在常数时间计算多个字节的汉明重量,而且不需要使用任何额外的内存。
 

4 源程序

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
	public static partial class Algorithm_Gallery
	{
		public static int Count_Setbits(int n)
		{
			// initialize the result
			int bitCount = 0;
			for (int i = 1; i <= n; i++)
			{
				bitCount += Count_Setbits_Utility(i);
			}
			return bitCount;
		}

		private static int Count_Setbits_Utility(int x)
		{
			if (x <= 0)
			{
				return 0;
			}
			return (x % 2 == 0 ? 0 : 1) + Count_Setbits_Utility(x / 2);
		}

		public static int Count_Setbits_Second(int n)
		{
			int i = 0;
			int ans = 0;

			while ((1 << i) <= n)
			{
				bool k = false;

				int change = 1 << i;

				for (int j = 0; j <= n; j++)
				{
					ans += (k) ? 1 : 0;
					if (change == 1)
					{
						k = !k;
						change = 1 << i;
					}
					else
					{
						change--;
					}
				}
				i++;
			}
			return ans;
		}

		private static int Leftmost_Bit(int n)
		{
			int m = 0;
			while (n > 1)
			{
				n = n >> 1;
				m++;
			}
			return m;
		}

		private static int Next_Leftmost_Bit(int n, int m)
		{
			int temp = 1 << m;
			while (n < temp)
			{
				temp = temp >> 1;
				m--;
			}
			return m;
		}

		public static int Count_Setbits_Third(int n)
		{
			int m = Leftmost_Bit(n);

			return Count_Setbits_Third_Utility(n, m);
		}

		public static int Count_Setbits_Third_Utility(int n, int m)
		{
			if (n == 0)
			{
				return 0;
			}
			m = Next_Leftmost_Bit(n, m);

			if (n == ((int)1 << (m + 1)) - 1)
			{
				return (int)(m + 1) * (1 << m);
			}
			n = n - (1 << m);
			return (n + 1) + Count_Setbits_Third(n) + m * (1 << (m - 1));
		}
	}
}

POWER BY TRUFFER.CN
BY 315SOFT.COM

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

MIT-BEVFusion系列八--onnx导出2 spconv network网络导出

这里写目录标题 export-scn.py加载模型设置每层的精度属性初始化输入参数导出模型model.encoder_layers 设置初始化参数设置 indice_key 属性更改 lidar backbone 的 forward更改lidar网络内各个层的forward带参数装饰器&#xff0c;钩子函数代码使用装饰器修改forward举例 跟踪…

GPU芯片逆势扩张,NVIDIA成为2023年全球芯片的唯一赢家

市调机构Gartner发布数据指出2023年全球诸多芯片行业都在下滑&#xff0c;唯一取得增长的仅有GPU/AI芯片&#xff0c;GPU芯片的市场规模增加了一倍&#xff0c;而领头羊NVIDIA无疑成为最大的赢家。 从2022年下半年以来&#xff0c;全球芯片行业就已步入供给过剩的阶段&#xff…

HarmonyOS—状态管理概述

在前文的描述中&#xff0c;我们构建的页面多为静态界面。如果希望构建一个动态的、有交互的界面&#xff0c;就需要引入“状态”的概念。 图1 效果图 上面的示例中&#xff0c;用户与应用程序的交互触发了文本状态变更&#xff0c;状态变更引起了UI渲染&#xff0c;UI从“He…

C++中对象的构造与析构顺序

一、对象的构造顺序 对象的构造&#xff0c;先被创建的对象&#xff0c;先被构造&#xff0c;先调用其构造函数 class A { private:int _a 0; public://构造函数A(int a 0){_a a;cout << "A(int a 0)" << " " << _a << endl…

【计算机网络】网际协议——互联网中的转发和编址

编址和转发是IP协议的重要组件 就像这个图所示&#xff0c;网络层有三个主要组件&#xff1a;IP协议&#xff0c;ICMP协议&#xff0c;路由选择协议IPV4 没有选项的时候是20字节 版本&#xff08;号&#xff09;&#xff1a;4比特&#xff1a;规定了IP协议是4还是6首部长度&am…

【Redis】Redis

❤️ Author&#xff1a; 老九 ☕️ 个人博客&#xff1a;老九的CSDN博客 &#x1f64f; 个人名言&#xff1a;不可控之事 乐观面对 &#x1f60d; 系列专栏&#xff1a; 文章目录 Nosql为什么使用Nosql什么是NosqlNosql特点 Redis入门windows安装Linux安装 Nosql 为什么使用N…

盐构造发育的动力学机制

盐构造可以由以下6 种机制触发引起(图 2)[18] &#xff1a;①浮力作用&#xff1b;②差异负载作用&#xff1b;③重力扩张作 用&#xff1b;④热对流作用&#xff1b;⑤挤压作用&#xff1b;⑥伸展作用。盐体 的塑性流动和非常规变形是盐构造的主要特点,岩 盐有时在几百m 深处就…

Linux第一个小程序-进度条

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言 一、回车和换行 二、行缓冲区概念 三、倒计时 四、进度条代码 版本一&#xff1a; ​编辑 版本二&#xff1a; 总结 前言 世上有两种耀眼的光芒&#xff0c;一…

java中的枚举

枚举 枚举类型的概述 关键字&#xff1a;enum 你可以把枚举类型理解成是一个自定义的常量的序列 枚举的语法结构 定义的枚举类型文件 package com.it.xiaosi.demo01;/*** Classname : direction* Description : TODO 枚举* Author : lin_refuelqq.com*/ public enum direct…

关于VIT(Vision Transformer)的架构记录

在VIT模型设计中&#xff0c;尽可能地紧密遵循原始的Transformer模型&#xff08;Vaswani等人&#xff0c;2017年&#xff09;。这种刻意简化的设置的一个优势是&#xff0c;可扩展的NLP Transformer架构及其高效的实现几乎可以即插即用。 图&#xff1a;模型概述。我们将图像分…

Qt实用技巧:QCustomPlot做北斗GPS显示绝对位置运动轨迹和相对位置运动轨迹图的时,使图按照输入点顺序连曲线

若该文为原创文章&#xff0c;转载请注明原文出处 本文章博客地址&#xff1a;https://hpzwl.blog.csdn.net/article/details/136131310 红胖子网络科技博文大全&#xff1a;开发技术集合&#xff08;包含Qt实用技术、树莓派、三维、OpenCV、OpenGL、ffmpeg、OSG、单片机、软硬…

机器学习入门--LSTM原理与实践

LSTM模型 长短期记忆网络&#xff08;Long Short-Term Memory&#xff0c;LSTM&#xff09;是一种常用的循环神经网络&#xff08;RNN&#xff09;变体&#xff0c;特别擅长处理长序列数据和捕捉长期依赖关系。本文将介绍LSTM模型的数学原理、代码实现和实验结果&#xff0c;并…

MongoDB从入门到实战之.NET Core使用MongoDB开发ToDoList系统(3)-系统数据集合设计

前言 前几章教程我们把ToDoList系统的基本框架搭建好了&#xff0c;现在我们需要根据我们的需求把ToDoList系统所需要的系统集合&#xff08;相当于关系型数据库中的数据库表&#xff09;。接下来我们先简单概述一下这个系统主要需要实现的功能以及实现这些功能我们需要设计那些…

平时积累的FPGA知识点(10)

平时在FPGA群聊等积累的FPGA知识点&#xff0c;第10期&#xff1a; 41 ZYNQ系列芯片的PL中使用PS端送过来的时钟&#xff0c;这些时钟名字是自动生成的吗&#xff1f; 解释&#xff1a;是的。PS端设置的是ps_clk&#xff0c;用report_clocks查出来的时钟名变成了clk_fpga_0&a…

NX二次开发树列表双击快速进入编辑状态

先将这几个树列表回调注释给解开 int TreeColumn0;//定义一个全局边量记录点击的那一列NXOpen::BlockStyler::Tree::BeginLabelEditState OnBeginLabelEditCallback(NXOpen::BlockStyler::Tree *tree,NXOpen::BlockStyler::Node *node,int columID) {if(columnIDTreeColumnID)…

The method toList() is undefined for the type Stream

The method toList() is undefined for the type Stream &#xff08;JDK16&#xff09; default List<T> toList() { return (List<T>) Collections.unmodifiableList(new ArrayList<>(Arrays.asList(this.toArray()))); }

磁体发条概念

使用磁体发条&#xff08;也称为磁弹簧或磁蓄能器&#xff09;作为储能装置是一个有趣的概念&#xff0c;它利用电磁感应原理来存储和释放能量。磁体发条的基本原理是通过旋转一个强磁体&#xff0c;使其通过一个线圈的中心&#xff0c;从而在线圈中产生电流。当磁体停止旋转时…

平时积累的FPGA知识点(11)

平时在FPGA群聊等积累的FPGA知识点,第11期: 51 可以把dcp文件封装到自己ip里吗? 解释:不可以 52 fifo的异步复位要做异步复位同步释放吗? 解释:要跟写时钟同步,所以需要在ip外部做一下同步释放 53 vivado报错 Phase 6.1 Hold Fix Iter Phase 6.1.1 Update Timing …

下一代Windows系统曝光:基于GPT-4V,Agent跨应用调度,代号UFO

下一代Windows操作系统提前曝光了&#xff1f;&#xff1f; 微软首个为Windows而设的智能体&#xff08;Agent&#xff09; 亮相&#xff1a; 基于GPT-4V&#xff0c;一句话就可以在多个应用中无缝切换&#xff0c;完成复杂任务。整个过程无需人为干预&#xff0c;其执行成功…

PANTONE(R)_colorist 潘通色号查询软件

PANTONE_colorist 潘通色号查询 查找颜色一栏输入对应的色号&#xff0c;即可显示对应的图案。 下载 https://download.csdn.net/download/jintaihu/19340557