نادرًا ، ولكن لا تزال مهام المقابلات والتدريب ذات قيمة عملية. لذلك ، كنت بحاجة إلى تطبيق في Java بديلاً للعمليات الحسابية على القيم الصحيحة. لحسن الحظ ، الصفحات الأولى من محركات البحث مليئة بالحلول الجاهزة للنظائر الحكيمة ، ولم يكن عليك أن تكسر رأسك فوق معظمها.
بصراحة ، لقد فوجئت إلى حد ما بعدم وجود مثل هذه المواد عن حبري (هل أبدو سيئًا؟) ، وبالتالي قررت ملء هذا النقص بتعليقاتي وإضافاتي.
يرجى ملاحظة أنه في الأمثلة ذات العمليات الأحادية ، يتم اقتطاع القيم إلى nibble: لن يكون هناك فرق جوهري ، ولكن يسهل فهمه.
إضافة
الخوارزمية:
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 إلى 18:
109 +
019 =
128
في النظام الثنائي ، يتم نقل كل ما هو أكبر من واحد:
0001 +
0001 =
----
0010
او مثل هذا:
0011 +
0011 =
----
0110
في المثال الأخير ، تمت إضافة البتات الأقل أهمية أولاً:
1 + 1 = 10 ()
يبقى الصفر في البت الحالي ، وينتقل الآخر إلى الجزء الأكثر أهمية ، حيث يشارك بالإضافة إلى ذلك:
1 + 1 + 1 = 11 ()
يبقى الأدنى في المستوى الحالي ، والأقدم يتحرك أكثر. من هنا ، يمكنك استنتاج القاعدة القائلة بأنه في النظام الثنائي لبت واحد حالي ، فإن القيم من اثنين إلى ثلاثة ، شاملة ، تندرج تحت الحمل.
في الجزء المتعلق بالخوارزمية ، يجدر الانتباه إلى التعليمات الخاصة بتحديد وجود / غياب النقل باستخدام مثال القيم السابقة:
carry = (summand & addend);
0011 = 0011 & 0011
هذا ليس نقلًا بعد ، ولكن وضع "العلامات" فوق الأرقام ، والتي تؤدي إضافتها إلى ترك النقل ، أي إضافة الحمل عندما تكون البتات هي نفسها.
بمجرد أن يتم مسح شيء ما بالفعل ، الآن يجب تحرير المصطلح الأول من البتات التي يتم أخذ التحويل في الاعتبار:
summand = summand ^ addend;
0000 = 0011 ^ 0011
كما تعلم ، فإن عامل تشغيل أحادي الاتجاه XOR سيعين البتات فقط إذا كانت قيم البت معاكسة.
الخطوة الثالثة في الحلقة هي تحويل أعلام الحمل مباشرة إلى حمل. للقيام بذلك ، يتم نقلهم خطوة واحدة إلى اليسار ويتم تعيينهم إلى المصطلح الثاني:
addend = (carry << 1);
0110 = (0011 << 1);
في التكرار التالي ، لن يتم إصلاح النقل ، للأسباب التالية:
carry = (summand & addend);
0000 = 0000 & 0110
الخطوة الثانية سوف تعطينا:
summand = summand ^ addend;
0110 = 0000 ^ 0110,
ما هو المبلغ المطلوب ، وستنتهي الخطوة الثالثة حلقة 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;
}
العودة إلى الأساسيات: الضرب المطول في النظام العشري:
25 *
05 =
--
125 +
00
---
125
أولئك. نضرب كل رقم من العامل الثاني في العامل الأول. من هنا يترتب على ذلك أن المنتج من أهم بت يتم إزاحته خطوة واحدة إلى اليسار. أخيرًا ، أضف القيم الوسيطة. يحدث نفس الشيء على مستوى البت:
0110 *
0011 =
----
0110 +
0 110 +
00 00 +
000 0 +
- ----
1 0010
نستنتج أن الخوارزمية يجب أن تقوم فقط ، بإضافة العامل الأول لنفسها كلما تمت مصادفة بت معين في العامل الثاني ، بالطبع ، مع مراعاة قاعدة النقل إلى البت الأكثر أهمية:
if ((mul2 & 1) == 1) //(0011 & 0001) == 0001
{
result = add(result, mul1); //0110 = 0000 + 0110
}
ثم يتم إزاحة المضاعف الأول قليلاً إلى اليسار (نشكل "سلمًا"):
mul1 <<= 1; //1100 = 0110 << 1;
نحدد الآن ما إذا كان هناك جزء صغير في ثاني أهم جزء من العامل الثاني:
mul2 >>>= 1; //0001 = 0011 >>> 1;
تستمر الدورة حتى يصبح العامل الثاني صفرًا. أود أن ألفت انتباهكم إلى ما يلي: مثال لهذه الخوارزمية يسير من مورد إلى مورد ، حيث يتم استبدال التحول المنطقي للعامل الثاني (mul2 >>> = 1) بعامل حسابي (mul2 >> = 1) . ربما نشأ من التنفيذ في C / C ++ ، حيث توجد كلمة أساسية غير موقعة وهذا الاستبدال ليس مشكلة. ومع ذلك ، في Java يتم توقيع جميع أنواع الأرقام ، وإذا تم تمثيل العامل الثاني بقيمة سالبة ، فإن مثل هذا الخطأ سيؤدي إلى سقوط الخوارزمية في حلقة لا نهائية ، حيث العامل الثاني سوف يفي دائمًا بشرطه:
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/1؛ 2147483647/2 ؛ 2147483647/3 ، يبدو أن التطبيق متجمد.
سيكون العمل على مستوى البت أكثر كفاءة. لكن الحل الوحيد الذي تم العثور عليه له عيب وهو أنه بالنسبة للاستدلال الصحيح ، فإن نوع المتغيرات مطلوب ، خطوة واحدة فوق النطاق المغطى ، أي إذا كان الإدخال قصيرًا ، فيجب أن يكون نوع المتغيرات المحلية صحيحًا ، وإلا فإن نتيجة تقسيم القيم الكبيرة ستكون مفاجئة. في حالتي ، تفاقم الوضع بغياب النوع الطويل.
لكن عد إلى كباشنا.
لفهم كيفية عمل الخوارزمية ، عليك أن تتذكر ترتيب تقسيم العمود:
= 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
يتم تنفيذ هذه الآلية في الخوارزمية. في حلقة () ، يجب أن يتحول المقسوم عليه إلى اليسار حتى يفي بالقاعدة المذكورة أعلاه. بالتوازي معها ، يتم إزاحة القناع الخاص. عامل التشغيل التفريعي إذا () يقول: "يمكنك التحويل إذا كانت نتيجة هذه العملية فقط لا تنتهك القاعدة الأساسية." التحقق الإضافي من الرقم السالب يرجع إلى حقيقة أن مجموعة البت الأكثر أهمية في Java هي رقم سالب. بدونها ، ستنخفض الدورة إلى ما لا نهاية:
//((divisor << 0x01) > 0) ,
1) 0111 >= 0010<<1
2) 0111 >= 0100<<1
3) 0111 >= 1000<<1 //! - if() , , .
4) 0111 >= 0000<<1
....
بمجرد أن تتوقف الخوارزمية عن تلبية شروط if () ، تدخل الكود الآخر ، حيث يتم تعيين بت القناع على حاصل القسمة:
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;
هنا يحدث ما يلي: إذا كان الرقم سالبًا ، فعكس بتاته ، وتضاف النتيجة بواحد ونحصل على قيمة موجبة (مطلقة). تنطبق نفس القاعدة على الأرقام الموجبة ، على سبيل المثال:
6 = 0110 -> ~6 = 1001 = 1001 + 1 = 1010 = -6
-6 = 1010 -> ~-6 = 0101 = 0101 + 1 = 0110 = 6
لكن هناك استثناء واحد - هذا هو أكبر رقم سلبي لنوع معين ، على سبيل المثال:
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.
كن حذرا.