※ 引述《oncemore (槍不能這樣打)》之銘言： : 給一些不會做circular shift 的同學參考，當然這不是唯一解 : 假設一個數字(number)，經過運算之後會得到一個數值(result) : 你現在的任務就是要把題目給的result 轉換成原本的number。 : int number; : int number_mod; : int result; : int shift; : not 的部分： : number = ~number; : result = number + 256; : (Ex.)以範例測資1來說， : df(16進位) = 223 (10進位)...我們要的result是223 : number = 32;(要得到223的解) : number = ~number; (此時number == -33 ) : result = number + 256; (result == 223) : 所以我們找到32經過not的運算後可以得到df，也就是223， : 所以要把(ASCII碼)32對應到的字元印出來。 之所以這樣的原因, 是因為 int 佔了 4 個 bytes, 而我們輸入的數值只有 0-255 number：00 00 00 df 做了 not 運算之後會變成這樣 ~number:ff ff ff 20 而 256 正好是 00 00 01 00, 所以加到 ~number 上剛好讓前三個 ff 溢位變成 0 回來 實際上我們可以很直觀的想：我們要的只是最後 8 個 bit 所以 (~number) & 0xff 就好了, 甚至你把 number 存成一個 unsigned char, 那 ~number 自然會是 0x20 不知道想到 (~number) + 256 的原因是不是從 (-a) = (~a) + 1 這樣來的呢:) : 這裡你可以用 number 從 0 跑到 255 去找出對應的值， : 找到了之後就記錄起來並 break 掉。 反過來想，一個數字 not 兩次之後跟沒 not 一樣 輸入的是 not 過的數字，要找 not 之前的數字，再 not 一次就好，就變回來了 : leftR 的部分：(假設要轉的位數是shift位) : number = number * pow( 2 , shift%8 ); (你要include <math.h> ) : number_mod = number % 256; : number = number / 256; : result = number + number_mod; : (Ex.)以範例測資1來說， : leftR 3，向左側移三位。 : 1(16進位) = 1(10進位)...我們要的result是1 : shift = 3; : number = 32;(要得到1的解) : number = number * pow(2,shift%8); (number == 32 * 8 == 256 ) : number_mod = number % 256;(number_mod == 0 ) : number = number / 256;(number == 1 ) : result = number + number_mod; (result == 1 + 0 == 1 ) : 於是我們找到了32可以經過左移三位後得到1 : rightR 的部分：(假設要轉的位數是shift位) : number = number * 256; : number = number / pow( 2 , shift%8 ); : number_mod = number % 256; : number = number / 256; : result = number + number_mod; : (Ex.)以範例測資1來說， : rightR 4，向右側移四位。 : 2(16進位) = 2(10進位)...我們要的result是2 : shift = 4; : number = 32(要得到2的解) : number = number * 256; (number == 8192) : number = nubmer / pow ( 2 , 4 ); (number == 512) : number_mod = number % 256; (number_mod == 0) : number = number / 256; (number == 2) : result = number + number_mod; (result = 2) : 於是我們找到了32可以經過右移四位後得到2 這邊我不太確定 pow 是不是那個 pow 函式？ 可是我怎麼記得那個 pow 是浮點數的@@ 其實可以這樣想： 01234567 ror 1 70123456 ror 2 67012345 ...類推 首先考慮只向右輪旋一個位元的情形 他可以直接被拆解成 0123456 右移一位, or 7 左移 7 位 所以我們可以寫出如下的程式： output = (input >> 1) | ((input << 7) & 0xff) 0123456右移一位 or 左移 遮罩掉我們不要的位元(突出去的) 同理，若移 2 位也是類似 output = (input >> 2) | ((input << 6) & 0xff) 觀察規律, 可以知道是類似 output = (input >> i) | ((input << (8 - i)) & 0xff) 的東西, 其中 i 是旋轉的位數, 且 0 ≦ i < 8 當然輪旋了八次後與沒輪旋也是一樣的, 所以可以先把次數 mod 8 : 補充：對於left 和 right 的作法， : 我是想像成16個bits在做運算 : 以上是我的作法， : 請各位多多指教，謝謝。 p.s. 我個人在想位運算的時候 比較喜歡用兩進位或十六進位來看 好像比較直覺XD 此外, << a 相當於乘上 2^a, >> a 則相當於除以 2^a (整數除法), 這都很方便使用 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.217.34.61 ※ 編輯: suhorng 來自: 61.217.34.61 (12/06 00:08)