如何判断一个整数的二进制中有多少个1
2019/7/10 23:26:14
本文主要是介绍如何判断一个整数的二进制中有多少个1,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
复制代码 代码如下:
// 判断一个整数的二进制位中有多少个1
void totalOne(int x)
{
int count = 0;
while(x)
{
x = x & ( x - 1 );
count++;
}
printf("count = %d/n", count);
}
循环: x = x & ( x - 1 ); count++; 直到x为0为止。该方法的时间复杂度是O(m)
在此,不妨把x的二进制位表示为
x=an-1an-2...a0。
按从低位到高位的顺序,不失一般性,假设x的第i位为第一个为1的二进制位,即:ai=1。此时有:
x =an-1an-2...ai+1100...0 <1>
(x-1) =an-1an-2...ai+1011...1 <2>
很明显,从式1和式2可以得出,在第一次 x & (x-1) 后:
x=an-1an-2...ai+1000...0
之后重复同样操作,直到x的二进制位中没有1为止
从上面可以看出,每执行过一次 x & (x-1) 后,都会将x的二进制位中为1的最低位的值变为0,并记数加1。
目前而言,一个整数最大64bit,所有三种方法执行起来都可以认为是0(1)。
这篇关于如何判断一个整数的二进制中有多少个1的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain
- 2024-06-19EntBot.ai: AI Website Chatbot for Product Guides and Development Doc
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板