Soru Neden (a% 256) (a & 0xFF) değerinden farklı?


Bunu yaparken her zaman üstlendim (a % 256) Optimizer doğal olarak verimli bir şekilde bitli bir işlem kullanırdı, sanki yazmışım gibi (a & 0xFF).

Derleyici explorer gcc-6.2 (-O3) üzerinde test ederken:

// Type your code here, or load an example.
int mod(int num) {
    return num % 256;
}

mod(int):
    mov     edx, edi
    sar     edx, 31
    shr     edx, 24
    lea     eax, [rdi+rdx]
    movzx   eax, al
    sub     eax, edx
    ret

Ve diğer kodu denerken:

// Type your code here, or load an example.
int mod(int num) {
    return num & 0xFF;
}

mod(int):
    movzx   eax, dil
    ret

Tamamen bir şeyi özlüyorum gibi görünüyor. Herhangi bir fikir?


138
2017-11-08 09:29


Menşei


0xFF 255 değil 256'dır. - Rishikesh Raje
@RishikeshRaje: Öyleyse? % değil & Ya. - usr2564301
@RishikeshRaje: Eminim ki OP bunun farkındadır. Farklı operasyonlarla kullanılıyorlar. - Cheers and hth. - Alf
İlgilenmiyorum, daha iyi sonuçlar alırsanız num olduğu unsigned? - Bathsheba
@RishikeshRaje Bitwise ve 0xFF, imzasız tamsayılar için modulo 2 ^ 8'e eşdeğerdir. - 2501


Cevaplar:


Aynı şey değil. Deneyin num = -79ve her iki işlemden farklı sonuçlar elde edersiniz. (-79) % 256 = -79, süre (-79) & 0xff bazı pozitif sayıdır.

kullanma unsigned int, işlemler aynıdır ve kod muhtemelen aynı olacaktır.

ps Birisi yorum yaptı

Aynı olmamalılar, a % b olarak tanımlanır a - b * floor (a / b).

C, C ++, Objective-C'de (yani, söz konusu kodun derleneceği tüm diller) nasıl tanımlandığı değil.


226
2017-11-08 09:33



Yorumlar uzun tartışma için değil; bu konuşma oldu sohbete taşındı. - Martijn Pieters♦


Kısa cevap

-1 % 256 verim -1 ve yok 255 hangisi -1 & 0xFF. Bu nedenle, optimizasyon yanlış olur.

Uzun cevap

C ++ bu sözleşmeyi (a/b)*b + a%b == aoldukça doğal görünüyor. a/b her zaman kesirli kısım olmadan aritmetik sonucu döndürür (0'a doğru kesilir). Sonuç olarak, a%b aynı işarete sahip a veya 0'dır.

Bölme -1/256 verim 0 ve dolayısıyla -1%256 olmalıdır -1 Yukarıdaki koşulu yerine getirmek için ((-1%256)*256 + -1%256 == -1). Bu açıkça farklıdır -1&0xFF hangisi 0xFF. Bu nedenle, derleyici istediğiniz şekilde optimize edemez.

İlgili bölüm C ++ standardı [expr.mul §4] N4606 itibarıyla devletler:

İntegral işlenenler için / operatör, herhangi bir kesirli kısım atılmış olan cebirsel katsayısını verir; eğer bölüm a/b sonucun türünde temsil edilebilir (a/b)*b + a%b eşittir a [...].

Optimizasyonu etkinleştirme

Ancak, kullanma unsigned türleri, optimizasyon tamamen doğru olurduYukarıdaki kongreyi yerine getirmek:

unsigned(-1)%256 == 0xFF

Ayrıca bakınız bu.

Diğer diller

Bu, bakabileceğin farklı programlama dilleri arasında çok farklı ele alınır. Vikipedi.


53
2017-11-08 15:41





C ++ 11'den beri num % 256 eğer pozitif değilse num negatiftir.

Yani bit kalıbı sisteminizde imzalı tiplerin uygulanmasına bağlı olacaktır: negatif bir ilk argüman için sonuç en az anlamlı 8 bitin çıkarılması değildir.

Eğer farklı bir konu olurdu num senin durumunda unsigned: bugünlerde neredeyse beklemek alıntı yaptığınız optimizasyonu yapmak için bir derleyici.


50
2017-11-08 09:30



Neredeyse ama pek de değil. Eğer num o zaman negatif num % 256 sıfır veya negatiftir (a.k.a. pozitif olmayan). - Nayuki
Hangi IMO, standartta bir hatadır: matematiksel olarak modulo işlemi, bu durumda 256, bölenin işaretini almalıdır. Bunu neden dikkate aldığınızı anlamak için (-250+256)%256==6, fakat (-250%256)+(256%256) standarda göre "pozitif olmayan" olmalı ve bu nedenle 6. Böyle bir ilişkiyi gerçek yaşam yan etkileri vardır: örneğin tamsayı koordinatlarındaki "yakınlaştırma" işleminin hesaplanması sırasında, görüntüyü tüm koordinatların negatif olmayan şekilde kaydırması gerekir. - Michael
@Michael Modulus, ilaca verilen matematik tanımını takip etseniz bile, eklemeden önce hiçbir zaman dağıtılmamıştır ("buradaki özellik için" ilişkilendirici "yanlış addır!). Örneğin, (128+128)%256==0 fakat (128%256)+(128%256)==256. Belki de, belirtilen davranışa karşı iyi bir itiraz var, ama bana söylediğin şeyin açık değil. - Daniel Wagner
@DanielWagner, haklısınız, elbette, "çağrışımcı" ile yanlış konuştum. Bununla birlikte, eğer kişi bölenin işaretini tutarsa ​​ve her şeyi modüler aritmetik olarak hesaplarsa, dağıtım özelliği tutulur; senin örneğinde olurdu 256==0. Anahtar tam olarak sahip olmaktır N modulo'daki olası değerler N sadece sonuçların menzil içinde olması durumunda mümkün olan aritmetik 0,...,(N-1), değil -(N-1),...,(N-1). - Michael
@Michael:% hariç, bir modulo operatör değil, bir geri kalan kısım Şebeke. - Joren


Derleyicinin akıl yürütmesine telepatik anlayışım yok, ama % Olumsuz değerlerle (ve sıfıra doğru bölüm sıfırları) uğraşmanın gerekliliği vardır. & Sonuç her zaman düşük 8 bittir.

sar talimat, işaret bit değeri ile boş bitleri dolduran, "vardiya aritmetik doğru" gibi geliyor.


11
2017-11-08 09:33



Evet, SAR, aritmetik doğrudur. - v7d8dpo4


Matematiksel olarak, modulo aşağıdaki gibi tanımlanmıştır:

% b = a - b * kat (a / b)

Buradaki iş senin için onu temizlemeli. Tamsayılar için katmanı ortadan kaldırabiliriz çünkü tamsayı bölmesi zemine eşdeğerdir (a / b). Ancak, derleyici önerdiğiniz gibi genel bir hile kullanacak olsaydı, hepsi ve hepsi için çalışması gerekirdi. Ne yazık ki, bu durum böyle değil. Matematiksel olarak, numaranız imzasız tamsayılar için% 100 doğrudur (tamsayıların kesildiği bir cevap durumu görüyorum ama bunu onaylayabilirim veya reddedebilirim -a% b pozitif olmalıdır). Ancak, bu hile tüm b için yapabilir misin? Muhtemelen değil. Bu yüzden derleyici bunu yapmaz. Sonuçta, eğer modulo bir bitsel işlem olarak kolayca yazılırsa, o zaman ekleme ve diğer işlemler gibi bir modulo devre eklerdik.


0
2017-11-09 15:58



Sanırım "zemin" ile "zemin" karıştırıyorsun. Erken bilgisayarlar, kısmi bölünme kullandılar çünkü her şeyin düzgün bir şekilde dağıldığı durumlarda bile, taban döşemesinden daha kolay hesaplanırdı. Kesilmiş bölümün katlanmış bölümden daha faydalı olabileceği çok az sayıda vaka gördüm, ancak birçok dil FORTRAN'ın kesilmiş bölünmeyi kullanma yolunu takip ediyor. - supercat
@supercat Matematiksel konuşma, kat olduğu kısaltırız. İkisi de aynı etkiye sahiptir. Bir bilgisayarda aynı şekilde uygulanamayabilirler, ama aynı şeyi yaparlar. - The Great Duck
@TheGreatDuck: Negatif sayılar için aynı değiller. Tabanı -2.3 olduğu -3, eğer kısalırsan -2.3 aldığınız bir tam sayıya -2. Görmek en.wikipedia.org/wiki/Truncation. "negatif sayılar için kesilme, zemin işleviyle aynı yönde dönmez". Ve davranışları % negatif sayılar için OP'nin açıklanan davranışı görmesinin nedeni tam olarak budur. - Mark Dickinson
@MarkDickinson C ++ 'daki modulo'nun pozitif bölenler için pozitif değerler verdiğine eminim, ama tartışmayacağım. - The Great Duck
@TheGreatDuck - örneğe bakın: cpp.sh/3g7h  (C ++ 98'in, iki olası varyasyondan hangisinin kullanıldığını tanımlamadığını, ancak daha yeni standartların yapıldığını not edin, yani mümkün geçmişte C ++ uygulamasının farklı bir şekilde kullandığını gördünüz ...) - Periata Breatta