まれですが、それでも、インタビューやトレーニングからのタスクが実用的な価値を持っています。そのため、整数値に対する算術演算の代替手段をJavaで実装する必要がありました。幸いなことに、検索エンジンの最初のページには、ビット単位のアナログ用の既製のソリューションがたくさんあり、それらのほとんどに頭を悩ませる必要はありませんでした。
率直に言って、私はハブレにそのような資料がないことに少し驚いたので（私は見栄えが悪かったのですか？）、したがって、この欠点を私のコメントと追加で埋めることにしました。
ビット単位の操作を使用した例では、値がニブルに切り捨てられていることに注意してください：基本的な違いはありませんが、理解しやすくなっています。
添加
アルゴリズム：
private int add(int summand, int addend)
{
/*.*/
int carry = 0x00;
/* , .*/
while(addend != 0x00)
{
/* .*/
carry = (summand & addend);
/* , .*/
summand = summand ^ addend;
/* .*/
addend = (carry << 1);
}
return summand;
}
まず、シニアカテゴリーへの移行について覚えておく必要があります。10進法では、その定義（現在の桁）には10から18の範囲の値が含まれます：
109 +
019 =
128
バイナリシステムでは、1より大きいすべてのものが転送されます。
0001 +
0001 =
----
0010
またはこのように：
0011 +
0011 =
----
0110
最後の例では、最下位ビットが最初に追加されます。
1 + 1 = 10 ()
現在のビットにはゼロが残り、1つは最も重要なビットに移動し、さらに次のように参加します。
1 + 1 + 1 = 11 ()
最も低いものは現在のものに残り、古いものはさらに移動します。ここから、現在の1ビットのバイナリシステムでは、2から3までの値がキャリーに該当するというルールを推測できます。
アルゴリズムに関する部分では、前の値の例を使用して転送の有無を判別するための指示に注意を払う価値があります。
carry = (summand & addend);
0011 = 0011 & 0011
これはまだ転送ではありませんが、数字に「フラグ」を設定すると、それを追加すると転送が終了します。キャリーの追加は、ビットが同じ場合です。
何かがすでにクリアされたらすぐに、転送が考慮されるビットから最初の項を解放する必要があります。
summand = summand ^ addend;
0000 = 0011 ^ 0011
ご存知のように、ビット単位のXOR演算子は、ビット値が反対の場合にのみビットを設定します。
ループの3番目のステップは、キャリーフラグを直接キャリーに変換することです。これを行うには、それらを1ステップ左にシフトし、第2項に割り当てます。
addend = (carry << 1);
0110 = (0011 << 1);
次の反復では、次の理由により、転送は修正されません。
carry = (summand & addend);
0000 = 0000 & 0110
2番目のステップは私たちに与えるでしょう：
summand = summand ^ addend;
0110 = 0000 ^ 0110,
これは望ましい合計であり、3番目のステップはwhile（）ループを終了します。
addend = (carry << 1);
0000 = (0000 << 1)
減算
アルゴリズム：
private int sub(int minuend, int subtrahend)
{
/* .*/
int borrow = 0x00;
/* , .*/
while(subtrahend != 0x00)
{
/* .*/
borrow = ((~minuend) & subtrahend);
/* , .*/
minuend = minuend ^ subtrahend;
/* .*/
subtrahend = (borrow << 1);
}
return minuend;
}
前のものと同等ですが、最上位ビットからのビットの借用が逆含意反転で実装されている点が異なります。さて、ローカル変数の名前を変更します。
乗算
アルゴリズム：
public int multiply(int mul1, int mul2)
{
int result = 0;
/* .*/
while(mul2 != 0)
{
/* ...*/
if ((mul2 & 1) == 1)
{
/* .*/
result = add(result, mul1);
}
/* ("")*/
mul1 <<= 1;
/* if()*/
mul2 >>>= 1;
}
return result;
}
基本に戻る：10進法での長い乗算：
25 *
05 =
--
125 +
00
---
125
それら。2番目の要素の各桁に最初の要素を掛けます。ここから、最上位ビットからの積が1ステップ左にシフトされます。最後に、中間値を追加します。同じことがビット単位のレベルでも起こります。
0110 *
0011 =
----
0110 +
0 110 +
00 00 +
000 0 +
- ----
1 0010
もちろん、アルゴリズムは、最上位ビットに転送するためのルールを考慮に入れて、2番目のファクターでセットビットが検出されるたびに最初のファクターをそれ自体に追加するだけでよいと結論付けます。
if ((mul2 & 1) == 1) //(0011 & 0001) == 0001
{
result = add(result, mul1); //0110 = 0000 + 0110
}
次に、最初の乗数が1ビット左にシフトされます（「はしご」を形成します）。
mul1 <<= 1; //1100 = 0110 << 1;
ここで、2番目の要素の2番目に重要なビットにビットがあるかどうかを判断します。
mul2 >>>= 1; //0001 = 0011 >>> 1;
サイクルは、2番目の係数がゼロになるまで実行されます。次の点に注意してください。このアルゴリズムのインスタンスは、リソースからリソースへと移動します。ここで、2番目の要素（mul2 >>> = 1）の論理シフトが算術シフト（mul2 >> = 1）に置き換えられます。これはおそらく、C / C ++での実装に由来します。ここでは、unsignedキーワードがあり、そのような置換は問題ではありません。ただし、Javaではすべてのタイプの数値が署名されており、2番目の要素が負の値で表されている場合、そのような見落としはアルゴリズムが無限ループに陥ることになります。2番目の要素は常にその条件を満たすでしょう：
1000 >>1; //
1100 >>1; // ( 0100)
1110 >>1; // 0010
1111 >>1; // -1
分割
アルゴリズム：
private int divide(int dividend, int divisor)
{
/*, .*/
int quotient = 0x00, mask = 0x01;
/* .*/
int temp = divisor;
/* .*/
int sign = ((dividend < 0)^(divisor < 0)) ? sign = -1 : 1;
/* .*/
dividend = dividend < 0 ? add((~dividend), 1) : dividend;
divisor = divisor < 0 ? add((~divisor), 1) : divisor;
/* 0 .*/
if (dividend < divisor) return quotient;
while(dividend > 0 || divisor != 0)
{
/* .*/
if ((dividend >= (divisor << 0x01)) && ((divisor << 0x01) > 0))
{
divisor <<= 0x01;
mask <<= 0x01;
}
/* .*/
else
{
/* "" .*/
quotient = quotient | mask;
/* .*/
dividend = sub(dividend, divisor);
/* .*/
divisor = temp;
mask = 0x01;
}
}
return multiply(quotient, sign);
}
分割は前の例ほどスムーズに機能しませんでした：私は自転車を書かなければなりませんでした（強く打たないでください）。
除算は、商がゼロ以上である限り、被除数から除数を差し引くことです。このアプローチでは、各減算操作の後に値が増分されるカウンターを定義するだけで十分です。その最終的な値は特定のものです：
count = 0;
1) 7 - 3 = 4; count = 1;
2) 4 - 3 = 1; count = 2;
7 / 3 = count;
このアプローチの欠点は、次のような一連の命令の限られたリソースをデバイスに提供する場合に特に顕著になります。 2147483647/2; 2147483647/3、アプリケーションがフリーズしているようです。
ビットレベルでの作業ははるかに効率的です。しかし、見つかった唯一の解決策には、正しい推論のために、カバーされた範囲の1ステップ上の変数のタイプが必要であるという欠点があります。入力が短い場合、ローカル変数のタイプはintである必要があります。そうでない場合、大きな値を分割した結果は驚くべきものになります。私の場合、ロングタイプがないために状況は悪化しました。
しかし、私たちの雄羊に戻ってください。
アルゴリズムがどのように機能するかを理解するには、列の分割順序を覚えておく必要があります。
= 6, = 2;
0110|0010
----
110|10 //
, , :
1) (1 >= 10) -> ,
110|10
--
0
2) (11 >= 10) -> ,
110|10
-10 --
-- 01
01
ここでより詳細に。排気口で、次のことがわかりました。仕切りを左に「押して」放電し、分割可能なものとの差を最小限に抑えました。
2.1) 0110 / 0010 -> 0110 - 0100 = 0010 = 2.
3) (10 >= 10) -> ,
110|10
-10 --
-- 011
010
-10
--
00
このメカニズムは、アルゴリズムに実装されています。while（）ループでは、上記のルールを満たすまで除数を左にシフトする必要があります。それと並行して、プライベートマスクがシフトされます。分岐演算子if（）は、「この操作の結果のみが基本ルールに違反しない場合にシフトできます。」と言います。負の数の追加チェックは、Javaで設定された最上位ビットが負の数であるという事実によるものです。それがないと、サイクルは無限大になります。
//((divisor << 0x01) > 0) ,
1) 0111 >= 0010<<1
2) 0111 >= 0100<<1
3) 0111 >= 1000<<1 //! - if() , , .
4) 0111 >= 0000<<1
....
アルゴリズムがif（）条件を満たさなくなるとすぐに、コードはelseに入ります。ここで、マスクビットが商に設定されます。
quotient = quotient | mask;
0010 = 0000 | 0010
これは、長分割のビットを設定するのと同じです。次に、除数が配当から差し引かれます。
dividend = sub(dividend, divisor);
0010 = 0110 - 0100
その後、仕切りとマスクが元の状態に戻り、サイクルが再開されます。
divisor = temp;
mask = 0x01;
最後に、追加のコードについていくつか説明します。
上記のアルゴリズムは、補完コードによって取得された正の数の除算のみを想定しています。
dividend = dividend < 0 ? add((~dividend), 1) : dividend;
divisor = divisor < 0 ? add((~divisor), 1) : divisor;
ここで、次のことが起こります。数値が負の場合、そのビットが反転され、結果に1が加算され、正の（絶対）値が得られます。同じルールが正の数に適用されます。例：
6 = 0110 -> ~6 = 1001 = 1001 + 1 = 1010 = -6
-6 = 1010 -> ~-6 = 0101 = 0101 + 1 = 0110 = 6
ただし、例外が1つあります。これは、特定のタイプの最大の負の数です。次に例を示します。
int -2147483648 ->
~1000 0000 0000 0000 0000 0000 0000 0000 =
0111 1111 1111 1111 1111 1111 1111 1111 + 1 =
1000 0000 0000 0000 0000 0000 0000 0000.
注意してください。