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

[TobyH4cker (河海不擇細水長流)]

※ 引述《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來了

推 CaptainH: a*((a>0)*2-1)
#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

推 chubiei: int myabs(int i)
→ chubiei: {
→ chubiei:     double d = i; unsigned long long *l = &d;
→ chubiei:     *l <<= 1; *l >>= 1;
→ chubiei:     return d;
→ chubiei: }
推 chubiei: 上面的假設是int為32 bits, double和unsigned long long
→ chubiei: 都是64 bits
#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
推 Frozenmouse: https://ideone.com/lvKnkB sprintf+sscanf硬幹XD
→ TobyH4cker: XD 在解一些無腦文字遊戲我也都不喜歡用腦直接硬幹
推 chubiei: int myabs(int i)
→ chubiei: {
→ chubiei:     double d = i; unsigned long long *l = &d;
→ chubiei:     *l <<= 1; *l >>= 1;
→ chubiei:     return d;
→ chubiei: }
推 chubiei: 上面的假設是int為32 bits, double和unsigned long long
→ chubiei: 都是64 bits
※ 編輯: TobyH4cker (134.208.48.204), 04/07/2016 08:34:02
→ TobyH4cker: 這個太邪門啦
※ 編輯: 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
推 stupid0319: i = i & 0x7FFFFFFF;  這樣可以嗎?
→ TobyH4cker: 不能，負數是以2的補數表示，把整數的MSB抹掉會變別的
推 stupid0319: i = i * ((((i>>31) ^ 1) << 1 )- 1); 這樣呢
→ bibo9901:   i = i * (( i>0        )   *2  - 1) 一樣啊
→ bibo9901: 你還假設int一定要32bit
推 stupid0319: 對吼,不知道有沒有CPU的指令集比較快
→ TobyH4cker: 就是abs 那樣已經是最精簡的了
※ 編輯: TobyH4cker (134.208.48.204), 04/07/2016 13:27:01
※ 編輯: TobyH4cker (134.208.48.204), 04/07/2016 13:58:49
推 tuyutd0505: 推 這篇一堆超狂方法XD
推 ronin728: 各種被玩弄的二進制數字與位元運算子XD
推 Frozenmouse: wwwww
推 wtchen: 以後管版務要來設一個腦筋急轉彎專區....
→ Schottky: 我怎覺得像獵奇專區...
※ 編輯: TobyH4cker (134.208.48.204), 04/08/2016 11:05:50
推 soheadsome: 算法心得 短碼寫手表示:
推 LiloHuang: v = (v ^ (v >> 31)) - (v >> 31); // int32_t v;
→ LiloHuang: 更多 bithacks 技巧以及解說 https://goo.gl/2m2qzH
→ BlazarArc:     ^看起來有點像在放阿哩固(誤
→ suhorng: cdq;xor;sub 這個好像是經典作法XD
推 Caesar08: 這篇不錯
> -------------------------------------------------------------------------- <

作者: ronin728 (浪人) 看板: C_and_CPP
標題: Re: [問題] 不用if-else, for, while, do-while取絕
時間: Thu Apr  7 22:22:58 2016

原文吃掉

--------------------------------------------------

作業系統：Windows 10
編譯器：MSVC(x86 32bits模式)


※ 超低可移植性注意 ※

這個程式在別人的 x86 PC 跑不起來的機率應該有 80%
如果你編譯了這個程式，執行的時候卻當掉，
這是很正常的 (茶

--------------------------------------------------

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#include "Windows.h"

unsigned char code[] = {
    0x8b, 0x44, 0x24, 0x04,
    0x99,
    0x31, 0xd0,
    0x29, 0xd0,
    0xc3
};

int main() {
    typedef int(*i_i_fptr)(int);
    int code_size = sizeof(code);
    int to_alloc_size = code_size + 20;
    void *f = VirtualAlloc(
        NULL, sizeof(to_alloc_size),
        MEM_COMMIT, PAGE_EXECUTE_READWRITE
    );
    memset(f, 0, to_alloc_size);
    memcpy(f, code, code_size);
    i_i_fptr abs = (i_i_fptr)f;
    printf("%d", abs(-500));
}


> -------------------------------------------------------------------------- <

作者: seanwu (sean) 看板: C_and_CPP
標題: Re: [問題] 不用if-else, for, while, do-while取絕
時間: Sun Apr 10 23:06:36 2016


原文恕刪，手癢也來一個:

#include <stdio.h>
int main() {
    int num;
    scanf("%d", &num);
    printf("%d\n", snprintf(0, 0, "%*c", num));
}

// snprintf 也是可以換成 printf，不過會被輸出噴個滿臉 


顯然這個依賴 printf 實作就是了

glibc-2.21 下數值要在 +/-2147483614 之間結果才會對 ...天知道它幹了什麼蠢事

倒是 VS2015 編出來的完全正確，有點意外

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1460300799.A.DFD.html
→ bibo9901: printf的實作也有if-else啊 XD
推 suhorng: It's seanwu!!!!! 給跪
推 L4ys: 野生的 sean !!
推 lsc36: 我媽問我為何跪著上ptt
→ wtchen: 剛上任版工跪迎seanwu大神...
推 oscar60111: 是seanwu大神<_ _>
> -------------------------------------------------------------------------- <

作者: ibmibmibm (BestSteve) 看板: C_and_CPP
標題: Re: [問題] 不用if-else, for, while, do-while取絕
時間: Mon Apr 11 23:41:37 2016

原文恕刪
用setjmp/longjmp來模擬while loop

這裡有測試結果
http://ideone.com/PetGBe


以下是程式碼

#include <stdio.h>
#include <setjmp.h>

int abs(int value) {
        jmp_buf buf;
        char buffer[16];
        snprintf(buffer, sizeof(buffer), "%d+", value);
        char *cursor = buffer;
        switch (setjmp(buf)) {
                case 0:
                        ++cursor;
                        longjmp(buf, *cursor);
                case '-':
                        *cursor = ' ';
                        ++cursor;
                        longjmp(buf, *cursor);
                case '+':
                        *cursor = '\0';
                        sscanf(buffer, "%d", &value);
                        return value;
                default:
                        ++cursor;
                        longjmp(buf, *cursor);
        }
}

int main(void) {
        int value;
        while (1 == scanf("%d", &value)) {
                printf("%d\n", abs(value));
        }
        return 0;
}