如何判断一个整数的二进制中有多少个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)。

赞 (0)

相关推荐

  • 如何判断一个整数的二进制中有多少个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实现判断一个整数是否为回文数算法示例

    本文实例讲述了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次方幂的实例

    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(){

随机推荐

其他