15

掛け算と足し算の両方を行う方法はありますが、頭を悩ませることはできません。どちらも外部のWebサイトからのものであり、私自身のものではありません。

public static void bitwiseMultiply(int n1, int n2) {
    int a = n1, b = n2, result=0;
    while (b != 0) // Iterate the loop till b==0
    {
        if ((b & 01) != 0) // Logical ANDing of the value of b with 01
        {
            result = result + a; // Update the result with the new value of a.
        }
        a <<= 1;              // Left shifting the value contained in 'a' by 1.
        b >>= 1;             // Right shifting the value contained in 'b' by 1.
    }
    System.out.println(result);
}

public static void bitwiseAdd(int n1, int n2) {
    int x = n1, y = n2;
    int xor, and, temp;
    and = x & y;
    xor = x ^ y;

    while (and != 0) {
        and <<= 1;
        temp = xor ^ and;
        and &= xor;
        xor = temp;
    }
    System.out.println(xor);
}

ステップバイステップのデバッグを試してみましたが、実際には機能しますが、あまり意味がありませんでした。

私がおそらく探しているのは、これがどのように機能するかを理解することです（おそらく数学的な基礎ですか？）。

編集：これは宿題ではありません。Javaでビット演算を学習しようとしています。

4

4 に答える 4

26

乗算コードを調べることから始めましょう。アイデアは実際にはかなり賢いです。n1とn2がバイナリで記述されているとします。次に、n1を2の累乗の合計と考えることができます。n2= c 30 2 30 + c 29 2 29 + ... + c 1 2 1 + c 0 2 0、ここで、各ciは0または1のいずれかです。次に、積n 1n2を次のように考えることができます。

n 1 n 2 =

n 1（c 30 2 30 + c 29 2 29 + ... + c 1 2 1 + c 0 2 0）=

n 1 c 30 2 30 + n 1 c 29 2 29 + ... + n 1 c 1 2 1 + n 1 c 0 2 0

これは少し密度が高いですが、2つの数値の積は、最初の数値に2の累乗を掛けて2番目の数値を構成する2の累乗に、2番目の数値の2進数の値を掛けたもので与えられるという考え方です。

ここで問題となるのは、実際の乗算を行わずにこの合計の項を計算できるかどうかです。そのためには、n2の2進数を読み取れる必要があります。幸い、シフトを使用してこれを行うことができます。特に、n 2から始めて、最後のビットだけを見るとします。それはc0です。次に、値を1つ下にシフトすると、最後のビットはc 0などになります。より一般的には、n 2の値をiの位置だけ下にシフトした後、最下位ビットはciになります。。最後のビットを読み取るには、値と数値1をビット単位でAND演算します。これは、最後の桁を除くすべての場所でゼロである2進表現を持ちます。任意のnに対して0ANDn = 0であるため、これにより最上位ビットがすべてクリアされます。さらに、0 AND 1=0および1AND1 = 1であるため、この操作は数値の最後のビットを保持します。

さて、これでciの値を読み取ることができることがわかりました。だから何？幸いなことに、同様の方法で系列n 12iの値を計算することもできます。特に、値のシーケンスn 1 << 0、n 1 << 1などを考慮してください。左ビットシフトを実行するときはいつでも、2の累乗を掛けることに相当します。これは、上記の合計を計算するために必要なすべてのコンポーネントが揃ったことを意味します。これがあなたのオリジナルのソースコードで、何が起こっているのかコメントされています：

public static void bitwiseMultiply(int n1, int n2) {
    /* This value will hold n1 * 2^i for varying values of i.  It will
     * start off holding n1 * 2^0 = n1, and after each iteration will 
     * be updated to hold the next term in the sequence.
     */
    int a = n1;

    /* This value will be used to read the individual bits out of n2.
     * We'll use the shifting trick to read the bits and will maintain
     * the invariant that after i iterations, b is equal to n2 >> i.
     */
    int b = n2;

    /* This value will hold the sum of the terms so far. */
    int result = 0;

    /* Continuously loop over more and more bits of n2 until we've
     * consumed the last of them.  Since after i iterations of the
     * loop b = n2 >> i, this only reaches zero once we've used up
     * all the bits of the original value of n2.
     */
    while (b != 0)
    {
        /* Using the bitwise AND trick, determine whether the ith 
         * bit of b is a zero or one.  If it's a zero, then the
         * current term in our sum is zero and we don't do anything.
         * Otherwise, then we should add n1 * 2^i.
         */
        if ((b & 1) != 0)
        {
            /* Recall that a = n1 * 2^i at this point, so we're adding
             * in the next term in the sum.
             */
            result = result + a;
        }

        /* To maintain that a = n1 * 2^i after i iterations, scale it
         * by a factor of two by left shifting one position.
         */
        a <<= 1;

        /* To maintain that b = n2 >> i after i iterations, shift it
         * one spot over.
         */
        b >>>= 1;
    }

    System.out.println(result);
}

お役に立てれば！

于 2011-02-04T06:46:43.897 に答える
6

問題はJavaではなく、2進数で計算しているようです。単純なものの始まり:(すべての数値は2進数:)

0 + 0 = 0   # 0 xor 0 = 0
0 + 1 = 1   # 0 xor 1 = 1
1 + 0 = 1   # 1 xor 0 = 1
1 + 1 = 10  # 1 xor 1 = 0 ( read 1 + 1 = 10 as 1 + 1 = 0 and 1 carry)

わかりました...xor演算を使用して2つの1桁の数値を追加できることがわかります。とを使用すると、「キャリー」ビットがあるかどうかを確認できます。これは、ペンと紙で数字を追加するのと非常によく似ています。（この時点まで、Half-Adderと呼ばれるものがあります）。次の2ビットを追加するときは、それらの2桁にキャリービットも追加する必要があります。これを考慮に入れると、全加算器を取得できます。ウィキペディアで半加算器と全加算器の概念について読むことができます：http： //en.wikipedia.org/wiki/Adder_ （electronics ）そしてウェブ上の他の多くの場所。それがあなたのスタートになることを願っています。

ちなみに掛け算はとても似ています。小学校でペンと紙を掛けた方法を覚えておいてください。それがここで起こっていることです。10進数ではなく、2進数で発生しているだけです。

于 2011-02-04T06:39:45.790 に答える
6

bitwiseAddメソッドの説明：

私はこの質問がしばらく前に尋ねられたことを知っていますが、bitwiseAddメソッドがどのように機能するかについて完全な答えが与えられていないので、ここに1つあります。

bitwiseAddにカプセル化されたロジックを理解するための鍵は、加算演算とxorおよびビット単位演算の関係にあります。この関係は、次の式で定義されます（この式の数値例については、付録1を参照してください）。

x + y = 2 * (x&y)+(x^y)     (1.1)

またはもっと簡単に：

x + y = 2 * and + xor       (1.2)

with
    and = x & y
    xor = x ^ y

この方程式でおなじみの何かに気づいたかもしれません。and変数とxor変数は、bitwiseAddの最初に定義されたものと同じです。2による乗算もあります。これは、bitwiseAddではwhileループの開始時に実行されます。しかし、後で戻ってきます。

先に進む前に、「＆」ビット演算子についても簡単に説明します。 この演算子は基本的に、適用されるビットシーケンスの共通部分を「キャプチャ」します。たとえば、9＆13 = 1001＆1101 = 1001（= 9）です。この結果から、両方のビットシーケンスに共通するビットのみが結果にコピーされていることがわかります。これから、2つのビットシーケンスに共通ビットがない場合、それらに「＆」を適用した結果は0になることがわかります。 これは、加算とビット単位の関係に重要な結果をもたらします。これはすぐに明らかになります。

ここで問題となるのは、式1.2では「+」演算子が使用されているのに対し、bitwiseAddでは使用されていないことです（「^」、「＆」、「<<」のみを使用しています）。では、式1.2の「+」をどういうわけか消えさせるにはどうすればよいでしょうか。回答：「強制的に」and式で0を返すようにします。これを行う方法は、再帰を使用することです。

これを実証するために、方程式1.2を1回繰り返します（このステップは最初は少し難しいかもしれませんが、必要に応じて付録2に詳細なステップバイステップの結果があります）：

x + y = 2*(2*and & xor) + (2*and ^ xor)     (1.3)

またはもっと簡単に：

x + y = 2 * and[1] + xor[1]     (1.4)

with
    and[1] = 2*and & xor,
    xor[1] = 2*and ^ xor,
    [1] meaning 'recursed one time'

ここで注意すべき興味深いことがいくつかあります。最初に、実際にbitwiseAddに見られるような、再帰の概念がループの概念にどのように近いかに気づきました。and[1]とxor[1]が何であるかを考えると、この関係はさらに明白になります。これらは、 bitwiseAddのwhileループ内で定義されたandおよびxor式と同じ式です。また、パターンが出現することにも注意してください。式1.4は式1.2とまったく同じように見えます。

この結果、再帰表記を維持すれば、さらに再帰を実行するのは簡単です。ここで、方程式1.2をさらに2回繰り返します。

x + y = 2 * and[2] + xor[2]
x + y = 2 * and[3] + xor[3]

これで、bitwiseAddにある「 temp」変数の役割が強調表示されます。tempを使用すると、ある再帰レベルから次の再帰レベルに渡すことができます。

また、これらすべての方程式で2が乗算されていることにも注意してください。前述のように、この乗算は、and <<=1ステートメントを使用してbitwiseAddのwhileループの開始時に行われます。and [i]のビットは、前のステージのand [i]のビットとは異なるため、この乗算は次の再帰ステージに影響を及ぼします（また、「＆」演算子について前に作成した小さなサイドノートを思い出してください。あなたはおそらくこれが今どこに向かっているのかわかるでしょう）。

式1.4の一般的な形式は次のようになります。

x + y = 2 * and[x] + xor[x]     (1.5)
with x the nth recursion

ファイナリー：

では、この再帰ビジネスはいつ正確に終了するのでしょうか。

回答：式1.5のand[x]式の2つのビットシーケンス間の交差が0を返すと終了します。これと同等のbitwiseAddは、whileループ条件がfalseになると発生します。この時点で、式1.5は次のようになります。

    x + y = xor[x]      (1.6)

そしてそれが、bitwiseAddで最後にxorのみを返す理由を説明しています！

これで完了です。このbitwiseAdd私が言わなければならないかなり賢いコードの断片:)

これがお役に立てば幸いです

付録：

1）式1.1の数値例

式1.1は次のように述べています。

    x + y = 2(x&y)+(x^y)        (1.1)

このステートメントを検証するために、簡単な例をとることができます。たとえば、9と13を足し合わせます。手順を以下に示します（ビット単位の表現は括弧内にあります）。

我々は持っています

    x = 9 (1001)
    y = 13  (1101)

と

    x + y = 9 + 13 = 22
    x & y = 9 & 13 = 9 (1001 & 1101 = 1001)
    x ^ y = 9^13 = 4 (1001 ^ 1101 = 0100)

これを式1.1に戻すと、次のようになります。

    9 + 13 = 2 * 9 + 4 = 22 et voila!

2）最初の再帰ステップのデモンストレーション

プレゼンテーションの最初の漸化式（式1.3）は、次のように述べています。

もしも

x + y = 2 * and + xor           (equation 1.2)

それから

x + y = 2*(2*and & xor) + (2*and ^ xor)     (equation 1.3)

この結果を得るには、上記の式1.2の2*および+xorの部分を取得し、式1.1で与えられる加算/ビットごとのオペランドの関係を適用しました。これは次のように示されます。

もしも

    x + y = 2(x&y) + (x^y)      (equation 1.1)

それから

     [2(x&y)] + (x^y)     =      2 ([2(x&y)] & (x^y)) + ([2(x&y)] ^ (x^y))
(left side of equation 1.1)  (after applying the addition/bitwise operands relationship)

式1.2のandおよびxor変数の定義を使用してこれを単純化すると、式1.3の結果が得られます。

[2(x&y)] + (x^y) = 2*(2*and & xor) + (2*and ^ xor)

with
    and = x&y
    xor = x^y

そして、同じ単純化を使用すると、式1.4の結果が得られます。

2*(2*and & xor) + (2*and ^ xor) = 2*and[1] + xor[1]

with
    and[1] = 2*and & xor
    xor[1] = 2*and ^ xor
    [1] meaning 'recursed one time'
于 2012-11-24T01:22:18.153 に答える
0

これが乗算の別のアプローチです

/**
 * Multiplication of binary numbers without using '*' operator
 * uses bitwise Shifting/Anding
 *
 * @param n1
 * @param n2
 */
public static void multiply(int n1, int n2) {
    int temp, i = 0, result = 0;

    while (n2 != 0) {
        if ((n2 & 1) == 1) {
            temp = n1;

            // result += (temp>>=(1/i)); // To do it only using Right shift
            result += (temp<<=i); // Left shift (temp * 2^i)
        }
        n2 >>= 1;   // Right shift n2 by 1.
        i++;
    }

    System.out.println(result);
}
于 2015-10-09T09:04:45.987 に答える