☰

a ^ b と (a & b) << 1 とは何ですか? 質問する

tag-icon • tag-icon javascript bitwise-operators
a ^ b と (a & b) << 1 とは何ですか? 質問する

私はこれをやっていた質問leetcode で。

リクエスト：

2 つの整数 a と b の合計を計算しますが、演算子 + と - は使用できません。

提示された解決策が理解できない

このgetSum機能がどのように動作するのか説明してくれる人はいますか?

JS での答えは次のとおりです。

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

ベストアンサー1

基本的には、半加算器

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  ║
╚═══╧═══╧═══════╧═════╝

表から出力のロジックを取得します。キャリー = A と B、合計 = A xor B

排他的論理和はキャリーレス加算演算子とも呼ばれ、⊕で表され、+その中に記号が入っています。

上記のスニペットは次のように動作します

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^baとbの各ビットを同時に加算し、aとbの非キャリー合計をに残しますSum。次に、a + b = a ⊕ b + キャリーを実行する全加算器ではなく、半加算器しかないため、最終結果を得るためには、キャリーなしの合計にキャリーを加算する必要があります。

参照

おすすめ記事