C位操作的難題

/* 
* ezThreeFourths - multiplies by 3/4 rounding toward 0, 
* Should exactly duplicate effect of C expression (x*3/4), 
* including overflow behavior. 
* Examples: ezThreeFourths(11) = 8 
*    ezThreeFourths(-9) = -6 
*    ezThreeFourths(1073741824) = -268435456 (overflow) 
* Legal ops: ! ~ &^| + << >> 
* Max ops: 12 
* Rating: 3 
*/ 

int ezThreeFourths(int x) { 
    int z = x+x+x; 
    int sign_z = z>>31; 
    return ((z>>2)&(~sign_z)) + (((z>>2)+1)&sign_z); 
}

我試圖解決這個難題，但C位操作的難題

 

ERROR: Test ezThreeFourths(-2147483648[0x80000000]) failed... 
...Gives -536870911[0xe0000001]. Should be -536870912[0xe0000000]

與海灣合作委員會（GCC）編譯4.1.2 20080704（紅帽4.1.2-51）

這有什麼錯此解決方案？

來源

2012-02-08 user1114371

嗯......我跑這個代碼在我的電腦測試，我不得不說，這似乎是工作的測試用例，你給的例子這裏。我甚至讓你使用的是哪個編譯器2147483647 – Lefteris 2012-02-08 02:58:26

正確的結果呢？ – 2012-02-08 03:02:41

你是否分解了所有中間值？ – EboMike 2012-02-08 03:04:35

工作正常，我使用Embarcadero的C++ 6.43：

// x = 2147483647 
int ezThreeFourths(int x) 
{ 
    int z = x+x+x; 
    // z = 2147483645 (6442450941[0x17FFFFFFD] truncated to 32-bits!) 

    int sign_z = z>>31; 
    // sign_z = (2147483645 >> 31) = 0 

    return ((z>>2)&(~sign_z)) + (((z>>2)+1)&sign_z); 
    // = ((2147483645 >> 2) & (~0)) + (((2147483645 >> 2) + 1) & 0) 
    // = (536870911 & 0xFFFFFFFF) + ((536870911+1) & 0) 
    // = (536870911 & 0xFFFFFFFF) + (536870912 & 0) 
    // = (536870911 & 0xFFFFFFFF) + 0 
    // = (536870911 & 0xFFFFFFFF) 
    // = 536870911 
}

來源

2012-02-08 03:05:39

您製作負數向零舍入不通過4.爲0x80000000整除的輸入值的情況下正常工作的方法是這樣的一個例子，但如果您嘗試使用較小的值，則可能更容易看到問題。

例如：ezThreeFourths（-8）= -5 [應該是-6]

來源

2012-02-08 05:58:05

這裏就是我所做的：

#include <stdio.h> 
#include <limits.h> 

int ThreeFourths(int x) 
{ 
    int x3 = x + x + x; 
    return (x3 >= 0) ? (x3 >> 2) : -(int)((UINT_MAX - x3 + 1) >> 2); 
} 

int testData[] = 
{ 
    0, 
    1, 
    -1, 
    2, 
    -2, 
    3, 
    -3, 
    4, 
    -4, 
    5, 
    -5, 
    -9, 
    11, 
    INT_MAX/2 + 1, 
    INT_MIN 
}; 

int main(void) 
{ 
    int i; 

    for (i = 0; i < sizeof(testData)/sizeof(testData[0]); i++) 
    { 
    printf("  %d * 3/4 = %d\n", 
      testData[i], testData[i] * 3/4); 
    printf("ThreeFourths(%d) = %d\n", 
      testData[i], ThreeFourths(testData[i])); 
    } 
    return 0; 
}

輸出：

 0 * 3/4 = 0 
ThreeFourths(0) = 0 
     1 * 3/4 = 0 
ThreeFourths(1) = 0 
     -1 * 3/4 = 0 
ThreeFourths(-1) = 0 
     2 * 3/4 = 1 
ThreeFourths(2) = 1 
     -2 * 3/4 = -1 
ThreeFourths(-2) = -1 
     3 * 3/4 = 2 
ThreeFourths(3) = 2 
     -3 * 3/4 = -2 
ThreeFourths(-3) = -2 
     4 * 3/4 = 3 
ThreeFourths(4) = 3 
     -4 * 3/4 = -3 
ThreeFourths(-4) = -3 
     5 * 3/4 = 3 
ThreeFourths(5) = 3 
     -5 * 3/4 = -3 
ThreeFourths(-5) = -3 
     -9 * 3/4 = -6 
ThreeFourths(-9) = -6 
     11 * 3/4 = 8 
ThreeFourths(11) = 8 
     1073741824 * 3/4 = -268435456 
ThreeFourths(1073741824) = -268435456 
     -2147483648 * 3/4 = -536870912 
ThreeFourths(-2147483648) = -536870912

我之所以沒有在負整數上使用正確的轉換很簡單。這些變化的結果是實現定義（按C標準），並不能保證是一樣的帶符號擴展右移，我們可能因爲它是最常見的實現來期待。

我寫(UINT_MAX - x3 + 1)而不是簡單地-x3，因爲它會導致一個符號溢出時（ = INT_MIN是2負電源），這不確定的行爲（根據C標準，再次）。即使這種未定義的行爲被認爲是無害的，簡單的否定仍然不能產生一個正數（因爲在有符號整數的2的補碼錶示中的不對稱性）。

x + x + x仍能產生符號溢出就像x * 3即可。所以，這是未定義的行爲。

順便說一句，因爲簽署溢出導致UB，它甚至不應該從法律上你問來實現這些目標，更談不上有什麼時候發生UB結果具體的期望。

來源

2012-02-08 08:03:39

int ezThreeFourths(int x) { 


    int z = x+x+x; 
    int sign_z = z>>31; 


    return ((z>>2)&(~sign_z)) + (((z>>2)+1)&sign_z); 

}

適用於非負數。你也不應該說謊code "you" wrote。考慮到確切的代碼寫在「2008-01-26」

來源

2012-02-08 13:29:06

C位操作的難題

回答

相關問題