欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

《剑指offer》数字-进制转换:二进制中1的个数

程序员文章站 2024-03-17 12:59:40
...

题目

description:输入一个整数,输出该数二进制表示中1的个数。
其中负数用补码表示。

分析一

来自牛客网题解:一个数n与其n-1的与运算会消掉最右边一位的1耗时18ms
例如

n 二进制表示(int为32位,这里表示为8位) 与n-1的&运算
14 00001110 00001100
13 00001101 00001100
12 00001100 00001000
11 00001011 00001010

可以看出一个数n与其n-1的与运算会消掉最右边一位的1,然后再建立while循环判断。

代码

private static int NumberOf1V2(int n) {
       int count = 0;
        while(n != 0){
            count++;
            n = n & (n - 1); 
        }
        return count;
    }

分析二

自己最开始写的笨办法,没有从位运算的角度来想,写的比较繁琐,。。但是时间耗时为17ms。仅供参考。

思路

问题的难点主要在负数的补码表示。通过两个计数器完成。

  1. 判断正负,如果n > 0;进行n / 2 运算求得1的个数。
  2. 如果n < 0,考虑
    • n为偶数,其原码末尾为xxx000型,反码为xxx111型,补码为xxx000型,这种就需要计算(源码)末尾连0的个数。
    • n为奇数,原码末尾为xxx111型,反码为xxx000型,补码为xxx001型
      不需要计算连0的个数
    • 所以负数的判断为 32(int类型) - 原码除去首位的1的数(即(-n),步骤1可求)- 原码的末尾连0的个数(所有奇数都为0) + 1(取补码的操作)
    • 特殊的数字 -2147483648 它对应的正数不是int范围内,需特殊处理
      例如
n 原码 反码 补码 公式计算
-16 1001 0000 1110 1111 1111 0000 32 - 1 - 4 +1 = 28

代码

public static int NumberOf1(int n) {
        /*
        正数:依次求2的余数可以求出
        负数:int 为 32 位
            分奇偶数 111型和000型
        */
        if(n == 0){
            return 0;
        }else if(n > 0){
            return PositiveNumberOf1(n)[0];
        }else{
            int[] num = PositiveNumberOf1(-n);
            return n == Integer.MIN_VALUE ? 1 : 33 - num[0] - num[1];
        }
    }
    public static int[] PositiveNumberOf1(int n){
        int i = 0; //总体1的个数
        int m = 0; //111型结尾的连1数
        if((n & 1) == 1){//奇数,不考虑连0;
            while(n > 0){
                if(n % 2 == 1){
                    i++;
                }
                n = n >> 1;
            }
            return new int[] {i, 0};
        }else{//偶数
            int count = 0;
            boolean flag = false;
            while(n > 0){
                if(n % 2 == 0){
                    count++;
                }else{
                    i++;
                }
                if(i == 1 && flag == false){
                    m = count;
                    flag = true;
                }
                n = n >> 1;
            }
            return new int[] {i, m};
        }
改进版本:
public static int NumberOf1V3(int n) {
        /*
        减少无用的变量,直接将m加在i上返回。
        */
        if(n == 0){
            return 0;
        }else if(n > 0){
            return getPositiveNumberOf1(n);
        }else{
            return n == Integer.MIN_VALUE ? 1 : 33 - positiveNumberOf1(-n);
        }
    }
    public static int getPositiveNumberOf1(int n){
        int count = 0;
        while(n > 0){
            if(n % 2 == 1){
                count++;
            }
            n = n >> 1;
        }
        return count;
    }
    public static int positiveNumberOf1(int n){
        int i = 0; //总体1的个数
        boolean flag = false;
        while(n > 0){
            if(flag == false &&  n % 2 == 0){
                i++;
            }
            if(n % 2 == 1){
                System.out.println(i);
                i++;
                flag = true;
            }
            n = n >> 1;
        }
        return i;
    }