[問題] 如何快速求出最左邊bit為1的位置

看板C_and_CPP作者 (HANA)時間16年前 (2009/12/31 13:23), 編輯推噓3(3推 0噓 10→)
留言13則, 7人參與, 最新討論串1/3 (看更多)
假設今天我有一個bit 串列 N=010010，我想快速求出最左邊的1 也就是010000 如果是最右邊的話 可以用 N XOR (N-1) & N 取得 但是最左邊目前沒什麼概念可以解這問題 有沒有高手可以指點一下 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.117.169.152
→
12/31 13:48, , 1F
我剛剛想到的是… ＝＿＝|||
12/31 13:48, 1F
→
12/31 13:49, , 2F
{ [(~N)+1] xor N } &N 不知道對不對？
12/31 13:49, 2F
→
12/31 13:51, , 3F
上式是：{ [反相加一] XOR N } AND N
12/31 13:51, 3F
推
12/31 13:56, , 4F
把串列顛倒過來 ?
12/31 13:56, 4F
→
12/31 14:01, , 5F
(~((~0)>>1))&N
12/31 14:01, 5F
推
12/31 14:01, , 6F
把串列倒過來不如就直接跑迴圈找下去了啊XD
12/31 14:01, 6F
→
12/31 14:01, , 7F
歐 不是這個
12/31 14:01, 7F
推
12/31 14:03, , 8F
這快的話,要直接用CPU指令去找..用gcc有ffs(FindFirstSet)
12/31 14:03, 8F
→
12/31 14:04, , 9F
用vc的話,有_BitScanForward 等可以用..
12/31 14:04, 9F
→
12/31 14:09, , 10F
看起來像是floor( log2(N) )
12/31 14:09, 10F
→
12/31 16:18, , 11F
去找 hacker's delight 來看
12/31 16:18, 11F
→
12/31 23:30, , 12F
這種東西很多 DSP 都會有特殊指令支援，所以想也知道不會
12/31 23:30, 12F
→
12/31 23:30, , 13F
有真正快的方法在 C-level。
12/31 23:30, 13F
‣ 更多 del680202 的文章
文章代碼(AID): #1BF3LRth (C_and_CPP)
‣ 更多 del680202 的文章
文章代碼(AID): #1BF3LRth (C_and_CPP)