C++ Jounior

統(tǒng)計(jì)1的個(gè)數(shù)

統(tǒng)計(jì)1的個(gè)數(shù)

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

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


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

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

然后呢？

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

每執(zhí)行一次x? = ?x & (x - 1 )，會(huì)將x用二進(jìn)制表示時(shí)最右邊的一個(gè)1變?yōu)?，因?yàn)閤 - 1將會(huì)將該位(x用二進(jìn)制表示時(shí)最右邊的一個(gè)1)變?yōu)?。

如果是二進(jìn)制100, - 1 ，則為011

如果是二進(jìn)制101， - 1則為100

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

明白，謝謝了?

不客氣

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