Выполнить операцию 759 + 674, забыв о переносе. В результате получится 323

1. 
   Faraz qilaylik, ma'lum bir kafega faqat kamgap, muomalasiz mijozlar boradi. Kafe peshtaxtasi bo'ylab 25 ta o'rindiq mavjud. Har safar yangi mehmon kirsa, u boshqa mehmonlardan iloji boricha uzoqroqda o'tirishni xoxlaydi. Hech kim boshqa birovning yonida o'tirmaydi: agar mijoz kirsa va "bo`sh" o'rindiqlar yo'qligini ko'rsa, u darhol orqasiga o'girilib, kafeni tark etadi. Kafe egasi, tabiiyki, iloji boricha ko'proq mijozlar kafeda o'tirishni xohlaydi. Agar unga birinchi mijozni istalgan joyga o'tirishga ruxsat berilsa, kafe egasi nuqtai nazaridan uni qaysi o`rindiqqa o`tkizsa, kafega iloji boricha ko`proq mijoz sig`adi?
   

2. 
   Kitobda 1 dan N gacha raqamlangan n ta varaq bor. Har bir sahifa raqamidagi raqamlar sonini qo'shsangiz, 1095 ga teng bo'ladi. Kitobda nechta sahifa bor?
   

3. 
   Ikkita qarama-qarshi burchaklar (diagonal) kesilgan 8x8 shaxmat taxtasi va 31 ta domino berilgan; Har bir domino taxtada ikkita kvadratni yopishi mumkin. Butun shaxmat taxtanisi dominolar bilan qoplash mumkinmi? Javobingizning izohlab bering.
   

Чтобы просуммировать 759 + 674, я обычно складываю digit[0] обоих чисел, переношу единицу, затем перехожу к digit[1], переношу и т.д. Точно так же можно работать с битами: просуммировать все разряды и при необходимости сделать переносы единиц.

Можно ли упростить алгоритм? Да! Допустим, я хочу разделить «суммирование» и «перенос». Мне придется проделать следующее:

1. 
   Выполнить операцию 759 + 674, забыв о переносе. В результате получится 323.
   
2. 
   Выполнить операцию 759 + 674, но сделать только переносы (без суммирования разрядов). В результате получится 1110.
   
3. 
   Теперь нужно сложить результаты первых двух операций (используя тот же механизм, описанный в шагах 1 и 2): 1110 + 323 = 1433.
   

Теперь вернемся к двоичной системе.

1. 
   Если просуммировать пару двоичных чисел, без учета переноса знака, то i-й просуммированный бит может быть нулевым, только если i-e биты чисел a и b совпадали (оба имели значение 0 или 1). Это классическая операция XOR.
   
2. 
   Если суммировать пару чисел, выполняя только перенос, то i-му биту суммы присваивается значение 1, только если i-1-е биты обоих чисел (a и b) имели значение 1. Это операция AND со смещением.
   
3. 
   Нужно повторять эти шаги до тех пор, пока не останется переносов.
   

759 + 674 ni jamlash uchun men odatda ikkala raqamning [0] raqamini qo'shaman, birini o'tkazaman, so'ngra [1] raqamiga o'taman, o'tkazaman va hokazo. Bitlar bilan xuddi shunday ishlashingiz mumkin: barcha bitlarni jamlang va agar kerak bo'lsa, birliklarni o'tkazing.
Algoritmni soddalashtirish mumkinmi? Ha! Aytaylik, men "sum" va "tashish" ni ajratmoqchiman. Men quyidagilarni qilishim kerak:
1. O'tkazishni unutib, 759 + 674 operatsiyasini bajaring. Natijada 323 bo'ladi.
2. 759 + 674 operatsiyasini bajaring, lekin faqat o'tkazmalarni bajaring (raqamlarni yig'masdan). Natijada 1110 bo'ladi.
3. Endi siz dastlabki ikkita operatsiya natijalarini qo'shishingiz kerak (1 va 2-bosqichlarda tasvirlangan bir xil mexanizm yordamida): 1110 + 323 = 1433.
Endi ikkilik tizimga qaytaylik.
1. Agar siz ikkilik sonlar juftligini tashuvchi belgisini hisobga olmagan holda jamlasangiz, a va b sonlarning i-e bitlari mos kelgan taqdirdagina (ikkalasi ham 0 yoki 1 qiymatga ega bo‘lgan) i-jamlangan bit nolga teng bo‘lishi mumkin. Bu klassik XOR operatsiyasi.
2. Agar siz bir juft raqamlarni qo'shsangiz, faqat ko'chirishni amalga oshirsangiz, yig'indining i-bitiga 1-qiymati, agar ikkala raqamning (a va b) i-1-bitlari 1 qiymatiga ega bo'lsagina beriladi. ofset bilan AND operatsiyasidir.
3. Hech qanday transferlar qolmaguncha ushbu amallarni takrorlashingiz kerak.
public static int add(int a, int b) {
if (b == 0) return a;
int sum = a ^ b; // добавляем без переноса
int carry = (a & b) << 1; // перенос без суммирования
return add(sum, carry); // рекурсия
}