面试题15:二进制中1的个数
输入一个整数,输出该数32位二进制表示中1的个数。其中负数用补码表示。
思路:我想的蠢方法当然是一个个的检验二进制序列里面有没有1,但是这种方法也有陷阱。
方法1:判断整数二进制序列最右边是不是为1,判断方法可以是整数n与无符号数1进行位与,若结果为1,则最右边为1,否则,最右边为0;判断完一位后,将整数二进制向右移。这种方法有个很大的弊端:若n是个负数,一直右移右移,最后会变为0xFFFFFFFF,造成死循环。所以想到第二种常规方法。
方法2:既然移动整数会造成死循环,那就不要移动它。设置一个无符号标志位flag=1,左移flag与n进行位相与判断结果。例如,当flag=0x000...0001时,可以检查n最低位是否为1;flag左移变为0x000...0010可以检测n次低位是否为1....依次循环32次,到flag=0时检查完成。
代码:
int binary_system(int digit) { unsigned long int flag = 1; int count = 0; while (flag) { if (digit & flag) count++; flag = flag << 1; } return count; }