PTT數位生活區 / C_and_CPP (C/C++)

[問題]位元的1的計算

看板C_and_CPP (C/C++)作者時間16年前 (2010/02/24 16:32), 編輯推噓6(6推 0噓 9→)
留言15則, 6人參與, 最新討論串1/2 (看更多)
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) 我不知要怎樣想 -- -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.45.148.54 ※ 編輯: markchen 來自: 114.45.148.54 (02/24 16:32)
推
02/24 16:34, , 1F
loop bit scan會固定掃完所有low part bits; 這個方法則
02/24 16:34, 1F
→
02/24 16:35, , 2F
是有效的一次跳過了 bit 為 0 的連續bits, 推一下吧:)
02/24 16:35, 2F
推
02/24 16:42, , 3F
扛漸庢N是把最右邊的 1 給變成 0
02/24 16:42, 3F
→
02/24 16:42, , 4F
它的用意
02/24 16:42, 4F
→
02/24 16:42, , 5F
所以計算到 0 之前的次數就可以得它的 1 的個數了
02/24 16:42, 5F
→
02/24 16:43, , 6F
拿幾個二進位值去試試就知道為什麼是這個樣子了
02/24 16:43, 6F
推
02/24 21:54, , 7F
既然是C++版，那當然是一定要用 bitset 瞬間解決問題啊
02/24 21:54, 7F
→
02/25 00:08, , 8F
其實還有另一種平行算法，更快更小
02/25 00:08, 8F
推
02/25 09:30, , 9F
建表吧，我記得是最快的。
02/25 09:30, 9F
推
02/25 09:48, , 10F
建表應該是最快沒錯, 但是感覺撐不上小....@_@"
02/25 09:48, 10F
→
02/25 20:47, , 11F
所以不是建表～
02/25 20:47, 11F
→
02/25 22:57, , 13F
看 Counting bits set, in parallel 這一小節
02/25 22:57, 13F
→
02/25 22:58, , 14F
走火入魔級....
02/25 22:58, 14F
→
02/26 12:13, , 15F
沒錯，就是 in parallel 這個又快又小的方法
02/26 12:13, 15F
‣ 更多 markchen 的文章
文章代碼(AID): #1BXEGUGu (C_and_CPP)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共2篇)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 markchen 的文章
文章代碼(AID): #1BXEGUGu (C_and_CPP)