Re: [問題] 針對一些考題的疑問。
其實如果是我面試我一定會問清楚以下：
除法和取餘的"概念"是否能用。
/和%一定不能用的，那除以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
:
: ※ 引述《Arton0306 (Ar藤)》之銘言：
:
: 我只是想針對 Q2 做一點意見。
:
: : : Q2.寫一個檢查輸入為3倍數的函數，但不能使用除法和餘數。
: : : 除了使用
: : : while(input>2){input-=3 check=input}if(check)...
: : : 這種算法外，還有更好的算法嗎?
: : 這方法不錯了
: : 不然利用3倍數的特性 寫一個function 把原數字轉字串後取出每個位的數字 求和
: : 看是否大於9 是的話 recursive 不是的話 若數字是0 3 6 9那就是3倍數
:
: 之前某論壇也是看到這題，目前大多都放在這解法上，
: 後來想到另一解法。
:
: 看一下這特性 -
:
: 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.
:
: --
: ※ 發信站: 批踢踢實業坊(ptt.cc)
: ◆ From: 180.177.76.201
: ※ 編輯: EdisonX 來自: 180.177.76.201 (01/08 19:16)
: 推 Arton0306:推！數學的方法很帥！ 01/08 20:07
: → EdisonX:謝謝 A 大稱讚,這份code還有改善空間便是 ^^ 01/08 20:11
: → DEATHX:讚，小弟我這邊看了覺得受益良多。 01/08 21:29
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.25.211.58
推
01/10 13:38, , 1F
01/10 13:38, 1F
討論串 (同標題文章)