Re: [問題]位元的1的計算
看板C_and_CPP (C/C++)作者gohomexx (gohomexx)時間16年前 (2010/02/24 17:56)推噓3(3推 0噓 0→)留言3則, 3人參與討論串2/2 (看更多)
※ 引述《markchen ()》之銘言：
: int bitcount (unsigned int n)
: {
: int count = 0 ;
: while (n)
: {
: count++ ;
: n &= (n - 1) ; //關鍵演算之處
: }
: return count ;
: }
: 事實上 程式上沒有問題，只是上文中的關鍵之處
: 8 = 1000
: 8 - 1 = 0111
: 這樣可以抓得到該值的二進位只是我不知道該怎麼詮釋這樣的作法
: 以前最為直觀的作法就是使用移位的方式
: 8 = 1000 向左移或向右移，計算有1的總合
: 但是n &= (n - 1) 我不知要怎樣想
提供我的想法供參考,
以位移方式計算時,至少要計算最高位元的次數,
例如 1 0 0 0 0 0 0 0至少要計算8次,
顯然不太聰明....
n & (n-1)的方法,
任何一個二進位數都是 2^n + 2^n-1 +.....+ 1 或是 2^n + 2^n-1 +... + 2
當這個二進位數是奇數時, n & (n-1) 會直接把最尾巴 1 的部份清掉,
所以就可以看成是計算 2^n + 2^n-1 + ... + 2 這個部份共有幾個 bit,
用例子來看 任何一個二進位可以表示成 xxxx 1 0...0 (共n個0) 的型式
xxxx 1 0...0
& xxxx 0 1...1 ( [xxxx 1 0...0] - 1 = [xxxx 0 1...1] )
---------------
xxxx 0 0...0
一下子跳掉 n 個 0, 足足省了 n-1 次計算...
xxxx 0 0...0 又可以表示成 xxxx 1 0...0的型式, 再依次計算.
以上,這個演算法的概念大概是這樣.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.220.110.100
推
02/24 19:10, , 1F
02/24 19:10, 1F
推
02/24 22:59, , 2F
02/24 22:59, 2F
推
02/25 00:20, , 3F
02/25 00:20, 3F
討論串 (同標題文章)
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章