剑指offer之二进制中1的个数
程序员文章站
2022-07-15 14:28:50
...
题目描述
输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
解题思路
- 一开始看到题目说负数用补码表示,以为是让我用补码表示输入的十进制负数再count,没想到意思是输入的就是补码表示的负数(我一直默认输入十进制,其实也可以二进制等TAT)。但是虽然是负数的补码右移会在最高位补1,因此会陷入死循环。。所以我一开始做题还是将输入的负数转为正数再计算1的个数,但是需要注意int的范围是
-2^31~2^31-1
,负数比正数多表示一位,即-2^31
没有对应的正数,需要特判。。关于负数中的1的计算公式=32-正数数位长+count(第一个1之后的0的个数)+1
Code
class Solution {
public:
int NumberOf1(int n) {
if(n == (-1<<31)) {
return 1;
}
int res = 0;
if(n < 0) {
n = -n;
int digitLength = 0, countZeros = 0, hasOne = 0;
while(n) {
digitLength ++;
if(n & 1) {
if(!hasOne) {
hasOne = 1;
}
} else {
if(hasOne) {
countZeros ++;
}
}
n = n >> 1;
}
res = 32-digitLength+countZeros+1;
} else {
while(n) {
res += n & 1;
n = n >> 1;
}
}
return res;
}
};
总结
上一篇: 位运算 -- 只出现一次的的数字
推荐阅读
-
如何求二进制数中1的个数
-
【LeeCode 中等 数学 python3】剑指 Offer 43. 1~n整数中1出现的次数
-
剑指offer11:输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。(进制转换,补码反码)
-
【剑指 Offer 53 - II】0~n-1中缺失的数字
-
剑指offer书(53)-2:0-n-1中缺失的数字
-
剑指OFFER----53-2、0~n-1中缺失的数字(js实现)
-
剑指 Offer 53 - II. 0~n-1中缺失的数字
-
剑指offer 53 - II. 0~n-1中缺失的数字
-
剑指 Offer 53 - II. 0~n-1中缺失的数字
-
剑指Offer编程题--数组中重复的数字