Re: [問題] 針對一些考題的疑問。
這有規律:
1 mod 3 = 1
2 mod 3 = 2
4 mod 3 = 1
8 mod 3 = 2
16 mod 3 = 1 ...
(背後的原因是因為 mod 3 群中, 1 和 2 互為自己的乘法反元素)
因此, 若輸入值為x, 則演算法可以化簡為
1. a = 取 x 的奇數位bit為1的個數
2. b = 取 x 的偶數位bit為1的個數
3. x = a + 2 * b
4. 若 x >= 3 回到 1
用這個方法收斂速度會快很多
如果搭配陣列把int分成多部份做快速index
應該也可以不用迴圈
舉例而言,
x = 146,
則 146 mod 3 = (128 + 16 + 2) mod 3 = 2 + 1 + 2 mod 3 = 2
用演算法來看的話
x = 146
146 二進位表示為 10010010
奇數位的bit是1的有1個
偶數位的bit是1的有2個
新的 x = 1 + 2 * 2 = 5
x = 5
5 二進位表示為 101
奇數位的bit是1的有2個
偶數位的bit是1的有0個
新的 x = 2 + 0 * 2 = 2
因此 146 mod 3 = 2
※ 引述《bleed1979 (十三)》之銘言：
: 其實如果是我面試我一定會問清楚以下：
: 除法和取餘的"概念"是否能用。
: /和%一定不能用的，那除以4我改>>2這樣算對還是錯？
: 在我的標準我覺得是不能用的。
: 但想來想去似乎還是倚賴了位元運算。
: 我的寫法和E大雷同，概念上都是對4動腦筋。
: 方法是可以分四部分那就把三部分丟掉，留最後一部分和分四部分剩下的零數。
: 一直做到不能分四部分，再探討其結果。
: unsigned MOD3(unsigned x) {
: unsigned work = x, part;
: while(work > 3) {
: part = work >> 2;
: work = work - (part << 2) + part;
: }
: return work == 3 ? 0 : work;
: }
: ※ 引述《EdisonX (閉上眼的魚)》之銘言：
: : 標題: Re: [問題] 針對一些考題的疑問。
: : 時間: Sun Jan 8 18:57:56 2012
: : 我只是想針對 Q2 做一點意見。
: : 之前某論壇也是看到這題，目前大多都放在這解法上，
: : 後來想到另一解法。
: : 看一下這特性 -
: : 95 mod 3 = (1 + 32 + 64 ) mod 3 = 1 mod 3 = 3
: : 這特性是花五分鐘觀查出來的，我也不保證這是最快的方式，
: : (面試的時候可能是很久的時候，所以第一次看到可能會想不到)
: : 2^n + 2^(n+1) 必為 3 之倍數
: : 所以用 shift right + and gate 可做一點加速，效率會不會比較快留著待分析
: : ( 和布斯乘法器一樣，有些情況會比較慢 )
: : 類似觀念可以變成用 3bits、4bits 方式分析，(3 bits 可能不好做或不能做)
: : ( 就像是改善形的布斯乘法器 )
: : unsigned Mod3(unsigned x)
: : {
: : unsigned sum;
: : do{
: : sum = 0;
: : while(x) {
: : sum+=x&0x3; // 取最後 2 bits
: : x>>=2;
: : }
: : x = sum;
: : }while(sum>3);
: : return sum==3 ? 0 : sum; // 最後等於 3 額外判斷
: : }
: : 這應也不是最快的方式，在猜想最快的方式應該是用 floating multi. 去做，
: : 可能一、二行就出來了，只是那個 magic number 可能面試的時候時間有限，
: : 找不出來吧。
: : --
: : If there is no tomorrow,
: : I want to see u last time.
: : --
: : ◆ From: 180.177.76.201
: : 推 Arton0306:推！數學的方法很帥！ 01/08 20:07
: : → EdisonX:謝謝 A 大稱讚,這份code還有改善空間便是 ^^ 01/08 20:11
: : → DEATHX:讚，小弟我這邊看了覺得受益良多。 01/08 21:29
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.70.119
→
01/08 22:13, , 1F
01/08 22:13, 1F
→
01/08 22:14, , 2F
01/08 22:14, 2F
→
01/08 22:16, , 3F
01/08 22:16, 3F
→
01/08 22:17, , 4F
01/08 22:17, 4F
推
01/09 05:46, , 5F
01/09 05:46, 5F
→
01/09 05:46, , 6F
01/09 05:46, 6F
推
01/10 00:32, , 7F
01/10 00:32, 7F
其實這個方法本身可以推廣到mod任意奇數p
因為2本身是偶數
和任意奇數一定互質
因此2^k mod p 一定會是重複數列 (Euler定理)
ex. 2^k mod 5 的循環是 2, 4, 3, 1, ...
2^k mod 7 的循環是 2, 4, 1, ...
2^k mod 9 的循環是 2, 4, 8, 7, 5, 1, ...
所以對於任意奇數p而言
只要計算相對應位數的bit個數
再乘上相對應的循環數
就可以得知答案了
※ 編輯: chubiei 來自: 114.32.70.119 (01/10 01:07)
推
01/10 10:46, , 8F
01/10 10:46, 8F
→
01/10 10:47, , 9F
01/10 10:47, 9F
→
01/10 10:48, , 10F
01/10 10:48, 10F
討論串 (同標題文章)