剑指Offer CountOneInBinary 计算二进制中1的个数

方法1：根据除2取余的方法判断1的个数

原理：一个数除以2相当于右移一位 如果除的过程中有与 表示当前位置有一个1

以10 100 010为例：

第一次除以2 商是1 010 001 余数是0 第二次除以2 商是 101 000 余数是1

代码实现：

public static int countByDivide(int num) { int count = 0; while (num != 0) { if (num % 2 == 1) { count++; } num = num / 2; } return count; }

方法二：使用位运算

当一个数进行无符号右移时 会丢弃最后一位 所以只要在右移过程中判断最后一位是否是1 来统计1的个数 要判断最后一位是否是1 只需要和0000 0001进行与运算即可

代码实现

public static int countByMove(int num) { int count = 0; while (num != 0) { count += num & 0x01; num = num >> 1; } return count; }

方法三：优化算法复杂度 让算法复杂度只和1的个数有关

public static int countByOne(int num) { int count = 0; while (num != 0) { num &= (num - 1); count++; } return count; }

方法四：一般的与运算

public int NumberOf1(int n) { int count = 0; for (int t = 31; t >= 0; t--) { if ((n & 1) == 1) { count++; } n = n >> 1; } return count; }

ps: 如果是负数 只有最好两种方法符合