如何判断一个整数的二进制中有多少个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
随机推荐
- 用JS判断IE版本的代码 超管用!
- java多线程应用实现方法
- 用js的for循环获取radio选中的值
- perl use 命令中指定路径的方法
- 找到了一篇jQuery与Prototype并存的冲突的解决方法
- oracle 索引的相关介绍(创建、简介、技巧、怎样查看) .
- php验证码生成器
- 跟老齐学Python之通过Python连接数据库
- 实例讲解Android App使用自带的SQLite数据库的基本方法
- PHPUnit PHP测试框架安装方法
- .net 单点登录的设计与实践
- java持久层框架mybatis防止sql注入的方法
- jQuery数据类型小结(14个)
- 通过Mybatis实现单表内一对多的数据展示示例代码
- 15个款优秀的 jQuery 图片特效插件推荐
- 基于jquery的一个图片hover的插件
- javascript 表单的友好用户体现
- Android实现ImageView图片缩放和拖动
- c#对字符串操作的技巧小结
- 基于JS实现仿京东搜索栏随滑动透明度渐变效果