首页 > 代码库 > 位运算:二进制中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 = 0for(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的个数