首页
技术博客
PHP教程
数据库技术
前端开发
HTML5
Nginx
php论坛
新用户注册
|
会员登录
PHP教程
技术博客
编程问答
PNG素材
编程语言
前端技术
Android
PHP教程
HTML5教程
数据库
Linux技术
Nginx技术
PHP安全
WebSerer
职场攻略
JavaScript
开放平台
业界资讯
大话程序猿
登录
极速注册
取消
热门标签 | HotTags
post
php7
copy
testing
python3
client
include
metadata
javascript
string
nodejs
regex
fetch
search
version
text
datetime
future
callback
tags
runtime
buffer
jar
cSharp
php5
web
triggers
utf-8
httpclient
usb
bit
uml
cPlusPlus
scala
io
cookie
jsp
loops
blob
eval
stream
bash
dll
chat
hook
heatmap
audio
dagger
cmd
default
command
emoji
数组
timezone
hash
dockerfile
ip
get
solr
byte
flutter
plugins
go
netty
config
input
sum
bitmap
schema
const
replace
hashcode
php
object
request
iostream
yaml
import
tree
当前位置:
开发笔记
>
编程语言
> 正文
判断32位整数二进制中1的个数的算法
作者:那时_心不在_476 | 来源:互联网 | 2023-09-14 12:50
再转 http:blog.chinaunix.netuid-20480343-id-1941577.html今天在CU上看到了关于“判断32位整数二进制中1的个数的算法”的问题。因
再转 http://blog.chinaunix.net/uid-20480343-id-1941577.html
今天在CU上看到了关于 “判断32位整数二进制中1的个数的算法” 的问题。因为马上就要下班,没有时间再研究了。只好先把论坛中帖子的地址拷贝下来了。学习ing....
http://dev.bibts.com/32-1-t936968.htm
http://www.chinaunix.net/jh/23/795048.html
在下面的英文网址中,对这个问题有详细的介绍:
http://www.everything2.com/index.pl?node=counting%201%20bits
http://www.everything2.com/index.pl?node=counting%201%20bits%20SPOILER
http://www.everything2.com/index.pl?node_id=1181258
刚开始看到这个问题的时候,我就傻乎乎的开始写代码:
unsigned int FindOneInNumber_00(unsigned int x)
{
unsigned int i,j=1;
unsigned int count=0;
for(i=0;i<32;i++)
{
if((x & j) != 0) count++;
j = j<<2;
}
return count;
}
下面是我写的
很明显我的这段代码写的是非常糟糕的。每次传过来一个数字,我总是要进行32次扫描。就这一点就可以说我的代码是典型的垃圾代码,那么别人是不是有简洁一点的代码呢。在上面的三个英文网址中找到了一些东西。
unsigned int FindOneInNumber_01(unsigned int x)
{
unsigned int n;
for(n=0; x; x >>= 1)
if (x & 1) n++;
return n;
}
在英文文档中,原作者给出的第一种方法。看到这样的代码,俺只能说自己太笨,代码写起来太傻。不就是查查一个数字中 1 的个数吗?自己为啥非得要把所有的 位 都扫描呢? 这是一个值得想想的问题。 原作者给出的代码已经是很不错了,不过,在下面接着他又给出了第二种解法,这第二种解法,更是简洁 优雅 。
unsigned int FindOneInNumber_02(unsigned int x)
{
unsigned int n;
for(n=0; x; n++)
x &= x-1;
return n;
}
原作者给出的第二种方法明显的要优于第一种方法。两者的程序中,循环体执行完后,n表示 1 个个数。x的值变为 0 。两者都达到了目的,循环次数也是一样的。但是二者的区别就在于 第二种方法不用 执行条件判断跳转。当数据量的比较大的时候,二者的差距还是蛮大的。
原文作者又给出第三种方法来解决这个问题:
unsigned FindOneInNumber_03(unsigned int x)
{
const unsigned MASK1 = 0x55555555;
const unsigned MASK2 = 0x33333333;
const unsigned MASK4 = 0x0f0f0f0f;
const unsigned MASK8 = 0x00ff00ff;
const unsigned MASK16 = 0x0000ffff;
x = (x&MASK1 ) + (x>>1 &MASK1 );
x = (x&MASK2 ) + (x>>2 &MASK2 );
x = (x&MASK4 ) + (x>>4 &MASK4 );
x = (x&MASK8 ) + (x>>8 &MASK8 );
x = (x&MASK16) + (x>>16&MASK16);
return x;
}
原文作者的一个朋友又给出一种方法,【查表法】,不过,这样要浪费一定的主存。这种方法也是一个很不错的方法,不过,在单片机下开发的时候,就是个问题的了。象我们公司在单片机上开发游戏,所有的能够给 图片、声音、程序的所有ROM空间仅仅 8MB,采用这种方法就是很不明智的一种选择了。
unsigned numbits_lookup_table[256] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2,
3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3,
3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3,
4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4,
3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5,
6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4,
4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,
6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,
3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3,
4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6,
6, 7, 6, 7, 7, 8
};
unsigned FindOneInNumber_04(unsigned int x)
{
unsigned n;
n = numbits_lookup_table[x & 0xff];
n += numbits_lookup_table[x>>8 & 0xff];
n += numbits_lookup_table[x>>16 & 0xff];
n += numbits_lookup_table[x>>24 & 0xff];
return n;
}
【本程序在Dev C++ 4.9.9.2 下编译通过】
算法
http
unix
html
编程
php
bit
int
const
写下你的评论吧 !
吐个槽吧,看都看了
会员登录
|
用户注册
推荐阅读
string
如何用JNI技术调用Java接口以及提高Java性能的详解
本文介绍了如何使用JNI技术调用Java接口,并详细解析了如何通过JNI技术提高Java的性能。同时还讨论了JNI调用Java的private方法、Java开发中使用JNI技术的情况以及使用Java的JNI技术调用C++时的运行效率问题。文章还介绍了JNIEnv类型的使用方法,包括创建Java对象、调用Java对象的方法、获取Java对象的属性等操作。 ...
[详细]
蜡笔小新 2023-12-11 14:53:02
string
lua语言闭包、模式匹配、日期、编译、模块的特性及应用
本文介绍了lua语言中闭包的特性及其在模式匹配、日期处理、编译和模块化等方面的应用。lua中的闭包是严格遵循词法定界的第一类值,函数可以作为变量自由传递,也可以作为参数传递给其他函数。这些特性使得lua语言具有极大的灵活性,为程序开发带来了便利。 ...
[详细]
蜡笔小新 2023-12-14 18:18:21
string
Android中高级面试必知必会,积累总结
本文介绍了Android中高级面试的必知必会内容,并总结了相关经验。文章指出,如今的Android市场对开发人员的要求更高,需要更专业的人才。同时,文章还给出了针对Android岗位的职责和要求,并提供了简历突出的建议。 ...
[详细]
蜡笔小新 2023-12-14 14:53:02
web
CSS3选择器的使用方法详解,提高Web开发效率和精准度
本文详细介绍了CSS3新增的选择器方法,包括属性选择器的使用。通过CSS3选择器,可以提高Web开发的效率和精准度,使得查找元素更加方便和快捷。同时,本文还对属性选择器的各种用法进行了详细解释,并给出了相应的代码示例。通过学习本文,读者可以更好地掌握CSS3选择器的使用方法,提升自己的Web开发能力。 ...
[详细]
蜡笔小新 2023-12-14 14:37:52
usb
[译]技术公司十年经验的职场生涯回顾
本文是一位在技术公司工作十年的职场人士对自己职业生涯的总结回顾。她的职业规划与众不同,令人深思又有趣。其中涉及到的内容有机器学习、创新创业以及引用了女性主义者在TED演讲中的部分讲义。文章表达了对职业生涯的愿望和希望,认为人类有能力不断改善自己。 ...
[详细]
蜡笔小新 2023-12-14 11:31:05
copy
clone的fork与pthread_create创建线程有何不同
本文讨论了clone的fork与pthread_create创建线程的不同之处。进程是一个指令执行流及其执行环境,其执行环境是一个系统资源的集合。在调用系统调用fork创建一个进程时,子进程只是完全复制父进程的资源,这样得到的子进程独立于父进程,具有良好的并发性。但是二者之间的通讯需要通过专门的通讯机制,另外通过fork创建子进程系统开销很大。因此,在某些情况下,使用clone或pthread_create创建线程可能更加高效。 ...
[详细]
蜡笔小新 2023-12-12 20:00:06
string
手机移动端HTML5和JavaScript如何实现视频上传和压缩视频质量?
本文讨论了在手机移动端如何使用HTML5和JavaScript实现视频上传并压缩视频质量,或者降低手机摄像头拍摄质量的问题。作者指出HTML5和JavaScript无法直接压缩视频,只能通过将视频传送到服务器端由后端进行压缩。对于控制相机拍摄质量,只有使用JAVA编写Android客户端才能实现压缩。此外,作者还解释了在交作业时使用zip格式压缩包导致CSS文件和图片音乐丢失的原因,并提供了解决方法。最后,作者还介绍了一个用于处理图片的类,可以实现图片剪裁处理和生成缩略图的功能。 ...
[详细]
蜡笔小新 2023-12-12 15:58:44
include
深入浅出Linux设备驱动编程的重要性与方法
本文介绍了深入浅出Linux设备驱动编程的重要性,以及两种加载和删除Linux内核模块的方法。通过一个内核模块的例子,展示了模块的编译和加载过程,并讨论了模块对内核大小的控制。深入理解Linux设备驱动编程对于开发者来说非常重要。 ...
[详细]
蜡笔小新 2023-12-12 15:28:09
triggers
引擎之旅 Chapter.2 线程库
预备知识可参考我整理的博客Windows编程之线程:https:www.cnblogs.comZhuSenlinp16662075.htmlWindows编程之线程同步:https ...
[详细]
蜡笔小新 2023-12-12 14:06:39
version
PHP常量的定义和使用方法
本文介绍了PHP常量的定义和使用方法,包括常量的命名规则、大小写敏感性、全局范围和标量数据的限制。同时还提到了应尽量避免定义resource常量,并给出了使用define()函数定义常量的示例。 ...
[详细]
蜡笔小新 2023-12-11 10:19:40
buffer
C#生成随机数的三种方法及其问题分析
本文介绍了C#中生成随机数的三种方法,并分析了其中存在的问题。首先介绍了使用Random类生成随机数的默认方法,但在高并发情况下可能会出现重复的情况。接着通过循环生成了一系列随机数,进一步突显了这个问题。文章指出,随机数生成在任何编程语言中都是必备的功能,但Random类生成的随机数并不可靠。最后,提出了需要寻找其他可靠的随机数生成方法的建议。 ...
[详细]
蜡笔小新 2023-12-14 14:15:30
include
P1651 塔 (动态规划) 的最大高度计算方法
本文介绍了P1651题目的描述和要求,以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术,将问题转化为求解差值的问题,并定义了相应的状态。最终得出了计算最大高度的解法。 ...
[详细]
蜡笔小新 2023-12-13 19:52:19
web
如何在Windows环境下配置php+apache环境
本文介绍了在Windows环境下如何配置php+apache环境,包括下载php7和apache2.4、安装vc2015运行时环境、启动php7和apache2.4等步骤。希望对需要搭建php7环境的读者有一定的参考价值。摘要长度为169字。 ...
[详细]
蜡笔小新 2023-12-13 10:39:24
include
3.223.28周学习总结中的贪心作业收获及困惑
本文是对3.223.28周学习总结中的贪心作业进行总结,作者在解题过程中参考了他人的代码,但前提是要先理解题目并有解题思路。作者分享了自己在贪心作业中的收获,同时提到了一道让他困惑的题目,即input details部分引发的疑惑。 ...
[详细]
蜡笔小新 2023-12-13 03:42:02
text
浏览器中的异常检测算法及其在深度学习中的应用
本文介绍了在浏览器中进行异常检测的算法,包括统计学方法和机器学习方法,并探讨了异常检测在深度学习中的应用。异常检测在金融领域的信用卡欺诈、企业安全领域的非法入侵、IT运维中的设备维护时间点预测等方面具有广泛的应用。通过使用TensorFlow.js进行异常检测,可以实现对单变量和多变量异常的检测。统计学方法通过估计数据的分布概率来计算数据点的异常概率,而机器学习方法则通过训练数据来建立异常检测模型。 ...
[详细]
蜡笔小新 2023-12-12 16:22:39
那时_心不在_476
这个家伙很懒,什么也没留下!
Tags | 热门标签
post
php7
copy
testing
python3
client
include
metadata
javascript
string
nodejs
regex
fetch
search
version
text
datetime
future
callback
tags
runtime
buffer
jar
cSharp
php5
web
triggers
utf-8
httpclient
usb
RankList | 热门文章
1
matlab基础 conv 多项式 乘法
2
极客星球|Clickhouse在数据智能公司的应用与实践
3
Android如何以编程方式将证书存储在密钥库中?
4
AJAX在线音乐网站(1)需求和功能结构
5
UI设计来说必不可少的技能是:图标绘制
6
浮点数在Python中可以具有的值范围是多少?
7
云计算基础技术及解决方案介绍 云计算基础及应用
8
蘸字意思 在新华字典的读音解释笔画常用组词起名
9
《经杀子谷》翻译 原文赏析诗人唐陶翰
10
ML回归问题的评估(MSE、RMSE、MAE、R Square)
11
已解决 | Apache(LAMP)网站如何升级配置https
12
struts2 模型驱动封装动态参数
13
oracle常用数值函数,转换函数,字符串函数
14
《奉和圣制过温汤》翻译 原文赏析诗人唐杨思玄
15
中国云原生AI开发平台白皮书 附下载
PHP1.CN | 中国最专业的PHP中文社区 |
DevBox开发工具箱
|
json解析格式化
|
PHP资讯
|
PHP教程
|
数据库技术
|
服务器技术
|
前端开发技术
|
PHP框架
|
开发工具
|
在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved |
京公网安备 11010802041100号
|
京ICP备19059560号-4
| PHP1.CN 第一PHP社区 版权所有