討論區快速選單
知識庫快速選單
傑米的攝影旅遊筆記 網路投保旅行平安險
[ 回上頁 ] [ 討論區發言規則 ]
Compute the minimum or maximum of two integers
更改我的閱讀文章字型大小
作者 : ozzy123(ozzy) VC++優秀好手資訊類作業求救卓越專家C++卓越專家貼文超過4000則人氣指數超過30000點
[ 貼文 4498 | 人氣 37262 | 評價 11100 | 評價/貼文 2.47 | 送出評價 49 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/10/31 下午 04:25:48
as title
作者 : ozzy123(ozzy) VC++優秀好手資訊類作業求救卓越專家C++卓越專家貼文超過4000則人氣指數超過30000點
[ 貼文 4498 | 人氣 37262 | 評價 11100 | 評價/貼文 2.47 | 送出評價 49 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/10/31 下午 04:48:53
but can't use any branch instructions
作者 : rollboy(roller) 貼文超過200則人氣指數超過10000點
[ 貼文 396 | 人氣 24176 | 評價 370 | 評價/貼文 0.93 | 送出評價 62 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/11/5 下午 10:59:44
這好像也能用底下方式進行
http://www.programmer-club.com.tw/ShowSameTitleN/c/45352.html
作者 : sflam(Raymond)討論區板主 Visual C++ .NET卓越專家VC++一代宗師新手入門優秀好手資訊類作業求救頂尖高手C++一代宗師貼文超過4000則
[ 貼文 4945 | 人氣 9172 | 評價 32290 | 評價/貼文 6.53 | 送出評價 142 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/11/6 上午 12:09:53
網上搜尋至少有兩個方法:

方法一:
  Min(x, y): y ^ ((x ^ y) & -(x < y))
  Max(x, y): x ^ ((x ^ y) & -(x < y))

方法二:
  Min(x, y): y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)))
  Max(x, y): x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)))


同樣類似的問題都可以在這裡找到方法, 有興趣的自己去看看吧:
  http://graphics.stanford.edu/~seander/bithacks.html

作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/11/6 下午 10:39:59
有那一顆 CPU 可以翻出 X<Y 不會用到 branch instructions?
作者 : sflam(Raymond)討論區板主 Visual C++ .NET卓越專家VC++一代宗師新手入門優秀好手資訊類作業求救頂尖高手C++一代宗師貼文超過4000則
[ 貼文 4945 | 人氣 9172 | 評價 32290 | 評價/貼文 6.53 | 送出評價 142 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/11/7 上午 12:33:26
>有那一顆 CPU 可以翻出 X<Y 不會用到 branch instructions?

從 C 及 C++ 語言的角度來看, x < y 會得到 1 或 0, 它不是 branch.

編譯器要如何轉成低階語言就看編譯器程式員對平台的熟悉度了, 我對 IA-32 的 assembly 不能算熟練, 只能用手頭上的編譯器來看它們的編譯結果. 用 VC++ 及 gcc 的編譯結果, x < y 會轉成兩個句子: cmp, 及 setl. 看整個句子的 assembly 也看不出有 branch.

ARM 會轉成 IT (If-Then) 指令, 那就不符合樓主的要求, 但樓主也沒說明是那個層次的 branch instruction. 還是你認為樓主的意思是: 用高階語言來寫, 在任何平臺上編譯後的結果都不能有 branch?

作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/11/7 上午 10:45:58
>用 VC++ 及 gcc 的編譯結果, x < y 會轉成兩個句子: cmp, 及 setl. 看整個句子的 assembly 也看不出有 branch.
setl 是 set if less
如果branch instruction指的是跳轉到另一個地址的instruction,那麼set if less就合於題目要求。
但set if 的指令本身就含有branch的操作(它是if,set合併的複合指令),只是跳轉在一個指令裡完成。
我所知道的只有高階的x86和ARM有這種set if的指令。
題目應該有CPU的限定和branch instruction更清楚的解釋。
但解釋了,除了宣揚某cpu俱有set if的指令可以隱藏branch操作外,不知道有什麼意義。
作者 : sflam(Raymond)討論區板主 Visual C++ .NET卓越專家VC++一代宗師新手入門優秀好手資訊類作業求救頂尖高手C++一代宗師貼文超過4000則
[ 貼文 4945 | 人氣 9172 | 評價 32290 | 評價/貼文 6.53 | 送出評價 142 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/11/12 上午 02:07:10
>但set if 的指令本身就含有branch的操作(它是if,set合併的複合指令),只是跳轉在一個指令裡完成。

這點我不同意. branching 在 CPU 裡有特定的涵義及對效率的影響, 在某些 CPU 下, branching 的執行成本相當高, 因為 instruction pipeline 會被清除掉.

CPU 的 'set if' 沒有 branch 的操作. 'if' 不是 branch, 它是個 condition. setl 是個 conditional operation, 它跟高階語言的 if (...) {...} 是不同的, 它不會像 branching instructions 那樣影響效率.

CPU 的 'set if' 跟高階語言的 if-statement 是兩個不同層次的東西.
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/11/12 下午 12:04:33
>>但set if 的指令本身就含有branch的操作(它是if,set合併的複合指令),只是跳轉在一個指令裡完成。
>這點我不同意. branching 在 CPU 裡有特定的涵義及對效率的影響,
>在某些 CPU 下, branching 的執行成本相當高, 因為 instruction pipeline 會被清除掉.
>CPU 的 'set if' 沒有 branch 的操作. 'if' 不是 branch,
>它是個 condition. setl 是個 conditional operation, 它跟高階語言的 if (...) {...} 是不同的,
>它不會像 branching instructions 那樣影響效率.
>CPU 的 'set if' 跟高階語言的 if-statement 是兩個不同層次的東西.
本題應該不是在效率的議題,為了避開branch指令所付的花費,不會在效率上獲益。
我不是說了嗎,branch instruction如果指的是branch到另一個地址,那setl是OK的^^
但有像set if 指令的cpu少之又少,C/C++的題目,不指定CPU的情況,這就不算解。

另外即使是setl,在CPU設計的高階語言下(如VHDL)仍可看到if then等branch的指令。
這表示setl在邏輯上還是以branch來完成的(雖然編譯完後是看不到)。
如果題目的界定是在C/C++本身沒有branch,那麼 x>y?y:x應該也算是解,因為從語意的觀點它就是一個表示式
並不是branch statement(如同x>y)。
就看要把branch界定在那一個層次。
 板主 : simula
 > C++ - 討論區
 - 最近熱門問答精華集
 - 全部歷史問答精華集
 - C++ - 知識庫
  ■ 全站最新Post列表
  ■ 我的文章收藏
  ■ 我最愛的作者
  ■ 全站文章收藏排行榜
  ■ 全站最愛作者排行榜
  ■  月熱門主題
  ■  季熱門主題
  ■  熱門主題Top 20
  ■  本區Post排行榜
  ■  本區評價排行榜
  ■  全站專家名人榜
  ■  全站Post排行榜
  ■  全站評價排行榜
  ■  全站人氣排行榜
 請輸入關鍵字 
  開始搜尋
 
Top 10
評價排行
C++
1 Raymond 13050 
2 青衫 4760 
3 simula 4690 
4 coco 4030 
5 白老鼠(Gary) 3670 
6 ozzy 2540 
7 Ben 2250 
8 Anderson 1960 
9 windblown 1650 
10 Kenny 1560 
C++
  專家等級 評價  
  一代宗師 10000  
  曠世奇才 5000  
  頂尖高手 3000  
  卓越專家 1500  
  優秀好手 750  
Microsoft Internet Explorer 6.0. Screen 1024x768 pixel. High Color (16 bit).
2000-2019 程式設計俱樂部 http://www.programmer-club.com.tw/
0.171875