Tamsayılarda taşma (overflow)

Giriş
Taşma (Overflow) iki durumda ortaya çıkar.

• Bir tamsayıya ekle çıkartma işlemi uygulanır ve alabileceği üst/alt sınır aşılırsa.
• Bir tip başka bir tipe çevirilirse. Örneğin 8 byte'lık bir double, iki byte'lık short'a çevirilirse

1. Taşma Olacağını Biliyorsak

Eğer taşma olacağını biliyorsak formülü genellikle ikiye ayırmak yeterli.

Örnek

2^70 mod 10^9 + 1'i hesaplamamız istendi.2^70 64 bit'e sığmaz ancak 2^70 = 2^35 x 2^35 şeklinde yazılabilir. Şöyle yaparız

2⁷⁰ (mod 10⁹ + 7)

= 2³⁵ · 2³⁵ (mod 10⁹ + 7)

= (2³⁵ mod 10⁹ + 7) · (2³⁵ mod 10⁹ + 7) mod 10⁹ + 7

= (34359738368 mod 10⁹ + 7) · (34359738368 mod 10⁹ + 7) mod 10⁹ + 7

= (359738130 · 359738130) mod 10⁹ + 7

= 129411522175896900 mod 10⁹ + 7

= 270016253

2. Taşmayı Tespit Etmezsek

2.1 Unsigned Değişkenler
Unsigned değişkenlerde taşma genelde probleme sebep olmuyor. Özellikle toplama ve çıkartmada taşma sıkça kullanılan genel kabul gören bir yöntem.

2.2 Signed Değişkenler
C ve C++ standardında signed integer taşması için şöyle yazıyor. Standarda göre donanım 2's complement olmak zorunda değil. Hiçbir kısıtlama konulmamış. Dolayısıyla portable davranış garanti edilmiyor.

If during the evaluation of an expression, the result is not mathematically defined or not in the range of representable values for its type, the behavior is undefined.

Aslında signed değişkenlerin taşması, herhangi bir dilde de tanımsız davranışa (undefined behavior) sebep olabilir. Bazı durumlarda tuhaf işler olabiliyor ve beklenenin aksine sonuçlar elde edebiliyoruz.
Örnek
Int32.MaxValue * Int32.MaxValue işleminin sonucu 1 çıkabiliyor.

            0x ffff ffff
*           0x ffff ffff
= 0x ffff fffe 0000 0001

Örnek
Elimizde şöyle bir kod olsun.

byte b = (byte)400; // Stored as -112

400 ikilik olarak şöyledir.

0000 0001 1001 0000

Baştaki iki byte atılırsa şu kalır. Bu da 112'dir.

1001 0000

3. Taşmayı Tespit Etmenin Yolları
C++ ile taşmayı tespit etmenin standart bir yolu yok. Ya derleyicinin sağladığı bazı uzantılar kullanılmalı ya da kendimiz kod yazmalıyız. int64 çarpmasında taşmayı tespit eden bir kod şöyle.

// Multiplies two 64-bit signed ints if possible.
// Returns 0 on success, and puts the product of x and y into the result.
// Returns 1 if there was an overflow.
int int64_mult(int64_t x, int64_t y, int64_t * result)
{
    *result = 0;
    if (x > 0 && y > 0 && x > INT64_MAX / y) return 1;
    if (x < 0 && y > 0 && x < INT64_MIN / y) return 1;
    if (x > 0 && y < 0 && y < INT64_MIN / x) return 1;
    if (x < 0 && y < 0 && x < INT64_MIN / y) return 1;
    *result = x * y;
    return 0;
}

Bir diğer basit yöntem ise eğer int kullanıyorsak aritmetiği int64 ile yaparız. Sonucun INT32_MAX ve INT32_MIN aralığında olup olmadığını kontrol ederek taşmayı tespit edebiliriz.
Java'da signed iki sayının toplamasında taşma şöyle bulunur.

/**
 * Add two long's with overflow detection (r = s + d)
 */
public static long add(final long s, final long d){
    final long r = s + d;
    if (((s & d & ~r) | (~s & ~d & r)) < 0)
        throw new RuntimeException("long overflow add(" + s + ", " + d + ")");
    return r;
}

C#
checked Anahtar Kelimesi yazısına taşıdım.