[分享] binary string 與 int 互轉

看板C_and_CPP作者 (小詹)時間12年前 (2012/06/20 18:31), 編輯推噓10(10推 0噓 77→)
留言87則, 8人參與, 最新討論串1/1
這是小詹自己寫的幾個function，是自己作業延伸出來做的。 為什麼呢？因為網路上找到能用的，速度都太慢>_<，不符合我作業的需求。 提供給版上需要的人參考。 當然，如果有bug，或者有更好的寫好，也請告訴我喔~~ 感謝各位為C&CPP貢獻的大大們！ 1。 binary to string function (版本1) inline int bin2int( string bin ){ int sum = 0; for( int i=0; i<bin.length(); ++i ){ // if( bin[i] == '0' ) sum *= 2; // else sum = sum*2+1; sum = (sum<<1) | (bin[i]&1); // 這個比較快！ XD } return sum; } 這版的想法很簡單，但由於用到了C++裡的string，速度實在不夠快。 中間的 sum*=2 我有考慮換成 sum<<=2 但實驗結果沒有比較快。 (小詹的實驗很簡單，兩個function計時各跑 N 次，看哪個時間花的少就是比較快 N 可為十萬、一百萬、一千萬，越大越明顯 ) 2。 binary to string function (版本2) inline int bin2int( const char* bin, int len ){ int sum = 0; for( int i=0; i<len; ++i ){ if( bin[i] == '0' ) sum*=2; else sum = sum*2+1; } return sum; } 這個版本跑得真的滿快的(希望能夠知道有更快的版本)，估計原因在於使用C本身的char* string，缺點就是，必須多傳一個參數len進來告知string的長度，如果用sizeof(bin)， 好像會有問題。 傳進來最保險。 小詹有比過例如一個string str = "110010"; 寫 bin2int( str ) 跟 bin2int( str.c_str(), str.length() ) 這兩種，真的是後者 比較快。 有興趣的朋友再自己實驗看看了。 3。 int to binary string function (第一種) inline string int2bin( int n, int len ){ int mask = 0x01; char pch[len]; int i = len; memset( pch, '0', len ); while( i!=0 ){ --i; if( n&mask ) pch[i] = '1'; n >>= 1; } return string( pch, len ); } 這也是我自己寫的版本，做法就是一直用 n>>=1 來讀最低的那個bit。 裡面一樣用到char的陣列，因為還是一樣，比c++的string快多了。 這個版本之所以要傳參數len，是讓使用者可以指定，回傳時的string長。 例如 int2bin( 5, 3 ) 會回傳 "101"，而int2bin( 5, 5 )會回傳"00101"， 在前面補了 0 。 如果不在意補0，小詹有另外一寫法，如下 4。 int to binary string (第二種) inline string int2bin( int n ){ char bits[32]; memset( bits, '0', 32 ); int i=31; while( n>0 ){ if( n%2 ) bits[i] = '1'; n >>= 1; // n = n/2 --i; } return string( &bits[i+1], 31-i ); } 這樣就只會回傳到剛剛好，不在前面補零。 這是小詹一點點的分享，感謝您的閱讀。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.218.146
→
06/20 18:36, , 1F
sum*=2會直接被優化成sum = sum << 2的樣子
06/20 18:36, 1F
→
06/20 18:37, , 2F
是 sum = sum << 1吧？
06/20 18:37, 2F
→
06/20 18:38, , 3F
但code上寫 sum <<= 1: 並沒有比較快，maybe是編譯器問
06/20 18:38, 3F
→
06/20 18:38, , 4F
題。 我是用dev c++ 4.9.9.2編譯的
06/20 18:38, 4F
※ 編輯: eejimchan 來自: 140.112.218.146 (06/20 18:39)
→
06/20 18:39, , 5F
sum = sum << 2 + bin[i] 可以減少一次判斷
06/20 18:39, 5F
→
06/20 18:40, , 6F
sum = sum << 1 + bin[i] - '0'
06/20 18:40, 6F
→
06/20 18:41, , 7F
sum << 2 是移動2個bits，意思等同x4喔！
06/20 18:41, 7F
→
06/20 18:42, , 8F
嗯嗯，好像可以耶
06/20 18:42, 8F
→
06/20 18:43, , 9F
我現在來實驗看看
06/20 18:43, 9F
→
06/20 18:47, , 10F
sum = sum << 1 + bin[i]&1
06/20 18:47, 10F
→
06/20 18:50, , 11F
有差一點。跑900萬次的結果，我的原寫法7.79秒
06/20 18:50, 11F
→
06/20 18:51, , 12F
改成 sum = sum<<1+bin[i]-'0' 為7.12秒
06/20 18:51, 12F
※ 編輯: eejimchan 來自: 140.112.218.146 (06/20 18:52)
→
06/20 18:54, , 13F
&1 更快 6.98秒。 感謝s大
06/20 18:54, 13F
→
06/20 19:01, , 14F
sum = (sum << 1)&(bin[i]&1)
06/20 19:01, 14F
→
06/20 19:06, , 15F
哇勒，更快！到6.7秒了
06/20 19:06, 15F
→
06/20 19:09, , 16F
但要改成 sum = (sum<<1)|(bin[i]&1) 才會對
06/20 19:09, 16F
→
06/20 19:29, , 17F
why Dev C++ .... OTZ
06/20 19:29, 17F
→
06/20 19:30, , 18F
樓上何意？
06/20 19:30, 18F
推
06/20 19:42, , 19F
我沒compile過，不過第3個可以compile嗎？
06/20 19:42, 19F
→
06/20 19:43, , 20F
沒細看,不過似乎都沒用查表技巧 ?
06/20 19:43, 20F
→
06/20 19:45, , 21F
Dev-C++ 是已經死掉的專案，官方沒有在維護了...
06/20 19:45, 21F
→
06/20 19:46, , 22F
喜歡的話也請用 Orwell fork 的版本
06/20 19:46, 22F
→
06/20 19:48, , 23F
http://goo.gl/zsMEc 這篇文章告訴你 Dev-C++ 是個悲劇XD
06/20 19:48, 23F
→
06/20 20:11, , 24F
呼叫的地方改成ref會更快吧，另外你的compiler版本是
06/20 20:11, 24F
→
06/20 20:12, , 25F
什麼0.0？
06/20 20:12, 25F
→
06/20 20:21, , 26F
Dev-Cpp default = 3.4.5 ...
06/20 20:21, 26F
→
06/20 20:43, , 27F
compile可以过。我是都跑过了才放上来分享的
06/20 20:43, 27F
→
06/20 20:44, , 28F
查表技巧是？
06/20 20:44, 28F
→
06/20 20:46, , 29F
查表 if else 不會比算數快吧？
06/20 20:46, 29F
→
06/20 21:02, , 30F
看了那篇文章後，我覺得裡面有個推文滿有道理的
06/20 21:02, 30F
→
06/20 21:03, , 31F
Dev C++是用來學習的。 若不是dev c++，我就不會想要如
06/20 21:03, 31F
→
06/20 21:04, , 32F
何改進code加快速度。用別人寫好的函式庫就好啦！但這樣
06/20 21:04, 32F
→
06/20 21:04, , 33F
就沒有練習到了
06/20 21:04, 33F
→
06/20 21:14, , 34F
查表不是if else，比較常是用array
06/20 21:14, 34F
→
06/20 21:16, , 35F
剛看了一下,這兩個例子似乎不適合查表就是了。
06/20 21:16, 35F
→
06/20 21:16, , 36F
@eej~: 你的code 最有問題應是這裡~char pch[len] ~ VLA
06/20 21:16, 36F
→
06/20 21:33, , 37F
沒辦法 這是限制int也是32bits 你要用new的也可以不影響
06/20 21:33, 37F
→
06/20 21:41, , 38F
mask0 = '0'; pch[i] = n&mask|mask0;
06/20 21:41, 38F
推
06/20 22:28, , 39F
第3個array的大小還沒決定也可以過喔@@，我印象中是不行
06/20 22:28, 39F
→
06/20 22:29, , 40F
我是不會c++，所以這是dev c++獨有還是怎樣？
06/20 22:29, 40F
→
06/20 22:35, , 41F
怎麼會說dev c++獨有這回事呢..
06/20 22:35, 41F
推
06/20 22:37, , 42F
這是個問句啊，我沒有下載dev c++來試，都是用邏輯來看
06/20 22:37, 42F
→
06/20 22:37, , 43F
我用gcc來試好了，驗證我的邏輯對不對
06/20 22:37, 43F
→
06/20 22:39, , 44F
有string這東西應該是c++的，算了XD
06/20 22:39, 44F
→
06/20 22:42, , 45F
dev c++是ide，跟語法不會有關系
06/20 22:42, 45F
推
06/20 22:52, , 46F
就算是ide也有綁定的compiler吧，我指是該版本綁的
06/20 22:52, 46F
→
06/20 22:52, , 47F
compiler可以容許這個語法讓我很吃驚
06/20 22:52, 47F
推
06/20 22:53, , 48F
c 大說的是這句嗎 pch[len] ？
06/20 22:53, 48F
→
06/20 22:54, , 49F
嗯，我看到一整個不舒服啊囧
06/20 22:54, 49F
→
06/20 22:54, , 50F
那叫可變長度陣列,C99有的,不過真的不建議用,蠻多compiler
06/20 22:54, 50F
→
06/20 22:55, , 51F
過不去.(補原文:Variable Length Array,VLA)
06/20 22:55, 51F
推
06/20 22:56, , 52F
了解謝謝，不過這個邏輯還蠻奇怪的，你compile時要怎麼決
06/20 22:56, 52F
→
06/20 22:57, , 53F
定stack的size，要是這個len是runtime才決定的話，放在
06/20 22:57, 53F
→
06/20 22:57, , 54F
stack要怎麼實作我很好奇就是
06/20 22:57, 54F
→
06/20 22:58, , 55F
我．猜．的． 直接在stack裡面切一大塊出來給它用.
06/20 22:58, 55F
→
06/20 22:58, , 56F
不夠用的時候就發error.
06/20 22:58, 56F
→
06/20 22:59, , 57F
用想的就覺得很危險啊…還是吃定你len不會太大嗎XD
06/20 22:59, 57F
→
06/20 22:59, , 58F
商業軟體的話我想這種寫法是絕對不允許的，如果我是老板
06/20 22:59, 58F
→
06/20 23:00, , 59F
你永遠想不到user會給你什麼input囧
06/20 23:00, 59F
→
06/20 23:01, , 60F
您不是第一個覺得VLA不好用,也不會是最後一個..
06/20 23:01, 60F
→
06/20 23:03, , 61F
直接用new還比較好，用vla也不能宣告太大啊
06/20 23:03, 61F
→
06/20 23:04, , 62F
不是不好用，其實以人的邏輯來想是好用的，只是從實作面
06/20 23:04, 62F
→
06/20 23:04, , 63F
來看風險不低就是
06/20 23:04, 63F
→
06/20 23:05, , 64F
要討論的話可能要開題吧,vla實作目前多半認為是用alloc.
06/20 23:05, 64F
→
06/20 23:06, , 65F
和我所認知的 stack 是有段差距。
06/20 23:06, 65F
→
06/20 23:07, , 66F
<alloca:在stack上配置記憶體,會自動釋放.不用手動>
06/20 23:07, 66F
推
06/20 23:18, , 67F
不過重點還是那個n吧，感覺起來是猜一個n來alloc
06/20 23:18, 67F
→
06/20 23:20, , 68F
我想補充一下，他的input是什麼？ 是int對吧？ 所以
06/20 23:20, 68F
→
06/20 23:20, , 69F
for最多run幾次？32次，那指定32一定夠用啊
06/20 23:20, 69F
→
06/20 23:21, , 70F
你user給一個input 256好了 轉成int還不是4個bytes
06/20 23:21, 70F
→
06/20 23:22, , 71F
你如果想一次轉更多bit，那這個function不適用
06/20 23:22, 71F
→
06/20 23:22, , 72F
而且我並沒有動態給定array的大小啊！我是寫char[32]
06/20 23:22, 72F
推
06/20 23:23, , 73F
現在討論的問題應該跟你的需求沒啥關係啦…純粹討論vla
06/20 23:23, 73F
→
06/20 23:23, , 74F
請問compiler是哪裡好不過啊？
06/20 23:23, 74F
→
06/20 23:23, , 75F
了解 我是回應早期的推文
06/20 23:23, 75F
→
06/20 23:24, , 76F
是一樣的東西啊，就是pch[len]這個寫法
06/20 23:24, 76F
→
06/20 23:25, , 77F
剛剛man了一下，alloc是不建議的用法，BUGS那欄有寫
06/20 23:25, 77F
→
06/20 23:25, , 78F
a
06/20 23:25, 78F
→
06/20 23:26, , 79F
不錯，丟了一個問題還多知道vla這東西XD，長知識
06/20 23:26, 79F
推
06/20 23:35, , 80F
#14XQNUYz 至此為止吧。沒人覺得不對，只覺得不大適合，
06/20 23:35, 80F
→
06/20 23:35, , 81F
也許跟 信仰 有關。
06/20 23:35, 81F
→
06/20 23:38, , 82F
2006年的都被挖出來了
06/20 23:38, 82F
→
06/20 23:39, , 83F
原來l大這麼早以前就在了！
06/20 23:39, 83F
推
06/22 03:15, , 84F
將每次只拿bin[i]改成一次32bit,http://ideone.com/7dazH
06/22 03:15, 84F
→
06/22 23:40, , 85F
樓上大大這種一定得傳32個字元才行 不方便
06/22 23:40, 85F
→
06/23 15:14, , 86F
改成任意長度很簡單http://ideone.com/6tzDh,這不是重點
06/23 15:14, 86F
→
06/23 15:15, , 87F
我想說的是一次取32bit運算應該比較快
06/23 15:15, 87F
※ 編輯: eejimchan 來自: 140.112.42.22 (10/03 12:11)
‣ 更多 eejimchan 的文章
文章代碼(AID): #1FuQQCRm (C_and_CPP)