لماذا (أ | ب) أي ما يعادل - (أ و ب) + (ب)؟

Question

وكنت أبحث عن وسيلة للقيام BITOR () مع قاعدة بيانات أوراكل، وجاءت عبر اقتراح لمجرد استخدام BITAND () بدلا من ذلك، استبدال BITOR (أ، ب) مع + ب - BITAND (أ، ب) .

واختبرت باليد عدة مرات والتحقق منها على ما يبدو للعمل لجميع الأرقام الثنائية كنت أفكر فيه، ولكن لا أستطيع أن أفكر من البرهان الرياضي السريع لماذا هذا هو الصحيح.
يمكن لأي شخص أن تنورني؟

Answer 1

وA & B هو مجموعة من البتات التي هي على حد سواء في A و B. A - (A & B) يترك لك مع كل هذه البتات التي هي فقط على في A. B اضافة الى ذلك، وتحصل على كل بت التي هي على في (أ) أو تلك التي هي على في B.

وسوف إضافة بسيطة من ألف وباء لا تعمل بسبب تحمل على حد سواء حيث يكون قليلا 1. عن طريق إزالة أجزاء مشتركة لA و B لأول مرة، ونحن نعلم أن (A- (A & B)) لن يكون هناك بت من القواسم المشتركة مع B، لذا إضافتها معا ويضمن عدم إنتاج حمل.

Answer 2

وتخيل لديك اثنين من الأرقام الثنائية: a وb. ودعونا نقول ان هذه العدد أبدا أن يكون 1 في نفس الشيء في نفس الوقت، أي إذا a لديه 1 في بعض الشيء، وb دائما 0 في بت المقابلة. وفي الاتجاه الآخر، إذا b لديه 1 في بعض الشيء، ثم a دائما 0 في هذا الشيء. على سبيل المثال

a = 00100011
b = 11000100

وهذا من شأنه أن يكون مثالا للa وb تلبية الشرط أعلاه. في هذه الحالة فمن السهل أن نرى أن ذلك a | b يكون بالضبط نفس a + b.

a | b = 11100111
a + b = 11100111

ودعونا الآن اتخاذ رقمين التي تنتهك حالتنا، أي رقمين لديك واحد على الأقل 1 في بعض الشيء المشترك

a = 00100111
b = 11000100

هل a | b نفس a + b في هذه الحالة؟ لا

a | b = 11100111
a + b = 11101011

لماذا هم مختلفة؟ فهي مختلفة لأننا عندما + بت التي لديها 1 من حيث العدد، ونحن ننتج ما يسمى <م> حمل : بت الناتج هو 0، ويتم 1 إلى بت المقبل إلى اليسار: 1 + 1 = 10. | العملية لا يوجد حمل، لذلك 1 | 1 مرة أخرى فقط 1.

وهذا يعني أن الفرق بين a | b وa + b يحدث عندما وفقط عندما تكون الأرقام لها واحد على الأقل 1 في الشيء المشترك. عندما كنا خلاصة القول رقمين مع 1 في بت المشتركة، والحصول على إضافة هذه القطع المشتركة "مرتين" وينتج حمل، والذي يدمر التشابه بين a | b وa + b.

والآن ننظر في a & b. ماذا حساب a & b؟ تنتج a & b الرقم الذي لديه 1 في كل بت على حد سواء حيث a وb ديك 1. في أحدث مثال لدينا

a =     00100111
b =     11000100
a & b = 00000100

وكما رأيت آنفا، وهذه هي بالضبط البتات التي تجعل a + b تختلف عن a | b. 1 في a & b تشير جميع المواقف التي سوف تحدث حمل.

والآن، عندما نفعل نحن a - (a & b) فعال <م> إزالة (طرح) عن "المخالف" بت من a وفقط هذه البتات

a - (a & b) = 00100011

وأرقام a - (a & b) وb ليس لديهم 1 بت المشتركة، مما يعني أنه إذا أضفنا a - (a & b) وb نحن لن تصل الى حمل، وإذا كنت تفكر في ذلك، يجب علينا في نهاية المطاف مع نفس النتيجة كما لو كنا فقط لم a | b

a - (a & b) + b = 11100111

Answer 3

وA & B = C حيث ترك أي بت في مجموعة C هي تلك المنصوص عليها في كل من A و B. في
إما A-C = D أو B-C مجموعات = E فقط هذه القطع المشتركة إلى 0. لا يوجد تأثير تحمل ل1/1 = 0.
D + B أو E + A يشبه إلى A + B إلا أن لأننا طرح A & B سابقا لن يكون هناك حمل نظرا لبعد أن أخلى كل مجموعة عادة بت في D أو E.

والنتيجة النهائية هي أن A-A & B + B أو B-A & B + A ما يعادل A |. B

وإليك جدول الحقيقة اذا كان لا يزال مربكا:

 A | B | OR   A | B | &    A | B | -    A | B | + 
---+---+---- ---+---+---  ---+---+---  ---+---+---
 0 | 0 | 0    0 | 0 | 0    0 | 0 | 0    0 | 0 | 0  
 0 | 1 | 1    0 | 1 | 0    0 | 1 | 0-1  0 | 1 | 1
 1 | 0 | 1    1 | 0 | 0    1 | 0 | 1    1 | 0 | 1  
 1 | 1 | 1    1 | 1 | 1    1 | 1 | 0    1 | 1 | 1+1

لاحظ الصفوف تحمل في + و- العمليات، نتجنب تلك لA- (A & B) تحدد الحالات كانت كل بت في A و B 1-0 في A، ثم إضافتها مرة أخرى من B يجلب أيضا في الآخر وكانت الحالات كان هناك 1 في إما A أو B ولكن ليس حيث كان كل من 0، وبالتالي فإن جدول الحقيقة OR وA- (A & B) + جدول B الحقيقة متطابقة.

وهناك طريقة أخرى لمقلة العين ذلك هو أن نرى أن A + B هو تقريبا مثل A | B باستثناء تحمل في الصف السفلي. A & B يعزل هذا الصف السفلي بالنسبة لنا، A-A & B يتحرك تلك معزولة فتش عن صفين في الجدول +، و(A-A & B) + B يصبح يعادل A |. B

وبينما كنت يمكن تخفيف هذا إلى A + B- (A & B)، وأنا خائفة من تجاوز محتمل لكن ذلك كان غير مبرر على ما يبدو:

#include <stdio.h>
int main(){ unsigned int a=0xC0000000, b=0xA0000000;
printf("%x %x %x %x\n",a,   b,       a|b,       a&b);
printf("%x %x %x %x\n",a+b, a-(a&b), a-(a&b)+b, a+b-(a&b)); }

c0000000 a0000000 e0000000 80000000
60000000 40000000 e0000000 e0000000

تحرير : لذلك أنا كتبت هذا قبل كانت هناك أجوبة، بعد ذلك كان هناك بعض 2 ساعة من الوقت لأسفل على ارتباطي المنزل، وأنا في النهاية تمكن من الرد على ذلك، يلاحظ فقط بعد ذلك أنه سوف تم الإجابة بشكل صحيح مرتين. شخصيا انا افضل اشارة الى جدول الحقيقة للعمل على العمليات المختصة بالبت، لذلك سأترك ذلك في حالة أنه يساعد شخص ما.

Answer 4