C trả chậm chút đố

Question

/* 
* 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); 
} 

tôi đã cố gắng để giải quyết câu đố này nhưng

 

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

biên dịch với gcc (GCC) 4.1.2 20.080.704 (Red Hat 4.1.2-51)

Có gì sai với giải pháp này?

Answer 1

trình tốt cho tôi sử dụng 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 
} 

Answer 2

cách tiếp cận của bạn để làm cho số âm tròn về phía zero không hoạt động một cách chính xác trong trường hợp của các giá trị đầu vào mà chia đều bởi 4. 0x80000000 là một ví dụ như vậy , nhưng có lẽ dễ dàng hơn để xem vấn đề nếu bạn thử với một giá trị nhỏ.

Ví dụ: ezThreeFourths (-8) = -5 [nên -6]

Answer 3

Dưới đây là những gì tôi đã làm:

#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; 
} 

Output:

 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 

Lý do tại sao tôi đã không sử dụng đúng ca trên số nguyên âm là đơn giản. Kết quả của những thay đổi này là xác định thực hiện (theo tiêu chuẩn C) và không được đảm bảo giống như sự thay đổi đúng với phần mở rộng dấu hiệu mà chúng ta có thể mong đợi vì nó là triển khai phổ biến nhất.

tôi đã viết (UINT_MAX - x3 + 1) thay vì chỉ đơn giản là -x3 bởi vì nó có thể gây ra một lỗi tràn bộ ký (khi = INT_MIN đó là một sức mạnh trừ 2), trong đó đã không xác định hành vi (theo tiêu chuẩn C, một lần nữa). Và ngay cả khi hành vi không xác định này được biết là vô hại, sự phủ định đơn giản vẫn có thể thất bại trong việc tạo ra một số dương (vì sự không đối xứng trong biểu diễn bổ sung của các số nguyên đã ký).

x + x + x vẫn có thể tạo tràn đăng nhập giống như x * 3 có thể. Vì vậy, đây là hành vi không xác định tương tự.

Btw, vì các luồng tràn đã ký kết quả trong UB, nó thậm chí không được yêu cầu một cách hợp pháp từ bạn để đạt được chúng, hãy để một mình có những kỳ vọng cụ thể về kết quả khi UB xảy ra.

Answer 4

int ezThreeFourths(int x) { 


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


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

} 

Làm việc với số không âm. Ngoài ra, bạn không nên nói dối về code "you" wrote. Xem xét mã chính xác được viết trong "2008-01-26"