Что такое ^ b и (a & b) << 1?

Я делал этот вопрос в Leetcode.

Запрос:

Вычислите сумму двух целых чисел a и b, но вы не можете использовать операторы + и -.

Я не могу понять решение, которое оно дало

Может кто-нибудь объяснить, как работает эта функция getSum?

Вот ответ в JS:

var getSum=function(a,b) {
    const Sum = a^b; //I can't understand how those two line code can
    const carry = (a & b) << 1; //get the sum
        if(!carry) {
            return Sum
        }
    return getSum(Sum,carry);
};
console.log(getSum(5,1));

Ответ 1

Давайте учиться на собственном примере. Представьте, что a = 3 и b = 5

В двоичной записи они a = 0011 и b = 0101

XOR: a^b является оператором XOR. При сравнении двух битов возвращается 0 если они одинаковы, и 1 если они разные. 01^10 => 11

Поэтому, когда мы делаем a^b результат будет 0110.

И + SHIFT

a&b выполняет логическую операцию И Возвращает 1 только тогда, когда a = b = 1.

В нашем случае результат 0001

<< сдвигает его (добавляет 0 на правой стороне), и результат стал 0010, который устанавливает carry переменной верно. (только 0000 будет ложным).

Следующие итерации:

Все повторяется, но теперь a = 0110 и b = 0010 (Sum и carry с последнего выполнения)

Теперь a^b = 0100 и (a&b)<<1 = 0100

Повторяю еще раз.

Теперь a^b = 0000 и (a&b)<<1 = 1000

И опять.

Теперь a^b = 1000 и (a&b)<<1 = 0000. Теперь carry, наконец, false. И мы возвращаем 1000 что является десятичным 8.

Все работало нормально, так как 3+5=8

Ответ 2

Это в основном тиражирование полусуммера

Добавление 2 битов A и B приводит к 2 выходам: сумма и бит переноса, как показано ниже

╔═══════╤═════════════╗
║ Input │   Output    ║
╠═══╤═══╪═══════╤═════╣
║ A │ B │ carry │ sum ║
╟───┼───┼───────┼─────╢
║ 0 │ 0 │   0   │  0  ║
╟───┼───┼───────┼─────╢
║ 1 │ 0 │   0   │  1  ║
╟───┼───┼───────┼─────╢
║ 0 │ 1 │   0   │  1  ║
╟───┼───┼───────┼─────╢
║ 1 │ 1 │   1   │  0  ║
╚═══╧═══╧═══════╧═════╝

Из таблицы мы получаем логику для выходов: carry = A и B, sum = A xor B

XOR также называется оператором сложения без переноса и представлен символом ⊕ с символом + внутри

Таким образом, фрагмент выше работает так

const Sum=a^b;              // sum = a xor b = a ⊕ b
const carry=(a&b)<<1;       // carry = 2*(a and b), since we carry to the next bit
if(!carry){
    return Sum;             // no carry, so sum + carry = sum
}
return getSum(Sum,carry);   // a + b = sum + carry

Таким образом, a^b добавляет каждый бит в и b одновременно, оставляя не переносимую сумму a и b в Sum. Затем мы должны добавить перенос к сумме без переноса, чтобы получить окончательный результат, так как у нас есть только полусуммер вместо полного сумматора, который выполняет перенос a + b = a ⊕ b +

Смотрите также

Ответ 3

 int result = p ^ q; // XOR Operator, + without carry 0+0=0, 0+1=1+0=1, 1+1=0
int carry = (p & q) << 1; // Left Shift, 1+1=2
if (carry != 0) {
    return getSum(result, carry);
}
return result;

Начните с p = 5, q = 6. Тогда XOR будет,

0101
0110
------
0011

Таким образом, XORing приводит к (0011), который на самом деле 3 в десятичном виде. Тогда ANDing p и q мы получаем,

0101
0110
-------
0100

Мы получаем 4 (100 в двоичном виде) с помощью ANDing 5 & 6, теперь, если мы сместим это значение влево, мы получим

 0100<<1=1000

Таким образом, мы получаем 8 (1000 в двоичном виде) после первой рекурсии. Так как результат (переменная переноса) не равен нулю, давайте повторим рекурсию по значению xor и значению переноса.

getSum(3, 8);

Итак, делая первый XORing, мы получаем,

0011
1000
-------
1011

XORing на этот раз дал 11 (1011 двоичный), поэтому мы выполняем И сейчас,

0011
1000
-------
0000

Мы получаем все НУЛИ для ANDing 3 и 8, поэтому на этот раз оператор сдвига влево также приводит к нулю, так как здесь у нас нет 1, который может дать нам значение путем смещения нуля влево. Поскольку переменная переноса теперь равна нулю, мы заканчиваем рекурсию, а значением XORed будет сумма, равная 11 (1011 в двоичном виде).

Надеюсь, вы получите работу процедуры. Вы можете узнать больше, изучая побитовые операции, так как машина выполняет арифметические операции.

Ответ 4

^ - это XOR, побитовая операция. Для одного бита применяются следующие правила: 0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 0 = 0 и 1 ^ 1 = 0, и вы просто расширяете его для соответствующих битов при работе с многобитовыми значениями. Название сокращенно от "исключающее или" и происходит от того факта, что A ^ B равно 1 если и только если A или B равно 1, а не оба. Но более интересно поговорить о другом его названии ⊕. ⊕ +, но немного отличается. Вы заметите, что правила для ⊕ аналогичны правилам сложения: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1 и 1 + 1 = 10. ⊕ равно +, кроме 1 ⊕ 1 = 0; то есть ⊕ +, за исключением случаев, когда нет. Это верно для нескольких битов: 011 + 001 = 100, потому что вы переносите 1 из одного места в место двойки, а затем снова переносите 1 в место четверки. Тогда 011 ⊕ 001 = 010, потому что вы просто не несете.

Теперь, когда вы делаете настоящее дополнение, когда вы носите? В двоичном коде ответ очень прост: вы переносите 1 на следующее место, когда в данном месте есть два 1. Это легко понять как побитовое И, &. 1 & 1 = 1 и 0 противном случае. Для 011 + 001 сложение без переноса дает 011 ⊕ 001 = 010, и мы можем сказать, что нам нужно вынести 1 из одного места, потому что 011 & 001 = 001. Сдвиг в (a & b) << 1 превращает число "откуда мне нужно нести?" в "где мне нужно добавить переносов?": (011 & 001) << 1 = 010; Мне нужно добавить немного переноса в месте двойки.

Итак, в getSum мы хотим знать a + b. Мы вычисляем сложение без переноса с a ^ b и находим, где нам нужно добавить переносимые биты с (a & b) << 1. Теперь нам просто нужно сложить эти два. Ну, у нас уже есть функция для сложения чисел; это называется getSum. Итак, мы просто пишем function getSum(a, b) { return getSum(a ^ b, (a & b) << 1); } function getSum(a, b) { return getSum(a ^ b, (a & b) << 1); }, за исключением того, что мы обеспечиваем короткое замыкание, если нечего нести, спасая нас от бесконечной рекурсии.