首页 > 代码库 > 位运算:二进制中1的个数
位运算:二进制中1的个数
- 题目描述:
输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
-
分析:
作为渣渣,这个题我一开始真没想到用位运算。。
首先,说到二进制,就应该想到二进制的各种运算:按位与运算(&)、按位或运算(|)、按位异或运算(^)、按位取反(~)。再看题目,要求二进制表示中1的个数,既然要求1的个数,那就是说要看这个二进制数的每一位是不是1,所以可以想到,用1去和二进制数里的每一位进行与(&)运算即可,因为1&1的1,1&0得0。接下来说两种思路
思路1:右移
用输入整数的最后一位和1进行与运算,结果为1则递增计数器;然后将整数右移,此时整数的最后一位即原整数的倒数第二位,继续与1进行与运算;直到整数变为0。
但是这个思路有一个bug,对于负数,右移过程中,最高位将自动补1!这样的话,当右移次数超过31次的时候,这个整数将变为0xFFFFFFFF(说到这再补一下32位整型的范围:0x7FFFFFFF~0x80000000,根本提无关,单纯复习),此时会进入死循环。
但是,这种思路也不是不可用,只要在右移时让其最高位不补1而是补0就好了,也就是所谓的逻辑位移。当然,为了简便,也完全没必要特意写个逻辑位移函数出来,还有两种方法:一是可以直接用位移次数来控制循环;二是先判断正负,如果是负数先把计数器加1,记录符号位的1,然后再把最高位置0,剩下的就可以直接进行右移了。code:
int NumberOf1(int n) { int count = 0; for(int i = 0; i < 32; ++i){ if(n & 1) ++count; n >>= 1; } return count; }
思路2:左移
既然右移输入的整数容易陷入死循环,那么左移1就好了,每左移一次1求与运算,就相当于向整数的前一位求与。code:
int NumberOf1(int n) { int count = 0; unsigned int flag = 1; while(flag){ if(n & flag) ++count; flag <<= 1; } return count; }
位运算:二进制中1的个数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。