剑指offer--面试题10

题目:求整数二进制表示中1的个数。

分析:此题直接考查二进制表示与位运算!!!

   正数和负数的二进制表示不同!在计算机中,正数的二进制表示即为通常所写的二进制;而负数的二进制表示则用补码表示,即原码的反码再+1。

   比如:1) 9:在32位计算机中表示为(十六进制)0x00000009 (其原码=反码=补码=0x00000009);

      2) -9:在32位计算机中表示为(十六进制)0xFFFFFFF7 ,原因:-9的原码=0x00000009,-9的反码=0xFFFFFFF6,-9的补码=0xFFFFFFF7

        所以,-9的二进制表示中1的个数为31 !

  另外,拿8位二进制来说,当表示有符号数时,00000000~01111111表示十进制0~127,而10000000~11111111表示十进制-128~-1 !!!

  位运算比乘除的效率更高!

解决该题时,首先想到的就是避免死循环的那种方法(这里值得骄傲一下!呵呵)

不过,虽然想到了左移1的方法,但由于当时对负数的二进制表示不熟悉,所以认为该方法可能对负数不起作用。。。

但仍先编写了如下代码,目的是验证应用于正数时是否有效:

//未考虑负数情况
int OneNumInBinaryForm(int n)
{
int Anded = ;
int i = ; //i为二进制中1的位置
int maxbits = sizeof(n)*;
//std::cout<<maxbits<<std::endl;
int OneNums = ;
while(i <= maxbits)
{
int Anded_iter = Anded<<(i-);
if((Anded_iter&n) != )
OneNums++;
i++;
}
return OneNums;
}
int main(int argc, char* argv[])
{
int n = ; int nums = OneNumInBinaryForm(n);
std::cout<<nums<<std::endl; return ;
}

不过,在理解了负数的二进制表示后,发现以上代码同样适用于负数,其总体思路和作者的参考代码一致!

但还是那句话,参考代码更加简洁、高效!

//根据作者代码,重写n为正、负数的情况
int NumberOf1(int n)
{
int count = ;
unsigned int flag = ; while(flag)
{
if((flag&n) != )
count++;
flag = flag<<;
} return count;
} int main(int argc, char* argv[])
{
int n = ; int nums = NumberOf1(n);
std::cout<<nums<<std::endl; return ;
}

参考代码中用flag作为循环终止条件,比自己所写的用数字所占位数(sizeof),要好很多。。。,关键在于自己没有想到1在循环左移后,最终会变为0!!!

经验证,-9的二进制表示中1的个数的确为 31!

作者所提供的更NB的方法太巧妙,自己很难想到啊!

int NumberOf1(int n)
{
int count = ; while(n)
{
count++;
n = n&(n-);
} return count;
}

思想:只要n非零,则n的二进制表示中必有1,且认为该1位于二进制表示的最右边。(while(n),count++);

在计数之后,消除该位置上的1(1->0),采取方法为n&(n-1)(这是较难想到的关键!);

    n=n&(n-1),再循环。

对负数,同样适用!

上一篇:P78、面试题10:二进制中1的个数


下一篇:Navigation Bar options for Android (based on photosomething project)