Re: [問題] 不用if-else, for, while, do-while取絕

看板C_and_CPP作者 (河海不擇細水長流)時間8年前 (2016/04/07 00:54), 8年前編輯推噓14(14推 0噓 16→)
留言30則, 15人參與, 最新討論串2/5 (看更多)
※ 引述《CaliforCat (加州貓)》之銘言： : 對一個整數取絕對值 : 如果不用到if-else, for, while, do-while : 可以使用什麼方法 : 我想到的都是會用到上列的限制... : 請前輩指教 謝謝 這題假設照原本的限制 再加上不能用任何relational operator或logical operator 但可以使用bitwise operator 則abs(int)有哪些做法 有放推文的表示概念上是一樣我再重新用C實作 ※法1 #include <stdio.h> int main() { unsigned int num; while (scanf("%d", &num) != EOF) { num ^= (num >> (sizeof(num) * 8 - 1)) * ((num & (~num + 1) * (num | (~num + 1))); printf("%d\n", num); } return 0; } 說明： 這只是純粹0與1的遊戲，當正數時XOR的右運算元是0 sizeof(num) * 8 - 1用來找MSB 必用unsigned是因為在右移時不讓它補位 ※法2來了
推
04/07 04:32,
a*((a>0)*2-1)
04/07 04:32
#include <stdio.h> int main() { unsigned int num; while (scanf("%d", &num) != EOF) { num *= 1 - 2 * (num >> (sizeof(num) * 8 - 1)); printf("%d\n", num); } return 0; } x86組語如下： mov eax,[num] shr eax,1F add eax,eax mov edx,00000001 sub edx,eax mov eax,[num] imul eax,edx mov [num],eax 說明： 原來這麼根本不必拐彎抹角，用數學關係就能解了zzz果然還是不夠 原理就是當num是正數則乘以1，負數則乘以-1，找出用MSB生出1或-1的方法就行了 正數MSB是0，負數MSB是1，於是1-MSB*2就會是我們要的東西 ※法3
推
04/07 02:09,
int myabs(int i)
04/07 02:09
→
04/07 02:09,
{
04/07 02:09
→
04/07 02:10,
double d = i; unsigned long long *l = &d;
04/07 02:10
→
04/07 02:10,
*l <<= 1; *l >>= 1;
04/07 02:10
→
04/07 02:10,
return d;
04/07 02:10
→
04/07 02:10,
}
04/07 02:10
推
04/07 02:17,
上面的假設是int為32 bits, double和unsigned long long
04/07 02:17
→
04/07 02:17,
都是64 bits
04/07 02:17
#include <stdio.h> #include <stdint.h> int main() { union db2 { int64_t i; double d; }; int32_t num; db2 tmp; while (scanf("%d", &num) != EOF) { tmp.d = (double)num; tmp.i &= ~(1ull << (sizeof(double) * 8 - 1)); num = (int32_t)tmp.d; printf("%d\n", num); } return 0; } 說明： 有點邪門，先把int轉成double，而由於IEEE 754只用MSB控制正負號 於是把負數MSB幹掉後這個double就變成正數，再轉回int就是絕對值了 至於用union是因為double沒有bitwise運算子，必須把它視為整數型別才能做 ※法4 #include <stdio.h> #include <stdlib.h> // int abs(int); int main() { int num; while (scanf("%d", &num) != EOF) printf("%d\n", abs(num)); return 0; } 發現abs只用了三條x86指令就完成了<(_ _)> 然而這是編譯器最佳化的結果 當你寫(num > 0) ? num : -num就有可能會最佳化成以下這樣 mov eax,[num] cdq xor eax,edx sub eax,edx mov [num],eax 說明： 由於cdq在當eax是正數時edx是0，負數則是-1， 正數時和0做XOR此時正數會維持不變，負數時和-1做XOR變成1的補數也就是NOT結果 又在將負數轉正數取2的補數時只要NOT後再加一 第三條指令剛好就是減去-1 正數處理時減0維持不變 參考 https://www.strchr.com/optimized_abs_function ※法5 get absolute value without using abs function nor if statement StackOverflow http://stackoverflow.com/questions/9772348/ 底下有一個( n >> 31 | 1 ) * n我竟然沒想到要利用補位特性... #include <stdio.h> int main() { int num; while (scanf("%d", &num) != EOF) { printf("%d\n", (num >> (sizeof(int) * 4 - 1) | 1 ) * num); } return 0; } 太神啦 ※法6 開大直接寫shellcode Intel Syntax for VC++ int abs(int a) { __asm { mov eax, dword ptr[a] cdq xor eax, edx sub eax, edx } } AT&T Syntax for GCC int abs(int a) { asm ("mov %0, %%eax" :: "r" (a) : "%eax"); asm ("cdq"); asm ("xor %%edx, %%eax" ::: "%eax"); asm ("sub %%edx, %%eax" ::: "%eax"); } -- Sent from my Linux -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 134.208.48.204 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1459961675.A.E21.html
推
04/07 01:11, , 1F
https://ideone.com/lvKnkB sprintf+sscanf硬幹XD
04/07 01:11, 1F
→
04/07 01:16, , 2F
XD 在解一些無腦文字遊戲我也都不喜歡用腦直接硬幹
04/07 01:16, 2F
推
04/07 02:09, , 3F
int myabs(int i)
04/07 02:09, 3F
→
04/07 02:09, , 4F
{
04/07 02:09, 4F
→
04/07 02:10, , 5F
double d = i; unsigned long long *l = &d;
04/07 02:10, 5F
→
04/07 02:10, , 6F
*l <<= 1; *l >>= 1;
04/07 02:10, 6F
→
04/07 02:10, , 7F
return d;
04/07 02:10, 7F
→
04/07 02:10, , 8F
}
04/07 02:10, 8F
推
04/07 02:17, , 9F
上面的假設是int為32 bits, double和unsigned long long
04/07 02:17, 9F
→
04/07 02:17, , 10F
都是64 bits
04/07 02:17, 10F
※ 編輯: TobyH4cker (134.208.48.204), 04/07/2016 08:34:02
→
04/07 08:35, , 11F
這個太邪門啦
04/07 08:35, 11F
※ 編輯: TobyH4cker (134.208.48.204), 04/07/2016 08:35:50 ※ 編輯: TobyH4cker (134.208.48.204), 04/07/2016 09:06:12 ※ 編輯: TobyH4cker (134.208.48.204), 04/07/2016 09:54:30 ※ 編輯: TobyH4cker (134.208.48.204), 04/07/2016 09:56:02 ※ 編輯: TobyH4cker (134.208.48.204), 04/07/2016 10:02:52 ※ 編輯: TobyH4cker (134.208.48.204), 04/07/2016 11:03:05 ※ 編輯: TobyH4cker (134.208.48.204), 04/07/2016 11:11:41
推
04/07 11:32, , 12F
i = i & 0x7FFFFFFF; 這樣可以嗎?
04/07 11:32, 12F
→
04/07 11:39, , 13F
不能，負數是以2的補數表示，把整數的MSB抹掉會變別的
04/07 11:39, 13F
推
04/07 11:58, , 14F
i = i * ((((i>>31) ^ 1) << 1 )- 1); 這樣呢
04/07 11:58, 14F
→
04/07 12:03, , 15F
i = i * (( i>0 ) *2 - 1) 一樣啊
04/07 12:03, 15F
→
04/07 12:03, , 16F
你還假設int一定要32bit
04/07 12:03, 16F
推
04/07 12:06, , 17F
對吼,不知道有沒有CPU的指令集比較快
04/07 12:06, 17F
→
04/07 12:17, , 18F
就是abs 那樣已經是最精簡的了
04/07 12:17, 18F
※ 編輯: TobyH4cker (134.208.48.204), 04/07/2016 13:27:01 ※ 編輯: TobyH4cker (134.208.48.204), 04/07/2016 13:58:49
推
04/07 17:48, , 19F
推 這篇一堆超狂方法XD
04/07 17:48, 19F
推
04/07 23:04, , 20F
各種被玩弄的二進制數字與位元運算子XD
04/07 23:04, 20F
推
04/07 23:41, , 21F
wwwww
04/07 23:41, 21F
推
04/08 01:28, , 22F
以後管版務要來設一個腦筋急轉彎專區....
04/08 01:28, 22F
→
04/08 03:05, , 23F
我怎覺得像獵奇專區...
04/08 03:05, 23F
※ 編輯: TobyH4cker (134.208.48.204), 04/08/2016 11:05:50
推
04/08 11:59, , 24F
算法心得 短碼寫手表示:
04/08 11:59, 24F
推
04/08 12:40, , 25F
v = (v ^ (v >> 31)) - (v >> 31); // int32_t v;
04/08 12:40, 25F
→
04/08 12:40, , 26F
更多 bithacks 技巧以及解說 https://goo.gl/2m2qzH
04/08 12:40, 26F
→
04/08 13:28, , 27F
^看起來有點像在放阿哩固(誤
04/08 13:28, 27F
→
04/08 19:42, , 28F
cdq;xor;sub 這個好像是經典作法XD
04/08 19:42, 28F
推
04/10 17:35, , 29F
這篇不錯
04/10 17:35, 29F
推
04/21 10:56, , 30F
應該發文到SO賺點數XD
04/21 10:56, 30F
‣ 更多 TobyH4cker 的文章
文章代碼(AID): #1N1JzBuX (C_and_CPP)
討論串 (同標題文章)
完整討論串 (本文為第 2 之 5 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共5篇)
‣ 更多 TobyH4cker 的文章
文章代碼(AID): #1N1JzBuX (C_and_CPP)