C++ Jounior

统计1的个数

统计1的个数

int  func(x)
{
     int  countx  =   0 ;
     while (x)
     {
        countx ++ ;
        x  =  x & (x - 1 );
    }
     return  countx;
}  

假定x  =   9999
10011100001111
答案:  8


将x转化为2进制，看含有的1的个数

x = x & (x - 1 ) 这种算法是把一个二进制数最右边的一个1变成0

然后呢？

x - 1与x区别在于最后二进制的1

每执行一次x  =  x & (x - 1 )，会将x用二进制表示时最右边的一个1变为0，因为x - 1将会将该位(x用二进制表示时最右边的一个1)变为0。

如果是二进制100, - 1 ，则为011

如果是二进制101， - 1则为100

与原数一与，就1后面的数，包括1全都与掉

明白，谢谢了 

不客气

思路: 将x转化为2进制，看含有的1的个数。
注: 每执行一次x = x&(x-1)，会将x用二进制表示时最右边的一个1变为0，因为x-1将会将该位(x用二进制表示时最右边的一个1)变为0。(1) 如果一个数是2的n次方，那么这个数用二进制表示时其最高位为1，其余位为0。
判断一个数(x)是否是2的n次方

#include  < stdio.h >

int  func(x)
{
     if ( (x & (x - 1 ))  ==   0  )
         return   1 ;
     else
         return   0 ;
}

int  main()
{
     int  x  =   8 ;
    printf( " %d\n " , func(x));
 }

posted on 2008-04-02 09:17 snowball 阅读(1122) 评论(0)  编辑 收藏 引用 所属分类: 算法＋数据结构