Cara terbaik untuk membuat modulus Java berperilaku seperti seharusnya dengan angka negatif?

103

Di java saat Anda melakukannya

a % b

Jika a negatif, itu akan mengembalikan hasil negatif, alih-alih membungkusnya menjadi b seperti seharusnya. Apa cara terbaik untuk memperbaikinya? Satu-satunya cara saya bisa berpikir adalah

a < 0 ? b + a : a % b
fent
sumber
12
Tidak ada perilaku modulus yang "benar" saat menangani bilangan negatif - banyak bahasa melakukannya dengan cara ini, banyak bahasa melakukannya dengan cara berbeda, dan beberapa bahasa melakukan sesuatu yang sama sekali berbeda. Setidaknya dua yang pertama memiliki pro dan kontra.
4
ini aneh bagiku. Saya pikir itu seharusnya hanya mengembalikan negatif jika b negatif.
merayakan
2
ini. tapi judul pertanyaan itu harus diganti namanya. saya tidak akan mengklik pertanyaan itu jika saya sedang mencari yang satu ini karena saya sudah tahu cara kerja modulus java.
merayakan
4
Saya baru saja mengganti namanya menjadi dari "Why is -13% 64 = 51?", Yang tidak akan pernah menjadi sesuatu yang dicari seseorang dalam sejuta tahun. Jadi judul pertanyaan ini jauh lebih baik, dan lebih mudah dicari dengan kata kunci seperti modulus, negatif, kalkulasi, angka.
Erick Robertson

Jawaban:

144

Ini berperilaku sebagaimana mestinya a% b = a - a / b * b; yaitu sisanya.

Anda dapat melakukan (a% b + b)% b


Ekspresi ini bekerja karena hasil dari (a % b)harus lebih rendah dari b, tidak peduli apakah apositif atau negatif. Penjumlahan bmenangani nilai negatif dari a, karena (a % b)merupakan nilai negatif antara -bdan 0, (a % b + b)harus lebih rendah dari bdan positif. Modulo terakhir ada jika apositif untuk memulai, karena jika apositif (a % b + b)akan menjadi lebih besar dari b. Oleh karena itu, (a % b + b) % bubah menjadi lebih kecil dari blagi (dan tidak mempengaruhi anilai negatif ).

Peter Lawrey
sumber
3
ini bekerja lebih baik, terima kasih. dan ini bekerja untuk bilangan negatif yang jauh lebih besar dari b juga.
merayakan
6
Ini berfungsi karena hasil dari (a % b)selalu lebih rendah dari b(tidak peduli apakah apositif atau negatif), penambahan bmenjaga nilai negatif a, karena (a % b)lebih rendah dari bdan lebih rendah dari 0, (a % b + b)harus lebih rendah dari bdan positif. Modulo terakhir ada jika apositif untuk memulai, karena jika apositif (a % b + b)akan menjadi lebih besar dari b. Oleh karena itu, (a % b + b) % bubah menjadi lebih kecil dari blagi (dan tidak mempengaruhi anilai negatif ).
ethanfar
1
@eitanfar Saya telah memasukkan penjelasan Anda yang luar biasa ke dalam jawaban (dengan sedikit koreksi a < 0, mungkin Anda bisa melihatnya)
Maarten Bodewes
5
Saya baru saja melihat ini mengomentari pertanyaan lain tentang topik yang sama; Mungkin perlu disebutkan bahwa (a % b + b) % bpemecahan untuk nilai yang sangat besar dari adan b. Misalnya, menggunakan a = Integer.MAX_VALUE - 1dan b = Integer.MAX_VALUEakan memberi -3hasil, yang merupakan angka negatif, yang ingin Anda hindari.
Thorbear
2
@Mikepote menggunakan a whileakan lebih lambat jika Anda benar-benar membutuhkannya kecuali Anda hanya perlu ifdalam hal ini sebenarnya lebih cepat.
Peter Lawrey
92

Pada Java 8, Anda dapat menggunakan Math.floorMod (int x, int y) dan Math.floorMod (long x, long y) . Kedua metode ini memberikan hasil yang sama dengan jawaban Petrus.

Math.floorMod( 2,  3) =  2
Math.floorMod(-2,  3) =  1
Math.floorMod( 2, -3) = -1
Math.floorMod(-2, -3) = -2
John Krueger
sumber
1
jawaban terbaik untuk Java 8+
Charney Kaye
Keren, tidak tahu tentang yang itu. Java 8 secara definitif memperbaiki beberapa PITA.
Franz D.
4
Cara yang baik. Tapi sayangnya tidak bekerja dengan floatatau doubleargumen. Mod binary operator ( %) juga bekerja dengan floatdan doubleoperan.
Mir-Ismaili
11

Bagi mereka yang belum menggunakan (atau belum bisa menggunakan) Java 8, Guava datang untuk menyelamatkan dengan IntMath.mod () , tersedia sejak Guava 11.0.

IntMath.mod( 2, 3) = 2
IntMath.mod(-2, 3) = 1

Satu peringatan: tidak seperti Math.floorMod () Java 8, pembagi (parameter kedua) tidak boleh negatif.

Ibrahim Arief
sumber
7

Dalam teori bilangan, hasilnya selalu positif. Saya kira hal ini tidak selalu terjadi dalam bahasa komputer karena tidak semua programmer adalah ahli matematika. Dua sen saya, saya akan menganggapnya sebagai cacat desain bahasa, tetapi Anda tidak dapat mengubahnya sekarang.

= MOD (-4.180) = 176 = MOD (176, 180) = 176

karena 180 * (-1) + 176 = -4 sama dengan 180 * 0 + 176 = 176

Menggunakan contoh jam di sini, http://mathworld.wolfram.com/Congruence.html Anda tidak akan mengatakan durasi_of_time mod cycle_length adalah -45 menit, Anda akan mengatakan 15 menit, meskipun kedua jawaban memenuhi persamaan dasar.

Chris Golledge
sumber
1
Dalam teori bilangan tidak selalu positif ... Mereka termasuk dalam kelas kesesuaian. Anda bebas memilih kandidat apa pun dari kelas itu untuk tujuan notasi Anda, tetapi idenya adalah bahwa ia memetakan ke semua kelas itu, dan jika menggunakan kandidat lain tertentu darinya membuat masalah tertentu jauh lebih sederhana (memilih -1daripada n-1misalnya) kemudian lakukan itu.
BeUndead
2

Java 8 memiliki Math.floorMod, tetapi sangat lambat (implementasinya memiliki beberapa divisi, perkalian, dan bersyarat). Mungkin saja JVM memiliki rintisan yang dioptimalkan secara intrinsik untuknya, bagaimanapun, yang akan mempercepatnya secara signifikan.

Cara tercepat untuk melakukan ini tanpanya floorModadalah seperti beberapa jawaban lain di sini, tetapi tanpa cabang bersyarat dan hanya satu %operasi lambat .

Asumsi n positif, dan x bisa berupa apa saja:

int remainder = (x % n); // may be negative if x is negative
//if remainder is negative, adds n, otherwise adds 0
return ((remainder >> 31) & n) + remainder;

Hasil ketika n = 3:

x | result
----------
-4| 2
-3| 0
-2| 1
-1| 2
 0| 0
 1| 1
 2| 2
 3| 0
 4| 1

Jika Anda hanya memerlukan distribusi seragam antara 0dan n-1dan bukan operator mod yang tepat, dan Anda xtidak mengelompokkan dekat 0, berikut ini akan menjadi lebih cepat, karena ada lebih banyak paralelisme tingkat instruksi dan %komputasi lambat akan terjadi secara paralel dengan yang lain bagian karena tidak bergantung pada hasilnya.

return ((x >> 31) & (n - 1)) + (x % n)

Hasil diatas dengan n = 3:

x | result
----------
-5| 0
-4| 1
-3| 2
-2| 0
-1| 1
 0| 0
 1| 1
 2| 2
 3| 0
 4| 1
 5| 2

Jika masukan acak dalam rentang penuh int, distribusi kedua solusi akan sama. Jika cluster masukan mendekati nol, akan ada terlalu sedikit hasil di n - 1solusi terakhir.

Scott Carey
sumber
1

Berikut ini alternatifnya:

a < 0 ? b-1 - (-a-1) % b : a % b

Ini mungkin atau mungkin tidak lebih cepat dari rumus lain [(a% b + b)% b]. Tidak seperti rumus lainnya, rumus ini berisi cabang, tetapi menggunakan satu operasi modulo yang lebih sedikit. Mungkin menang jika komputer dapat memprediksi <0 dengan benar.

(Edit: Memperbaiki rumus.)

Stefan Reich
sumber
1
Tetapi operasi modulo membutuhkan pembagian yang bahkan bisa lebih lambat (terutama jika prosesor menebak cabang dengan benar hampir sepanjang waktu). Jadi ini mungkin lebih baik.
Dave
@Tausiyahku. Kamu benar! Saya memperbaiki rumusnya, sekarang berfungsi dengan baik (tetapi membutuhkan dua pengurangan lagi).
Stefan Reich
Itu benar @dave
Stefan Reich