《剑指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。仅供参考。
思路
问题的难点主要在负数的补码表示。通过两个计数器完成。
- 判断正负,如果n > 0;进行n / 2 运算求得1的个数。
- 如果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;
}
推荐阅读
-
《剑指offer》数字-进制转换:二进制中1的个数
-
剑指 二进制中1的个数
-
牛客网-剑指offer[编程题]二进制中1的个数 js详解
-
剑指 Offer 53 - II. 0~n-1中缺失的数字 python
-
剑指 Offer 53 - II. 0~n-1中缺失的数字
-
[leetCode]剑指 Offer 53 - II. 0~n-1中缺失的数字
-
[LeetCode]剑指 Offer 53 - II. 0~n-1中缺失的数字
-
Leetcode 剑指 Offer 53 - II. 0~n-1中缺失的数字
-
剑指offer:输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
-
剑指offer:输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。