手机
当前位置:查字典教程网 >编程开发 >C语言 >如何判断一个整数的二进制中有多少个1
如何判断一个整数的二进制中有多少个1
摘要:复制代码代码如下://判断一个整数的二进制位中有多少个1voidtotalOne(intx){intcount=0;while(x){x=x...

复制代码 代码如下:

// 判断一个整数的二进制位中有多少个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】相关文章:

如何在C语言的宏中使用类型关键字

如何使用VC库函数中的快速排序函数

构造函数不能声明为虚函数的原因及分析

判断一个数是不是素数的方法

如何判断一个数是否为2的幂次方?若是,并判断出来是多少次方?

关于C语言中参数的传值问题

如何给随机数加密

c语言中单引号和双引号的区别(顺利解决从字符串中提取IP地址的困惑)

浅析如何在c语言中调用Linux脚本

c++ 虚函数与纯虚函数的区别(深入分析)

精品推荐
分类导航