如何判断一个整数的二进制中有多少个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
复制代码 代码如下: // 判断一个整数的二进制位中有多少个1void 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...a
-
判断一个整数是否是2的N次幂实现方法
实例如下: static bool CheckPowerOfTwo(ulong num) { return num > 0 && (num & (num - 1)) == 0; } 以上这篇判断一个整数是否是2的N次幂实现方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.
-
Python实现判断一个整数是否为回文数算法示例
本文实例讲述了Python实现判断一个整数是否为回文数算法.分享给大家供大家参考,具体如下: 第一个思路是先将整数转换为字符串,再将字符串翻转并与原字符串做比较 def isPalindrome(self, x): """ :type x: int :rtype: bool """ #思路:先将整数转换为字符串,再将字符串翻转并与原字符串做比较 x = str(x) return x == x[::-1] 代码简洁 第二个思路,尝试着不用字符串,
-
Java得到一个整数的绝对值,不使用任何判断和比较语句,包括API
复制代码 代码如下: /** * Java得到一个整数的绝对值,不使用任何判断和比较语句,包括API. <br> * 1.不得使用任何API,如Math.abs()等.<br> * 2.不得使用判断语句,如if.for.while.switch.?:等.<br> * 3.不得使用比较语句,如:==. <=.>=.!=. <.>等. <br> * * @author JAVA世纪网(java2000.net, laozizhu.com)
-
PHP判断一个变量是否为整数、正整数的方法示例
在PHP中判断一个变量是否为整数 在写PHP代码的时候遇到这样一个小问题:如何判断一个变量是否为整数,于是在网上找到了两个方法来解决,在此做一个小小的记录. 方法1 <?php $num=12; //返回right //$num=12.1 返回false if(is_int($num)){ echo "right"; }else{ echo "false"; } ?> 这里用is_int()方法来判断传入的参数是否为整数形(int),而不是判断它是否为整
-
python判断一个数是否能被另一个整数整除的实例
判断一个数是否能被另一个整数整除是一个挺简单的问题,一般一个模运算就可以搞定了,懒惰的晓萌还是不想自己做,于是找到你帮他写代码,你就帮帮他吧. 输入格式 输入包括两个由空格分开的整数M 和 N(1≤M,N≤500) 输出格式 输出包括一行,如果 M 可以被 N 整除就输出YES,否则输出NO(结果大小写敏感). 样例输入 21 7 样例输出 YES str = input() nums = str.split() if int(nums[0]) % int(nums[1]) == 0: prin
-
python怎样判断一个数值(字符串)为整数
目录 如何判断一个数值(字符串)为整数 不严格检查方法 严格的检查方法 判断输入的字符串是否是整数还是小数 总结 如何判断一个数值(字符串)为整数 不严格检查方法 浮点数的自带方法is_integer() 如果确定输入的内容为浮点数,是可以直接使用float数的is_integer()函数来进行判定. 需要注意的是当数字是 1.0这样的不带小数数值的浮点数时,会被默认判定为整数 a=1.0 print(a.is_integer()) #结果为 True b=1.1 print(b.is_inte
-
js 判断一个数字是不是2的n次方幂的实例
昨天去面试时,面试官问了一道面试题,说如何判断一个数是不是2的n次方幂,我当时不知道2的n次方幂是什么(糗大发了),还好给我解释了一下.最后回家上网查查资料,整理了一下方法. 方法一 如何判断一个数是否是2的n次方幂,其简单判断方法就是这个数num直接除2,若余数为0,则num/2再除2,再判断是不是余数是不是0,是的话继续按上一步来,直到最后为num=1. 比如: 2 2%2=0 (2/2)=1 是 4 4%2=0 (4/2)%2=0 (4/2/2)=
-
JavaScript中如何判断一个值的类型
我们知道在js中有一个运算符可以帮助我们判断一个值的类型,它就是typeof运算符. console.log(typeof 123); //number console.log(typeof '123'); //string console.log(typeof true); //boolean console.log(typeof undefined); //undefined console.log(typeof null); //object console.log(typeof []);
-
用C语言判断一个二叉树是否为另一个的子结构
1.问题描述: 如何判断一个二叉树是否是另一个的子结构? 比如: 2 / \ 9 8 / \ / 2 3 5 / 6 有个子结构是 9 / \ 2 3 2.分析问题: 有关二叉树的算法问题,一般都可以通过递归来解决.那么写成一个正确的递归程序,首先一定要分析正确递归结束的条件. 拿这道题来讲,什么时候递归结束. <1>第二个二叉树root2为空时,说明root2是第一棵二叉树的root1的子结构,返回tr
随机推荐
- swift3.0 创建sqlite数据库步骤方法
- 用JS实现轮播图效果(二)
- ASP.NET MVC阿里大于短信接口开发短信群发能
- asp.net AJAX实现无刷新获得数据
- 在ASP.NET中重写URL的代码
- asp.net 大文件上传控件
- Banner程序
- Ajax 生成流文件下载(实现代码)
- PHP页面中文乱码分析
- Myeclipse连接mysql数据库心得体会
- MySQL OOM 系统二 OOM Killer
- jQuery对象的length属性用法实例
- ng-options和ng-checked在表单中的高级运用(推荐)
- 通过windows自带的系统监视器来查看IIS并发连接数(perfmon.msc)
- Andorid TextView字幕效果实例
- 比较简单的异步加载JS文件的代码
- 浅谈Zookeeper开源客户端框架Curator
- K均值聚类算法的Java版实现代码示例
- C语言中K-means算法实现代码
- 解决MyEclipse出现the user operation is waiting的问题