Re: [討論] 雙班 hw 9-2
※ 引述《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)
推
12/06 02:12, , 1F
12/06 02:12, 1F
討論串 (同標題文章)