Soru İmzasız tamsayı çıkarma tanımlı davranış mıdır?


Sonuç negatif olduğunda, aynı türden bir başka tamsayıdan bir işaretsiz tamsayı çıkarırken bir sorun olduğuna inanan birinden kodla karşılaştım. Yani bu gibi kodlar çoğu mimaride çalışsa bile yanlış olur.

unsigned int To, Tf;

To = getcounter();
while (1) {
    Tf = getcounter();
    if ((Tf-To) >= TIME_LIMIT) {
        break;
    } 
}

Bu, bulabildiğim C standardından sadece belli belirsiz bir alıntıdır.

İmzasız işlenenleri içeren bir hesaplama hiçbir zaman aşırı yüklenemez, çünkü   Sonuçta ortaya çıkan imzasız tam sayı ile temsil edilemez   tip modulo, en büyüğünden büyük olan sayıdır.   Sonuç türü tarafından temsil edilebilecek değer.

Sanırım bu alıntı, doğru işlenenin daha büyük olması durumunda modülasyonun kesikli sayılar bağlamında anlamlı olacak şekilde ayarlanması anlamına gelebileceğini varsayalım.

diğer bir deyişle

0x0000 - 0x0001 == 0x 1 0000 - 0x0001 == 0xFFFF

uygulamaya bağlı imzalı semantiği kullanmanın aksine:

0x0000 - 0x0001 == (imzasız) (0 + -1) == (0xFFFF, ancak 0xFFFE veya 0x8001)

Hangi veya hangi yorum doğrudur? Hiç tanımlanmış mı?


76
2017-08-28 13:59


Menşei


Standarttaki kelimelerin seçimi talihsizdir. “Asla taşamaz”, bunun bir hata durumu olmadığı anlamına gelir. Standarttaki terminolojiyi kullanarak “sarar” değerini taşmak yerine. - danorton


Cevaplar:


İmzasız bir türde negatif bir sayı üreten bir çıkarmanın sonucu iyi tanımlanmıştır:

  1. [...] İmzasız işlenenleri içeren bir hesaplama asla taşmayabilir,   Sonuçta ortaya çıkan işaretsiz tamsayı türüyle temsil edilemeyen bir sonuç olduğu için   modulo azaltılmış en büyük değerden daha büyük olan sayı   sonuç türü ile temsil edilir.   (ISO / IEC 9899: 1999 (E) §6.2.5 / 9)

Gördüğün gibi, (unsigned)0 - (unsigned)1 -1 modulo UINT_MAX + 1 veya başka bir deyişle UINT_MAX.

"İmzasız işlenenleri içeren bir hesaplama hiçbir zaman taşmayabilir" demesine rağmen, bunun yalnızca üst sınırı aşmak için geçerli olduğuna inanmanıza neden olabileceğini unutmayın. motivasyon cümlenin gerçek bağlama kısmı için: "sonuçta imzasız tamsayı türüyle temsil edilemeyen bir sonuçtur modulo azaltılmış en büyük değerden daha büyük olan sayı Sonuç türü ile temsil edilir. "Bu ifade, türün üst sınırının taşmasıyla sınırlı değildir ve temsil edilmek için çok düşük değerlere eşit olarak uygulanır.


84
2017-08-28 14:06



Teşekkür ederim! Şimdi eksik olduğum yorumu gördüm. Bence daha net bir ifadeyi seçebilirlerdi. - jbcreix
Şimdi kendimi çok daha iyi hissediyorum, eğer imzasız bir ekleme sıfıra yaklaşırsa ve kargaşaya sebep olursa, bunun sebebi şudur: uint her zaman matematiksel temsili amaçlanmıştır halka tamsayıların 0 vasitasiyla UINT_MAXek ve çarpma modulo işlemleri ile UINT_MAX+1ve bir taşma yüzünden değil. Ancak, eğer yüzükler böyle temel bir veri türü ise, dil diğer boyutlardaki halkalar için daha genel bir destek sunmuyor. - Theodore Murdock
@TheodoreMurdock Bence bu sorunun cevabı basit. Anlayabildiğim kadarıyla, bunun bir yüzük olması bir sonuç değil, bir sebeptir. Gerçek gereksinim, imzasız türlerin, değer temsiline katılan tüm bitlerine sahip olması gerektiğidir. Halka benzeri davranış, doğal olarak bundan akar. Bu tür davranışları diğer türlerden istiyorsanız, aritmetiğinizi yapın ve ardından gerekli modülü uygulayın; Bu temel operatörleri kullanır. - underscore_d
@underscore_d Tabii ki ... tasarım kararını neden verdikleri belli. Bu tasarım tercihi, programcıların aşırı ve aşağıdan kaçınmak zorunda kalmamaları anlamına geldiği gibi, kabaca "veri türü bir zil olarak belirtildiği için fazla / alt akış yoktur" şeklindeki verileri yazdıkları için çok eğlendirici. -flow veya programlarının muhteşem bir şekilde başarısız olması. - Theodore Murdock


İle çalışırken imzasız tipleri, Modüler aritmetik (Ayrıca şöyle bilinir "etrafına sarmak" davranış) yer almaktadır. Bunu anlamak için Modüler aritmetik, sadece şu saatlere bakın:

enter image description here 

9 + 4 = 1 (13 mod 12), diğer yöne öyle: 1 - 4 = 9 (-3 mod 12). İmzasız türlerle çalışırken aynı prensip uygulanır. Eğer sonuç türü olduğu unsignedsonra modüler aritmetik gerçekleşir.


Şimdi sonucu aşağıdaki gibi saklayan aşağıdaki işlemlere bakın. unsigned int:

unsigned int five = 5, seven = 7;
unsigned int a = five - seven;      // a = (-2 % 2^32) = 4294967294 

int one = 1, six = 6;
unsigned int b = one - six;         // b = (-5 % 2^32) = 4294967291

Sonuçların ne olduğundan emin olmak istediğinizde signedsonra da signeddeğişken veya signed. Sayılar arasındaki farkı almak ve modüler aritmetiğin uygulanmayacağından emin olmak istediğinizde, kullanmayı düşünmelisiniz. abs() tanımlanan işlev stdlib.h:

int c = five - seven;       // c = -2
int d = abs(five - seven);  // d =  2

Özellikle yazım koşulları sırasında, çok dikkatli olun çünkü:

if (abs(five - seven) < seven)  // = if (2 < 7)
    // ...

if (five - seven < -1)          // = if (-2 < -1)
    // ...

if (one - six < 1)              // = if (-5 < 1)
    // ...

if ((int)(five - seven) < 1)    // = if (-2 < 1)
    // ...

fakat

if (five - seven < 1)   // = if ((unsigned int)-2 < 1) = if (4294967294 < 1)
    // ...

if (one - six < five)   // = if ((unsigned int)-5 < 5) = if (4294967291 < 5)
    // ...

96
2018-02-22 17:56



Gerçi saatlerle güzel olanı kanıt Bu doğru cevabı yapardı. Sorunun önermesi, tüm bunların doğru olabileceği iddiasını içerir. - Lightness Races in Orbit
@LightnessRacesinOrbit: Teşekkürler. Onu yazdım çünkü birisinin bunu çok yararlı bulabileceğini düşünüyorum. Katılıyorum, bu tam bir cevap değil. - LihO
Çizgi int d = abs(five - seven); iyi değil. İlk five - seven hesaplanır: promosyon, işlenen türlerini unsigned int, sonuç modulo hesaplanır (UINT_MAX+1)ve değerlendirir UINT_MAX-1. Sonra bu değer gerçek parametre absBu kötü bir haber. abs(int) aralıkta olmadığı için argümanı geçmeyen tanımsız davranışlara neden olur ve abs(long long) büyük olasılıkla değeri tutabilir, ancak dönüş değeri zorlandığı zaman tanımlanmamış davranış oluşur int başlatmak d. - Ben Voigt
@LihO: C ++ içindeki içeriğe duyarlı olan ve sonucunun nasıl kullanıldığına bağlı olarak farklı davranan tek operatör, özel bir dönüşüm operatörüdür operator T(). Tartıştığımız iki ifadedeki ekleme, türünde gerçekleştirilir. unsigned int, işlenen türlerine göre. Eklemenin sonucu unsigned int. Daha sonra bu sonuç örtük olarak bağlamda gerekli olan türe dönüştürülür, çünkü değer yeni türde gösterilemediği için başarısız olur. - Ben Voigt
@LihO: Düşünmeye yardımcı olabilir double x = 2/3; vs double y = 2.0/3; - Ben Voigt


Eh, ilk yorum doğrudur. Ancak, bu bağlamda "imzalı semantik" hakkındaki mantığınız yanlıştır.

Yine, ilk yorumunuz doğrudur. İmzasız aritmetik, modulo aritmetik kurallarını takip eder. 0x0000 - 0x0001 değerlendirir 0xFFFF 32 bit imzasız türler için.

Bununla birlikte, aynı sonucu elde etmek için ikinci yorumlama (“imzalı semantik” esasına dayanan) da gereklidir. Yani değerlendirseniz bile 0 - 1 imzalı alanda ve elde -1 ara sonuç olarak, bu -1 üretmek için hala gerekli 0xFFFF daha sonra imzasız türüne dönüştürülür. Bazı platformlar, imzalı tamsayılar için (1'in tamamlayıcısı, imzalı büyüklük) egzotik bir temsili kullansalar bile, bu platform, imzalı tamsayı değerlerini imzasız olanlara dönüştürürken yine de modulo aritmetiği kurallarını uygulamak zorundadır.

Örneğin, bu değerlendirme

signed int a = 0, b = 1;
unsigned int c = a - b;

hala üretilmesi garantilidir UINT_MAX içinde cPlatform, imzalı tamsayılar için egzotik bir gösterim kullanıyor olsa bile.


3
2018-02-22 18:22



Sanırım 32 bit değil, 16 bit işaretsiz türleri kastediyorsunuz. - xioxox


İmzasız sayı tipi ile unsigned int veya tür dönüşümlerin yokluğunda daha büyük, a-b eklendiğinde imzalanmamış imzalı numarayı vermek olarak tanımlanır. b, verecek a. Negatif bir sayının imzasız değere dönüştürülmesi, işaretin tersine çevrilmiş orijinal numarasına eklendiğinde sıfır kazandıracağı sayı olarak tanımlanır (bu nedenle, 5'e dönüştürüldüğünde, işaretsiz-5'e dönüştürüldüğünde, sıfır olarak üretilecek bir değer elde edilir) .

İmzasız sayıların daha küçük olduğunu unutmayın. unsigned int türüne yükseltilebilir int çıkarma işleminden önce, davranış a-b büyüklüğüne bağlı olacak int.


2
2018-01-09 17:22