如何判断一个整数的二进制中有多少个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
-
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
-
javascript中判断一个值是否在数组中并没有直接使用
在JS中要判断一个值是否在数组中并没有函数直接使用,如PHP中就有in_array()这个函数.但我们可以写一个类似in_array()函数来判断是一个值否在函数中 例1 复制代码 代码如下: /* * * 判断在数组中是否含有给定的一个变量值 * 参数: * needle:需要查询的值 * haystack:被查询的数组 * 在haystack中查询needle是否存在,如果找到返回true,否则返回false. * 此函数只能对字符和数字有效 * */ function findnum(){
随机推荐
- 用Asp与XML实现交互的一个实例源码
- 详谈Python基础之内置函数和递归
- JS实现手写parseInt的方法示例
- 字母顺序颠倒而单词顺序不变的php代码
- PHP实现图片旋转效果实例代码
- PHP函数preg_match_all正则表达式的基本使用详细解析
- Python实现将目录中TXT合并成一个大TXT文件的方法
- JSP中EL表达式用法_动力节点Java学院整理
- Android App仿微信界面切换时Tab图标变色效果的制作方法
- PureFTP借助MySQL实现用户身份验证的操作教程
- Python常用的日期时间处理方法示例
- 跟我学Nodejs(三)--- Node.js模块
- javascript简单事件处理和with用法介绍
- Jquery 数据选择插件Pickerbox使用介绍
- jQuery Ajax请求状态管理器打包
- Java基于正则表达式实现xml文件的解析功能详解
- asp.net(C#)中上传大文件的几中常见应用方法
- visual studio 2015+opencv2.4.13配置教程
- vue中的过滤器实例代码详解
- IDEA-Maven项目的jdk版本设置方法
其他
- springboot 设置启动端口
- data-url 重新赋值
- layui 接口有数据但页面没有
- python中如何执行同级目录下的py文件
- sql查询结果逗号拼接
- c# string 序列化如何去掉null值
- EntityWrapper or 用法
- linux dmp导入oracle
- f5刷新 mounted 中赋值不生效
- mybatis插入id过长
- android @GET传参
- nginx中配置503
- pandas 每行公约数
- this.$store.state.routes失败
- vue3 ts文件获取router store等实体类
- python教学管理系统代码
- springboot 读不到application.yml
- C# Eval 空格
- springboot树形菜单
- python-3.4.4 安装