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 閱讀(1137) 評論(0)  編輯 收藏 引用 所屬分類: 算法＋數據結構