Penerangan yang diberikan untuk Jumlah Dua Integer adalah sangat mudah:
Diberi dua integer a dan b, kembalikan jumlah dua integer tanpa menggunakan operator dan -.
Contohnya:
Input: a = 1, b = 2 Output: 3
Atau:
Input: a = 2, b = 3 Output: 5
Dalam masalah terakhir siri ini, kami akan menutup dengan menambah dua integer menggunakan manipulasi bit dan bukannya operator tambah kesayangan kami.
Menambah dua bit, sama ada daripadanya hanya boleh 1 atau 0, tidak mempunyai banyak hasil yang berbeza-beza.
Jika kita menambah dua bit iaitu 1 dan 0 (atau, 0 dan 1), hasilnya akan menjadi 1. Jika kita menambah dua bit 0, hasilnya ialah 0. Jika, bagaimanapun, kita menambah dua 1 bit, kita mempunyai carry — yang bermaksud kita perlu menulis 0 dalam output, tetapi juga membawa 1.
Sebagai contoh, menambah 2 dan 3 akan menghasilkan 5, dan kami akan mempunyai nilai bawa semasa operasi:
Tanpa memikirkan nilai bawaan, output yang perlu kita miliki selepas menambah dua bit adalah serupa dengan apa yang kita akan ada selepas operasi XOR. Jika kita mempunyai bit yang berbeza (0 dan 1, atau, 1 dan 0), output akan menjadi 1, jika tidak 0 (menambah 0 dan 0, atau , 1 dan 1).
Jadi, operasi XOR boleh membantu kami dengan output.
Bagaimana dengan pembawa?
Kami mempunyai nilai bawa hanya apabila kedua-dua bit adalah 1 — yang kelihatan seperti operasi DAN.
Jadi, operasi DAN boleh membantu kami dengan membawa.
Juga ambil perhatian bahawa nilai bawa dianjak ke kiri, yang mana kami juga mempunyai operator anjakan kiri yang berguna.
Jadi, output dan carry kami boleh kelihatan seperti ini:
let output = a ^ b; let carry = (a & b) << 1;
Kami boleh terus mengubah suai dua nilai yang kami ada dan teruskan sehingga kami tidak mempunyai sebarang nilai bawaan. Kita boleh mengubah suai a menjadi output, dan b menjadi carry, dan mengembalikan a, yang memegang output akhir pada penghujungnya.
Secara keseluruhan, penyelesaian akhir mungkin kelihatan seperti ini dalam TypeScript:
function getSum(a: number, b: number): number { // while we still have carry while (b !== 0) { let output = a ^ b; let carry = (a & b) << 1; a = output; b = carry; } return a; }
Kedua-dua a dan b ialah nilai malar, dan kami juga tidak memerlukan struktur data tambahan yang saiznya akan berkembang secara berkadar dengan input, jadi kedua-dua masa dan kerumitan ruang kami akan tetap, O(1) .
Dan, itulah masalah terakhir siri Meditasi LeetCode! Kami akan menyelesaikannya dengan kesimpulan dalam siaran seterusnya — sehingga itu, selamat mengekod.
Atas ialah kandungan terperinci Meditasi LeetCode: Jumlah Dua Integer. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!