Đổi giá trị 2 biến không dùng biến trung gian

[hieubm]

Mình biết được một thủ thuật đổi giá trị 2 biến mà không dùng biến trung gian như sau :

int a,b;

a=a+b;
b=a-b;
a=a-b;

Mình thấy mọi người bảo là cách này gây tràn bộ nhớ nếu như a, b lớn, và không nên dùng cách này. Qua kiểm chứng thì mình thấy cách làm trên luôn đưa ra kết quả chính xác. Vậy nhận xét của mọi người là sai và vẫn cứ sử dụng cách này phải không ?

[Xcross87]

a = 99999999999999999999999
b = 9999999999999999999999999999999999999

Kiểu int.
Test là biết thế nào là buffer overflow ^^

Thưa anh, a và b mà anh đưa ra đã vượt quá giới hạn biến int rồi. (Posted by huynguyen)

[thanhlv]

chắc chắn nếu a,b lớn sẽ tràn bộ nhớ rồi(vì có xử dùng phép cộng 2 số cùng kiểu),nhận xét đó ko có gì là sai,bạn cứ thử cho giá trị của a,b gần đến giớ hạn của kiểu int xem hoặc tổng (a+b) vượt ra giới hạn của kiểu int,sẽ xảy ra lỗi ngay
tôi thì vẫn dùng biến trung gian để gán giá trị giữa các biến,vừa rõ ràng vừa đảm bảo ko xảy ra lỗi

[nhc1987]

Yeah, cách này thì thế nào hả mọi người :

void Swap(int &a, int &b)
{
          a ^= b ^= a ^= b;
}

[Kevin Hoang]

void Swap(int &a, int &b)
{
          a ^= b ^= a ^= b;
}

Cái này sử dụng toán tử ^ (XOR) để đổi giá trị 2 biến. Khá hay! Dr nghĩ nên áp dụng cách này hoặc cách dùng biến temp thì hơn.

[hieubm]

a = 99999999999999999999999
b = 9999999999999999999999999999999999999

Kiểu int.
Test là biết thế nào là buffer overflow ^^

Ông Pete này ăn nói..."ngầu" quá há. Thử hỏi ông làm cách gì để mà đổi chỗ 2 biến kiểu int này cơ chứ. Vốn 2 số đã tràn rồi, thì có đổi đàng trời. Ý của tui là 2 biến tuy lớn nhưng chưa tràn kiểu ( ví dụ 32000 và 20000 ấy cơ ( với sizeof(int) = 2 ) )

chắc chắn nếu a,b lớn sẽ tràn bộ nhớ rồi(vì có xử dùng phép cộng 2 số cùng kiểu),nhận xét đó ko có gì là sai,bạn cứ thử cho giá trị của a,b gần đến giớ hạn của kiểu int xem hoặc tổng (a+b) vượt ra giới hạn của kiểu int,sẽ xảy ra lỗi ngay
tôi thì vẫn dùng biến trung gian để gán giá trị giữa các biến,vừa rõ ràng vừa đảm bảo ko xảy ra lỗi

Tất nhiên là mình thử với các số gần với giới hạn kiểu int rồi. Và tất nhiên là nó có tràn. Nhưng các bạn có biết nó tràn thế nào không ?

Giả sử trường hợp max int là 32767, mình có biến là x = 32767, nếu mình dùng phép x=x+1, lúc này x == -32768. Nếu mình cho x=x-1 thì x == 32767. Các bạn có thể tạm hiểu là nó tràn theo kiểu vòng tròn, chính vì vậy mà dù phép cộng có gây tràn đi nhưng phép trừ b=a-b vẫn cho ra kết quả mong muốn.

Yeah, cách này thì thế nào hả mọi người :

void Swap(int &a, int &b)
{
          a ^= b ^= a ^= b;
}

Cảm ơn bạn ! Mình cũng biết cách này rồi. Nhưng ở đây mình muốn nói rằng việc hoán đổi số lớn theo phép cộng không hề xảy ra lỗi như mọi người vẫn thường nghĩ.

Mình nghĩ đây là một vấn đề hay. Hóa ra việc hoán đổi số lớn bị tràn số mà mọi người e ngại trước đây đều không đúng. Các bạn không tin thì cứ thử xem, qua nó có thể giúp các bạn hiểu về việc tràn số hơn.

[thanhlv]

chính vì vậy mà dù phép cộng có gây tràn đi nhưng phép trừ b=a-b vẫn cho ra kết quả mong muốn.

tôi ko hiểu ý này,nếu phép cộng đã sinh lỗi thì thủ tục bị dừng lại ngay,làm sao mà nó thực hiện tiếp được phép trừ phía dưới,hơn nữa trong 1 đoạn lệnh mà bạn ko khống chế được lỗi phát sinh thì tốt nhất là đừng dùng đoạn lệnh đó,tại sao cứ phải dùng cách phức tạp mà ko dùng những cách đơn giản và an toàn

[nhc1987]

Mình thì không thích tất cả các cách này. Nên code theo dạng biến temp để ko phụ thuộc kiểu dữ liệu:

        public static void Swap<T> (ref T x, ref T y)        {            T temp = x;            x = y;            y = temp;        }

[Kevin Hoang]

2 cách dùng sau đây:

a ^= b ^= a ^= b;

và a=a+b; b=a-b; a=a-b;

Có sự tương đồng với nhau.
Có ai vạch ra được sự tương đồng trong 2 cách này không?
Sự khác nhau giữa 2 cách trên là chỗ nào?
Trong 2 cách trên, theo bạn nên dùng cách nào?
Giải thích những câu trả lời của bạn?
(Loại trừ TQN và rongchaua vì Dr đoán là 2 người này biết khá rõ vấn đề này)

[huynguyen]

tôi ko hiểu ý này,nếu phép cộng đã sinh lỗi thì thủ tục bị dừng lại ngay,

Tràn số ko phải là lỗi nhé, nó sẽ bị xoay vòng số.
Ko tin cứ test thử đoạn code dưới đây:

#include<iostream> using namespace std;                 int main() {    int i = 2147483647;    ++i;    cout <<i <<endl;    system("pause");    return 0;}

Trên môi trường Win kiểu int là 4 bit nên max là 2147483647, bảo đảm nó xuất ra số -2147483648.

tại sao cứ phải dùng cách phức tạp mà ko dùng những cách đơn giản và an toàn

Suốt đời cứ đơn giản và an toàn thì giống con ếch ngồi đáy giếng
Nói như bạn thì công nghệ máy tính ko thể nào phát triển nổi vì ko suy nghĩ ra những thứ phức tạp thì làm sao có thể làm gọn nhẹ chương trình được.

a ^= b ^= a ^= b;

và a=a+b; b=a-b; a=a-b;

Viết như trên nhiều bạn sẽ khó hiểu, viết lại thế này cho dễ hiểu nhé:

a = a ^ b; 
b = b ^ a; 
a = a ^ b;

Bây giờ ta tạm thời chuyển sang học toán 1 chút về phép xor nhé:
trên mỗi cặp bit tương ứng nhau của hai toán hạng, toán tử XOR sẽ trả về 1 nếu chỉ có một trong hai bit là 1 (và bit còn lại là 0), ngược lại, XOR trả về bit 0. Ví dụ:

    0101
XOR 0011
---------
    0110

Đặt a = 0101, b = 0011
a = a ^ b = 0110
Lúc này a = 0110, b = 0011
b = b ^ a = 0101 = a
Lúc này a = 0110, b = 0101
a = a ^ b = 0011 = b
Xét về phép xử lý bằng thuật toán cộng trừ:

a=a+b; 
b=a-b; 
a=a-b;

Cho a = 5, b = 3
a = a + b = 8
Lúc này a = 8, b = 3
b = a - b = 5 = a
Lúc này a = 8, b = 5
a = a - b = 3 = b
Trên phép tính số thập phân thì kết quả của phép tính cộng a và b khi trừ ngược lại cho a thì ra b, trừ ngược lại cho b thì ra a.
Trên phép tính số nhị phân thì kết quả của phép xor a và b khi xor ngược lại cho a thì ra b và xor ngược lại cho b thì ra a.
Dùng phép xor lợi thế hơn nhiều vì CPU xử lý nhanh hơn.
Và tôi bảo đảm với các bạn rằng dùng thuật toán cộng trừ ko bao giờ sai cho dù tổng của nó bị vượt quá giới hạn. Bạn hãy thử chạy đoạn code dưới đây sẽ thấy rõ ràng:

#include<iostream> using namespace std;                 int main() {    int a = 2000000000;    int b = 147483650;    a += b;    b = a - b;    a -= b;    cout <<a <<endl <<b <<endl;    a ^= b;    b ^= a;    a ^= b;    cout <<a <<endl <<b <<endl;    system("pause");    return 0;}

Để chứng minh điều này tôi giả sử ta có kiểu dữ liệu rất nhỏ với các giá trị đi từ -64 đến 63 (rất nhỏ để các bạn dễ nhẩm)
Ta cho 2 số 50 và 40 hoán vị với nhau, tổng của 2 số này là 90 nhưng do kiểu dữ liệu của ta quá nhỏ nên nó sẽ bị xoay vòng.
90 - 63 = 27 (tự chứng minh )
-64 + 26 = -38 (cộng 27 là sai nhé, tự chứng minh nốt )
Như vậy a = a + b = -38
Bây giờ b = a - b = -38 - 40 = -78 (lại vượt quá giới hạn)
-78 - (-64) = -14
63 - 13 = 50 (ặc ặc ) (-(-14) là sai, -(-13) cũng sai)
Bây giờ a = a - b = -38 - 50 = -88 (quá rồi)
-88 - (-64) = -24
63 - 23 = 40 (ô là la)
Vì các kiểu dữ liệu số nguyên trong máy tính là bội số của kiểu dũ liệu mà ta chứng minh cho nên bài toán này đúng với mọi kiểu dữ liệu là số nguyên trong máy tính.
Ta đã chứng minh thuật toán cộng trừ để hoán vị 2 biến là đúng bất chấp tổng 2 số vượt quá giới hạn của kiểu dữ liệu.