Taşmasız ortalama alma

[acehreli]

İki tane int değerin ortalamasını hesaplamak için (a+b)/2 yazmanın sakıncaları vardır. Eğer toplam, bir int'in alabileceği en yüksek değeri aşarsa, yani taşarsa, ortalama eksi bir değer olarak hesaplanır.

Örneğin int'in 32 bit olduğu bir ortamda, şu programın sonucu, 1.5 milyar olması gerekirken -647483648 çıkar:

#include <stdio.h>

int main()
{
    int a = 1400000000;
    int b = 1600000000;

    int ortalama = (a + b) / 2;

    printf("%d\n", ortalama);

    return 0;
}

Bunun önüne geçmek için ((unsigned int)a+b)/2) gibi yollar düşünülebilir. Bunlardan bir tanesiyle bugüne kadar karşılaşmamıştım:

int ortalama = (a & b) + ((a ^ b) >> 1);

O kod da iki sayının ortalamasını alır ama taşma sorunu yoktur! Çok ilginç...

Nasıl çalıştığını anlayabiliyor musunuz?

Ali

[e_koca]

(a & b) elde veren basamaklarin bir bit saga kaymis halini buluyo, (a ^ b) >> 1 ise elde vermeyen basamaklarin bir bit saga kaymisini buluyo. Yani ilk once ikiye bolup sonra toplamak gibi bisey(tam olarak matematiksel karsiligi olmasada) o zaman

int ortalama = (a / 2) + (b / 2) ifadesinde de tasma olmamasi lazim. a ve b Max tutsa bile yarilarinin toplami yine max olur, tasma olmaz. Sanki (a / 2) + (b / 2) isleminin bitsel islemlerle yapilmis hali.

[quasimodo]

Bu kisi bizim san diego'daki e_koca mi?

Ali

[acehreli]

(a & b) elde veren basamaklarin bir bit saga kaymis halini buluyo

& işleminde hiç sağa kaydırma yoktur ama. Örneğin 123 & 123 işleminin sonucu yine 123'tür.

(a ^ b) >> 1 ise elde vermeyen basamaklarin bir bit saga kaymisini buluyo

Elde vermeyen kısmını anlamıyorum. Çünkü sonucun bütün basamakları sağa kayıyor.

int ortalama = (a / 2) + (b / 2) ifadesinde de tasma olmamasi lazim.

Doğru. Onun sakıncası, tamsayı bölmedeki kırpılmanın iki kat olması. 3 ve 3'ün ortalamasını 2 olarak hesaplar.

(a / 2) + (b / 2) isleminin bitsel islemlerle yapilmis hali.

Sonuçta öyle oluyor ama nasıl çalıştığı bence daha ilginç.

Ali

[acehreli]

(a & b) elde veren basamaklarin bir bit saga kaymis halini buluyo, (a ^ b) >> 1 ise elde vermeyen basamaklarin bir bit saga kaymisini buluyo.

Tamam... Yüz yüze konuştuğum başka birisi daha aynı şeyi söyleyince anladım.

Yani a&b'nin "elde veren basamaklar" olmaları, ikisinde de 1 olanların elde verecekleri düşüncesinden geliyor.

Ben kendime başka türlü açıklamıştım: a&b, her ikisinde de bulunan parçaları seçer. a^b ise, yalnızca birinde bulunanların toplamlarını.

     (a + b) / 2

==>  ((ortak + a_özel) + (ortak + b_özel)) / 2

==>  ortak + (a_özel + b_özel) / 2

==> (a & b) + (a ^ b) / 2

Ali

[e_koca]

     (a + b) / 2

==>  ((ortak + a_özel) + (ortak + b_özel)) / 2

==>  ortak + (a_özel + b_özel) / 2

==> (a & b) + (a ^ b) / 2

Bu aciklama matematiksel olarak bir aciklama degil. & ve ^ simgelerinin ortak ve ozel isimleri yer degistirilmis hali. Asil onemli olan neden bunun yapildigi. Dediginiz gibi 1`ler ayni digitteyse bir sonraki basamaga elde verir ve kendi 0 olur. Fakat tasmanin onlenmesi icin toplamadan once saga kaydirilip 2 ye bolunurki buda (a & b) nin ta kendisi. (a ^ b) ise 0 + 1 = 1 ve kendi basamaginda kalir 2 ye bolmek icinde ((a ^ b) >> 1) yapilir. Bunlarin toplami ise ortalamayi vermis olur.


dobule ortalama = (double)a / 2 + double(b) / 2; seklide olsa bilgi kaybi olmuyo ama. Zaten ortamalayi tutan degiskenin double olmasi yaygin ve dogru kullanim degilmi ?

[acehreli]

Bu aciklama matematiksel olarak bir aciklama degil.

Benim hoşuma giden de zaten matematiksel olmamasıydı. & işlecinin "ikisinde de olanlar", ve ^ işlecinin "yalnızca birisinde olanlar" anlamlarının kullanılması çok hoşuma gitti. (Zaten yazmaya değer bulmazdım. )

dobule ortalama = (double)a / 2 + double(b) / 2; seklide olsa bilgi kaybi olmuyo ama. Zaten ortamalayi tutan degiskenin double olmasi yaygin ve dogru kullanim degilmi ?

Doğru tabii ama kesirli sayıların yavaşlığı bazı algoritmalarda önemli olabilir. Genel amaçlı kütüphaneler hızlı olmak için int kullanacaklardır ve kullanırlar. Bütün bu hikaye zaten bugün kullanımda olan ikili arama algoritmalarının hemen hemen hepsinin bozuk olduğunu okuduğum için ortaya çıktı.

Ali