[問題] most significant bit

看板C_and_CPP (C/C++)作者 (realgirl)時間1年前 (2023/03/26 15:22), 編輯推噓4(407)
留言11則, 4人參與, 1年前最新討論串1/1
各位大大好, 請問如果給您選擇, 您會選哪個函式來找出MSB呢? int get_highest_bit_position(unsigned char x) { int n = 7; if (x == 0) return -1; if ((x >> 4) == 0) { n = n-4; x=x << 4;} if ((x >> 6) == 0) { n = n-2; x=x << 2;} if ((x >> 7) == 0) { n = n-1;} return n; } int get_highest_bit_position(unsigned char x){ for(int i = 7; i >= 0 ; --i){ if(0b10000000 & x){return i;} else{x = x << 1;} } return 0; } 謝謝! ----- Sent from JPTT on my iPhone -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.49.99 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1679815376.A.FA6.html

03/26 16:43, 1年前 , 1F

03/26 16:44, 1年前 , 2F
C++20 把這個標準化了, 之前各家編譯器的這函數有各自名字
03/26 16:44, 2F

03/26 16:45, 1年前 , 3F
更多可參考維基百科↓
03/26 16:45, 3F

03/26 16:45, 1年前 , 4F

03/27 07:52, 1年前 , 5F
如果自幹的話我有看過1+最後4bit查表的做法
03/27 07:52, 5F

03/27 07:54, 1年前 , 6F
不過還是call clz比較省事
03/27 07:54, 6F

03/27 18:38, 1年前 , 7F
clz > 2 > 查表 > 1
03/27 18:38, 7F

03/29 00:40, 1年前 , 8F
2是O(N) 1是O(lgN), 查表是O(1)但是表不能太大
03/29 00:40, 8F

03/29 00:41, 1年前 , 9F
所以以前看xvid的實做不會用2
03/29 00:41, 9F

04/03 17:55, 1年前 , 10F
這兩個應該都是O(1) 他們都可以在某個常數時間完成
04/03 17:55, 10F

04/05 09:46, 1年前 , 11F
啊我說的N是bit數,64b的時候指令數就明顯有差
04/05 09:46, 11F
文章代碼(AID): #1a7_BG-c (C_and_CPP)
文章代碼(AID): #1a7_BG-c (C_and_CPP)