剑指offer-二进制中1的个数

it2022-05-06  4

要求

请实现一个函数,输入一个整数,输出该数二进制表示中1的个数。例如,把9表示成二进制是1001,有2位是1。

思路

1.最简单的方法是,将整数转化成二进制,统计这个二进制中1的个数就行了 2.使用移位运算,任意整数和1进行 与 运算,如果该整数的最后一位 等于1,那么最后的结果是1,否则都是0,然后整数右移一位,继续判断最后一位是否是1,知道该整数位移到0。 3.使用 n & (n -1 ) 的方式。效果就是将 n的最后一个1去掉。 例如 8(1000)& 7(0111)= 0(0000)这个值就是将 8(1000)中的最后一个1去掉,也就变成了 0(0000) 7 & 6 = (0111)&(0110)= 6(0110),这个值就是将 7(0111)中的最后一个1去掉,也就变成了 6(0110)

例如:8(1000)= 7(0111)+ 1(0001) 8 & 7 = (1000)&(0111)= 0(0000) 7(0111)= 6(0110)+ 1(0001) 7 & 6 = (0111)&(0110)= 6(0110) 7 & 6 = (0111)&(0110)= 6(0110) 6 & 5 = (0110)&(0101)= 4(0100) 4 & 3 = (0100 &(0011)= 0(0000)

实现

package com.offer.test; /** * 计算二进制中1的个数 * @author zhouwenchen@021.com * @date 2019年6月17日 下午3:21:54 */ public class BitCountDemo { /** * 普通的方式实现 n左移的方式 * 如果此时数据是负数的话,这种右移的方式是错误的 * @param n * @return */ public static int bitCount1(int n) { int count = 0;// 计数器 while (n > 0) { if ((n & 1) == 1) { ++count; } n >>= 1; } return count; } /** * 更为精简的一种实现方式 * @param n * @return */ public static int bitCount2(int n) { int count = 0; for (; n > 0; n >>= 1) { count += n & 1; } return count; } /** * n&(n-1),就会清除n最后一位的1 * 例如:8(1000)= 7(0111)+ 1(0001) 8 & 7 = (1000)&(0111)= 0(0000) * 7(0111)= 6(0110)+ 1(0001) 7 & 6 = (0111)&(0110)= 6(0110) * 7 & 6 = (0111)&(0110)= 6(0110) * 6 & 5 = (0110)&(0101)= 4(0100) * 4 & 3 = (0100 &(0011)= 0(0000) * @param n * @return */ public static int bigCount3(int n){ int count = 0; for (; n > 0; count++){ n &=(n-1); 每一次计算,都是去掉原整数二进制中最后一位是1的数,直到这个n不大于0的时候,也就表示结束了 } return count; } /** * @param args */ public static void main(String[] args) { // System.out.println(bitCount1(15)); // System.out.println(bitCount1(-1)); // 如果是负数的话,这种解决方案是错误的 System.out.println(bitCount2(14)); // System.out.println(bitCount2(-1)); // System.out.println(bigCount3(9)); } }

最新回复(0)