Bagaimana cara memeriksa apakah mengalikan dua angka di Java akan menyebabkan luapan?

101

Saya ingin menangani kasus khusus di mana mengalikan dua angka bersama-sama menyebabkan luapan. Kode tersebut terlihat seperti ini:

int a = 20;
long b = 30;

// if a or b are big enough, this result will silently overflow
long c = a * b;

Itu versi yang disederhanakan. Dalam program nyata adan bbersumber dari tempat lain saat runtime. Yang ingin saya capai adalah seperti ini:

long c;
if (a * b will overflow) {
    c = Long.MAX_VALUE;
} else {
    c = a * b;
}

Bagaimana saran Anda agar saya membuat kode terbaik ini?

Perbarui: adan bselalu tidak negatif dalam skenario saya.

Steve McLeod
sumber
6
Sayang sekali Java tidak menyediakan akses tidak langsung ke flag overflow CPU , seperti yang dilakukan di C # .
Drew Noakes

Jawaban:

92

Java 8 memiliki Math.multiplyExact, Math.addExactdll. Untuk int dan long. Ini membuang centang ArithmeticExceptionpada overflow.

bcoughlan.dll
sumber
59

Jika adan bkeduanya positif maka Anda dapat menggunakan:

if (a != 0 && b > Long.MAX_VALUE / a) {
    // Overflow
}

Jika Anda perlu berurusan dengan bilangan positif dan negatif maka ini lebih rumit:

long maximum = Long.signum(a) == Long.signum(b) ? Long.MAX_VALUE : Long.MIN_VALUE;

if (a != 0 && (b > 0 && b > maximum / a ||
               b < 0 && b < maximum / a))
{
    // Overflow
}

Berikut tabel kecil yang saya siapkan untuk memeriksanya, berpura-pura bahwa luapan terjadi pada -10 atau +10:

a =  5   b =  2     2 >  10 /  5
a =  2   b =  5     5 >  10 /  2
a = -5   b =  2     2 > -10 / -5
a = -2   b =  5     5 > -10 / -2
a =  5   b = -2    -2 < -10 /  5
a =  2   b = -5    -5 < -10 /  2
a = -5   b = -2    -2 <  10 / -5
a = -2   b = -5    -5 <  10 / -2
John Kugelman
sumber
Saya harus menyebutkan bahwa a dan b selalu tidak negatif dalam skenario saya, yang akan menyederhanakan pendekatan ini.
Steve McLeod
3
Saya pikir ini mungkin gagal dalam kasus: a = -1 dan b = 10. Maksimum / ekspresi menghasilkan Integer.MIN_VALUE dan mendeteksi overflow ketika tidak ada
Kyle
Ini sangat bagus. Bagi mereka yang bertanya-tanya, alasan mengapa ini berhasil adalah karena integer n, n > xsama dengan n > floor(x). Untuk pembagian bilangan bulat positif melakukan lantai implisit. (Untuk angka negatif malah dibulatkan)
Thomas Ahle
Untuk mengatasi masalah a = -1dan b = 10, lihat jawaban saya di bawah.
Jim Pivarski
17

Ada pustaka Java yang menyediakan operasi aritmatika yang aman, yang memeriksa long overflow / underflow. Misalnya, Guava's LongMath.checkedMultiply (long a, long b) mengembalikan produk dari adan b, asalkan tidak meluap, dan melempar ArithmeticExceptionjika a * bmeluap dalam longaritmatika bertanda tangan .

pemrogram ulang
sumber
4
Ini adalah jawaban terbaik - gunakan pustaka yang diterapkan oleh orang-orang yang sangat memahami aritmatika mesin di Java dan yang telah diuji oleh banyak orang. Jangan mencoba untuk menulis sendiri atau menggunakan kode setengah matang yang belum teruji yang diposting di jawaban lain!
Kaya
@Enerccio - Saya tidak mengerti komentar Anda. Apakah Anda mengatakan bahwa Jambu biji tidak akan berfungsi di semua sistem? Saya dapat meyakinkan Anda bahwa ini akan berfungsi di mana pun yang dijalankan Java. Apakah Anda mengatakan bahwa menggunakan kembali kode adalah ide yang buruk secara umum? Saya tidak setuju jika demikian.
Kaya
2
@ Kaya Saya katakan termasuk perpustakaan besar sehingga Anda dapat menggunakan satu fungsi adalah ide yang buruk.
Enerccio
Mengapa? Jika Anda menulis aplikasi besar, misalnya untuk bisnis, maka JAR tambahan pada classpath tidak akan membahayakan dan Guava memiliki banyak kode yang sangat berguna di dalamnya. Jauh lebih baik menggunakan kembali kode mereka yang telah diuji dengan cermat daripada mencoba menulis versi Anda sendiri dari yang sama (yang menurut saya adalah apa yang Anda rekomendasikan?). Jika Anda menulis di lingkungan di mana JAR tambahan akan sangat mahal (di mana? Java yang disematkan?) Maka mungkin Anda harus mengekstrak kelas ini dari Guava saja. Apakah menyalin jawaban yang belum teruji dari StackOverflow lebih baik daripada menyalin kode Guava yang telah diuji dengan cermat?
Kaya
Bukankah melempar pengecualian sedikit berlebihan untuk sesuatu yang bersyarat jika-maka dapat menangani?
pemenang
6

Anda dapat menggunakan java.math.BigInteger sebagai gantinya dan memeriksa ukuran hasilnya (belum menguji kode):

BigInteger bigC = BigInteger.valueOf(a) * multiply(BigInteger.valueOf(b));
if(bigC.compareTo(BigInteger.valueOf(Long.MAX_VALUE)) > 0) {
  c = Long.MAX_VALUE;
} else {
  c = bigC.longValue()
}
Ulf Lindback
sumber
7
saya menemukan solusi ini agak lambat
jangan sampai
Mungkin itu cara terbaik untuk melakukannya. Saya berasumsi ini adalah aplikasi numerik, itulah sebabnya saya tidak merekomendasikannya begitu saja, tetapi ini mungkin cara terbaik untuk menyelesaikan masalah ini.
Stefan Kendall
2
Saya tidak yakin Anda dapat menggunakan operator '>' dengan BigInteger. metode bandingkanTo harus digunakan.
Pierre
diubah menjadi CompareTo, dan kecepatan mungkin penting atau mungkin tidak, tergantung pada keadaan di mana kode akan digunakan.
Ulf Lindback
5

Gunakan logaritma untuk memeriksa ukuran hasil.

Tanda Kinerja Tinggi
sumber
maksud Anda: ceil(log(a)) + ceil(log(b)) > log(Long.MAX)?
Thomas Jung
1
Saya memeriksanya. Untuk nilai kecil, ini 20% lebih cepat dari BigInteger dan untuk nilai yang mendekati MAX hampir sama (5% lebih cepat). Kode Yossarian adalah yang tercepat (95% & 75% lebih cepat dari BigInteger).
Thomas Jung
Saya agak curiga bahwa ini mungkin gagal dalam beberapa kasus.
Tom Hawtin - tackline
Ingat log integer secara efektif hanya menghitung jumlah nol di depan, dan Anda dapat mengoptimalkan beberapa kasus umum (misalnya jika ((a | b) & 0xffffffff00000000L) == 0) Anda tahu Anda aman). Di sisi lain, kecuali Anda bisa mendapatkan optimasi Anda turun ke siklus jam 30/40-ish untuk kasus yang paling umum, metode John Kugelman mungkin akan bekerja lebih baik (pembagian integer c. 2 bits / clock cycle seingat saya).
Neil Coffey
PS Sorr, saya pikir saya perlu sedikit tambahan di topeng AND (0xffffffff80000000L) - ini agak terlambat, tetapi Anda mendapatkan ide ...
Neil Coffey
4

Apakah Java memiliki sesuatu seperti int.MaxValue? Jika ya, cobalah

if (b != 0 && Math.abs(a) > Math.abs(Long.MAX_VALUE / b))
{
 // it will overflow
}

edit: terlihat Long.MAX_VALUE yang dimaksud

nothrow
sumber
Saya tidak memberi suara negatif tetapi Math.Abs(a)tidak berfungsi jika aada Long.MIN_VALUE.
John Kugelman
@ John - a dan b> 0. Menurut saya pendekatan Yossarian (b! = 0 && a> Long.MAX_VALUE / b) adalah yang terbaik.
Thomas Jung
@ Thomas, a dan b adalah> = 0, yaitu non-negatif.
Steve McLeod
2
Benar, tapi dalam hal itu tidak perlu Abs. Jika angka negatif diperbolehkan maka ini gagal untuk setidaknya satu kasus tepi. Itu saja yang saya katakan, hanya bersikap rewel.
John Kugelman
di Jawa Anda harus menggunakan Math.abs, bukan Math.Abs ​​(C # guy?)
dfa
4

Inilah cara paling sederhana yang dapat saya pikirkan

int a = 20;
long b = 30;
long c = a * b;

if(c / b == a) {
   // Everything fine.....no overflow
} else {
   // Overflow case, because in case of overflow "c/b" can't equal "a"
}
Naren
sumber
3

Dicuri dari jruby

    long result = a * b;
    if (a != 0 && result / a != b) {
       // overflow
    }

UPDATE: Kode ini pendek dan berfungsi dengan baik; Namun, gagal untuk a = -1, b = Long.MIN_VALUE.

Satu peningkatan yang mungkin:

long result = a * b;
if( (Math.signum(a) * Math.signum(b) != Math.signum(result)) || 
    (a != 0L && result / a != b)) {
    // overflow
}

Perhatikan bahwa ini akan menangkap beberapa luapan tanpa pembagian apa pun.

rogerdpack
sumber
Anda dapat menggunakan Long.signum daripada Math.signum
aditsu berhenti karena SE EVIL
3

Seperti yang telah ditunjukkan, Java 8 memiliki metode Math.xxxExact yang memunculkan pengecualian saat overflow.

Jika Anda tidak menggunakan Java 8 untuk proyek Anda, Anda masih dapat "meminjam" implementasinya yang cukup ringkas.

Berikut adalah beberapa link ke implementasi ini dalam repositori kode sumber JDK, tidak ada jaminan apakah ini akan tetap valid, tetapi bagaimanapun juga Anda harus dapat mendownload sumber JDK dan melihat bagaimana mereka melakukan keajaibannya di dalam java.lang.Mathkelas.

Math.multiplyExact(long, long) http://hg.openjdk.java.net/jdk/jdk11/file/1ddf9a99e4ad/src/java.base/share/classes/java/lang/Math.java#l925

Math.addExact(long, long) http://hg.openjdk.java.net/jdk/jdk11/file/1ddf9a99e4ad/src/java.base/share/classes/java/lang/Math.java#l830

dll, dll.

DIPERBARUI: mengalihkan tautan tidak valid ke situs web pihak ketiga ke tautan ke repositori Mercurial dari Open JDK.

StFS
sumber
2

Saya tidak yakin mengapa tidak ada yang melihat solusi seperti:

if (Long.MAX_VALUE/a > b) {
     // overflows
} 

Pilih a menjadi lebih besar dari dua angka.

fastcodejava.dll
sumber
2
Saya tidak berpikir itu penting apakah alebih besar atau lebih kecil?
Thomas Ahle
2

Saya ingin mengembangkan jawaban John Kugelman tanpa menggantinya dengan mengeditnya secara langsung. Ini bekerja untuk kasus uji ( MIN_VALUE = -10, MAX_VALUE = 10) karena kesimetrisannya MIN_VALUE == -MAX_VALUE, yang bukan kasus untuk bilangan bulat komplemen dua. Sebenarnya MIN_VALUE == -MAX_VALUE - 1,.

scala> (java.lang.Integer.MIN_VALUE, java.lang.Integer.MAX_VALUE)
res0: (Int, Int) = (-2147483648,2147483647)

scala> (java.lang.Long.MIN_VALUE, java.lang.Long.MAX_VALUE)
res1: (Long, Long) = (-9223372036854775808,9223372036854775807)

Ketika diterapkan pada true MIN_VALUEand MAX_VALUE, jawaban John Kugelman menghasilkan kasus overflow kapan a == -1dan b ==lainnya (poin pertama kali dikemukakan oleh Kyle). Berikut cara untuk memperbaikinya:

long maximum = Long.signum(a) == Long.signum(b) ? Long.MAX_VALUE : Long.MIN_VALUE;

if ((a == -1 && b == Long.MIN_VALUE) ||
    (a != -1 && a != 0 && ((b > 0 && b > maximum / a) ||
                           (b < 0 && b < maximum / a))))
{
    // Overflow
}

Ini bukan solusi umum untuk MIN_VALUEdan MAX_VALUE, tetapi umum untuk Java Longdan Integerdan nilai apa pun dari adan b.

Jim Pivarski
sumber
Saya hanya berpikir itu tidak perlu mempersulitnya, karena solusi ini hanya berfungsi jika MIN_VALUE = -MAX_VALUE - 1, bukan kasus lain (termasuk contoh kasus uji Anda). Saya harus banyak berubah.
Jim Pivarski
1
Untuk alasan di luar kebutuhan poster asli; untuk orang-orang seperti saya yang menemukan halaman ini karena mereka membutuhkan solusi untuk kasus yang lebih umum (menangani angka negatif dan tidak hanya Java 8). Faktanya, karena solusi ini tidak melibatkan fungsi apa pun di luar aritmatika dan logika murni, solusi ini dapat digunakan untuk C atau bahasa lain juga.
Jim Pivarski
1

Mungkin:

if(b!= 0 && a * b / b != a) //overflow

Tidak yakin dengan "solusi" ini.

Edit: Menambahkan b! = 0.

Sebelum Anda memberi suara negatif : a * b / b tidak akan dioptimalkan. Ini akan menjadi bug kompilator. Saya masih tidak melihat kasus di mana bug luapan dapat ditutup-tutupi.

Thomas Jung
sumber
Juga gagal saat overflow menyebabkan loop sempurna.
Stefan Kendall
Apakah Anda punya contoh tentang apa yang Anda maksud?
Thomas Jung
Baru aja sedikit tesnya: Menggunakan BigInteger 6 kali lebih lambat dibanding menggunakan pendekatan pembagian ini. Jadi saya berasumsi pemeriksaan tambahan untuk kasing sudut sepadan dengan kinerja.
mhaller
Tidak tahu banyak tentang kompiler java, tapi ekspresi seperti a * b / bkemungkinan akan dioptimalkan hanya adalam banyak konteks lain.
SingleNegationElimination
TokenMacGuy - tidak dapat dioptimalkan seperti itu jika ada bahaya overflow.
Tom Hawtin - tackline
1

mungkin ini akan membantu Anda:

/**
 * @throws ArithmeticException on integer overflow
 */
static long multiply(long a, long b) {
    double c = (double) a * b;
    long d = a * b;

    if ((long) c != d) {
        throw new ArithmeticException("int overflow");
    } else {
        return d;
    }
}
dfa
sumber
Tidak akan membantu karena salah satu operannya long.
Tom Hawtin - tackline
1
Apakah Anda bahkan menguji ini? Untuk nilai a & b yang besar tetapi tidak meluap, ini akan gagal karena kesalahan pembulatan dalam versi ganda dari perkalian (coba misalnya 123456789123L dan 74709314L). Jika Anda tidak memahami aritmatika mesin, menebak jawaban untuk pertanyaan tepat semacam ini lebih buruk daripada tidak menjawab, karena akan menyesatkan orang.
Kaya
-1

c / c ++ (panjang * panjang):

const int64_ w = (int64_) a * (int64_) b;    
if ((long) (w >> sizeof(long) * 8) != (long) w >> (sizeof(long) * 8 - 1))
    // overflow

java (int * int, maaf saya tidak menemukan int64 di java):

const long w = (long) a * (long) b;    
int bits = 32; // int is 32bits in java    
if ( (int) (w >> bits) != (int) (w >> (bits - 1))) {
   // overflow
}

1. simpan hasilnya dalam tipe besar (int * int letakkan hasilnya ke long, long * long put ke int64)

2. hasil cmp >> bit dan hasil >> (bit - 1)

xuan
sumber