統(tǒng)計1的個數(shù)

統(tǒng)計1的個數(shù)

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

假定x? = ? 9999
10011100001111
答案:? 8


將x轉(zhuǎn)化為2進制，看含有的1的個數(shù)

x = x & (x - 1 )?這種算法是把一個二進制數(shù)最右邊的一個1變成0

然后呢？

x - 1與x區(qū)別在于最后二進制的1

每執(zhí)行一次x? = ?x & (x - 1 )，會將x用二進制表示時最右邊的一個1變?yōu)?，因為x - 1將會將該位(x用二進制表示時最右邊的一個1)變?yōu)?。

如果是二進制100, - 1 ，則為011

如果是二進制101， - 1則為100

與原數(shù)一與，就1后面的數(shù)，包括1全都與掉

明白，謝謝了?

不客氣

思路: 將x轉(zhuǎn)化為2進制，看含有的1的個數(shù)。
注: 每執(zhí)行一次x = x&(x-1)，會將x用二進制表示時最右邊的一個1變?yōu)?，因為x-1將會將該位(x用二進制表示時最右邊的一個1)變?yōu)?。(1) 如果一個數(shù)是2的n次方，那么這個數(shù)用二進制表示時其最高位為1，其余位為0。
判斷一個數(shù)(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 閱讀(1166) 評論(0)  編輯 收藏 引用 所屬分類: 算法＋數(shù)據(jù)結(jié)構(gòu)