算法--微软面试：整数的二进制表示中1的个数（Java实现）

爱被打了一巴掌 2022-06-13 07:39 271阅读 0赞

Q题目

整数的二进制表示中1的个数

  1. 输入一个整数，求该整数的二进制表达中有多少个1。
  2. 例如，输入10，由于其二进制表示为1010，有两个1，因此输出2。

这是一道很基本的考查位运算的面试题。

Answer解法

两种方式：

  1. 1.先将整数num转换为二进制后，在遍历
  2. 2.直接使用位运算

这道题的目的本就是考察位运算，所以建议采用第二种解法。

第二种算法中注意点：区别 右移>>和 无符号右移>>>

就该题本身而言，没有什么难度，这次就不做逻辑分析了。

代码如下

  1. public class Test {
  3.     public static void main(String[] args) {
  4.         //测试
  5.         System.out.println("方法一："+getCountOne(1801));
  6.         System.out.println("方法一："+getCountOne(-1801));
  7.         System.out.println("******************************");
  8.         System.out.println("方法二："+getCountOne2(1801));
  9.         System.out.println("方法二："+getCountOne2(-1801));
  10.     }
  12.     //方法一：进制转换后，for循环
  13.     public static int getCountOne(int num){
  14.         //1.转换为二进制
  15.         String binary=Integer.toBinaryString(num);
  16.         System.out.println(num+" 转化为二进制："+binary);
  17.         int count=0;//计数器
  18.         for(int i=0;i<binary.length();i++){
  19.             char x=binary.charAt(i);
  20.             if(x=='1'){
  21.                 count++;
  22.             }
  23.         }
  25.         return count;
  26.     }
  28.     //方法二：位运算
  29.     public static int getCountOne2(int num){
  30.         int count=0;
  31.         while(num!=0) {
  32.             if((num&1)==1) {
  33.                 count++;
  34.             }
  35.             //注意：必须使用无符号位右移(>>>)--区别于：右移(>>)，采用右移时，负数会陷入死循环(-1>>-1,结果为-1)
  36.             num = num>>>1;
  37.         }
  38.         return count;
  39.     }
  41. }

运算结果

  1. 1801 转化为二进制：11100001001
  2. 方法一：5
  3. -1801 转化为二进制：11111111111111111111100011110111
  4. 方法一：28
  5. ******************************
  6. 方法二：5
  7. 方法二：28

发表评论

表情：
评论列表 （有 0 条评论，271人围观）

还没有评论，来说两句吧...

相关阅读