ما هي الحيل المفيدة لرمز عامل البت التي يجب أن يعرفها المطور؟[مغلق]

Question

يجب أن أقول أنه لم يكن لدي أي سبب لاستخدام معاملات البت، لكنني متأكد من أن هناك بعض العمليات التي أجريتها وكان من الممكن إجراؤها بكفاءة أكبر.كيف ساعدك "التحويل" و"OR-ing" على حل مشكلة ما بشكل أكثر كفاءة؟

Answer 1

وانظر الشهيرة بت Twiddling المأجورون
معظم تتكاثر / تلك الفجوة ليست ضرورية - والمترجم تفعل ذلك تلقائيا وسوف مجرد مجموعة من الناس تخلط بين

ولكن هناك مجموعة من 'شيك / مجموعة / تبديل بت N' الخارقة نوع التي هي مفيدة جدا إذا كنت تعمل مع بروتوكولات الأجهزة أو الاتصالات.

Answer 2

استخدام عمليات البت على السلاسل (الأحرف)

تحويل حرف الى أحرف صغيرة:

• OR بواسطة المسافة => (x | ' ')
• تكون النتيجة دائمًا بأحرف صغيرة حتى لو كان الحرف صغيرًا بالفعل
• على سبيل المثال. ('a' | ' ') => 'a' ; ('A' | ' ') => 'a'

تحويل حرف الى الأحرف الكبيرة:

• AND بواسطة التسطير => (x & '_')
• تكون النتيجة دائمًا بأحرف كبيرة حتى لو كان الحرف كبيرًا بالفعل
• على سبيل المثال. ('a' & '_') => 'A' ; ('A' & '_') => 'A'

عكس حالة الرسالة:

• XOR بمساحة => (x ^ ' ')
• على سبيل المثال. ('a' ^ ' ') => 'A' ; ('A' ^ ' ') => 'a'

حروف موضع في الأبجدية:

• AND بواسطة chr(31)/binary('11111')/(hex('1F') => (x & "\x1F")
• النتيجة في نطاق 1..26، حالة الأحرف ليست مهمة
• على سبيل المثال. ('a' & "\x1F") => 1 ; ('B' & "\x1F") => 2

احصل على خطاب موضع في الأبجدية (ل الأحرف الكبيرة حروف فقط):

• AND بواسطة ? => (x & '?') أو XOR بواسطة @ => (x ^ '@')
• على سبيل المثال. ('C' & '?') => 3 ; ('Z' ^ '@') => 26

احصل على خطاب موضع في الأبجدية (ل أحرف صغيرة حروف فقط):

• XOR بواسطة علامة الظهر/chr(96)/binary('1100000')/hex('60') => (x ^ '`')
• على سبيل المثال. ('d' ^ '`') => 4 ; ('x' ^ '`') => 25

ملحوظة:سيؤدي استخدام أي شيء آخر غير الحروف الإنجليزية إلى نتائج غير مرغوب فيها

Answer 3

---

• عمليات البت على الأعداد الصحيحة (int)

---

الحصول على الحد الأقصى لعدد صحيح

int maxInt = ~(1 << 31);
int maxInt = (1 << 31) - 1;
int maxInt = (1 << -1) - 1;

الحصول على الحد الأدنى لعدد صحيح

int minInt = 1 << 31;
int minInt = 1 << -1;

احصل على الحد الأقصى الطويل

long maxLong = ((long)1 << 127) - 1;

مضروبة في 2

n << 1; // n*2

مقسمة على 2

n >> 1; // n/2

مضروبة في القوة m لـ 2

n << m;

مقسومًا على القوة m لـ 2

n >> m;

التحقق من الرقم الفردي

(n & 1) == 1;

تبادل قيمتين

a ^= b;
b ^= a;
a ^= b;

الحصول على القيمة المطلقة

(n ^ (n >> 31)) - (n >> 31);

احصل على الحد الأقصى لقيمتين

b & ((a-b) >> 31) | a & (~(a-b) >> 31);

احصل على الحد الأدنى من القيمتين

a & ((a-b) >> 31) | b & (~(a-b) >> 31);

تحقق مما إذا كان كلاهما لهما نفس الإشارة

(x ^ y) >= 0;

احسب 2^ن

2 << (n-1);

ما إذا كان مضروبا 2

n > 0 ? (n & (n - 1)) == 0 : false;

مودولو 2 ^ ن ضد م

m & (n - 1);

احصل على المتوسط

(x + y) >> 1;
((x ^ y) >> 1) + (x & y);

احصل على البتة m من n (من الأقل إلى الأعلى)

(n >> (m-1)) & 1;

اضبط البت m-th من n على 0 (من الأقل إلى الأعلى)

n & ~(1 << (m-1));

ن + 1

-~n

ن - 1

~-n

الحصول على رقم التباين

~n + 1;
(n ^ -1) + 1; 

إذا (س==أ) س=ب؛إذا (س==ب) س=أ؛

x = a ^ b ^ x;

Answer 4

هناك ثلاثة فقط استخدمتها بأي تردد:

1. تعيين قليلا:أ |= 1 << بت؛

2. واضح قليلا:&= ~(1 << بت);

3. اختبار أنه تم تعيين قليلا:أ & (1 << بت)؛

Answer 5

المسائل الحسابية:الأفكار، الخوارزميات، الكود المصدري، بقلم يورج أرندت (PDF).يحتوي هذا الكتاب على الكثير من الأشياء، وجدته عبر الرابط في http://www.hackersdelight.org/

متوسط ​​بدون تجاوز

روتين لحساب المتوسط ​​(x + y)/2 من وسيطين x و y

static inline ulong average(ulong x, ulong y)
// Return floor( (x+y)/2 )
// Use: x+y == ((x&y)<<1) + (x^y)
// that is: sum == carries + sum_without_carries
{
    return (x & y) + ((x ^ y) >> 1);
}

Answer 6

يمكنك ضغط البيانات، على سبيل المثال.مجموعة من الأعداد الصحيحة:

• تعرف على القيم الصحيحة التي تظهر بشكل متكرر في المجموعة
• استخدم تسلسلات بت قصيرة لتمثيل القيم التي تظهر بشكل متكرر (وتسلسلات البت الأطول لتمثيل القيم التي تظهر بشكل أقل تكرارًا)
• تسلسل تسلسل البتات:على سبيل المثال، قد تمثل البتات الثلاثة الأولى في تدفق البتات الناتج عددًا صحيحًا واحدًا، ثم تمثل البتات التسعة التالية عددًا صحيحًا آخر، وما إلى ذلك.

Answer 7

1) تقسيم / ضرب من قبل قوة من 2

وfoo >>= x; (القسمة على قوة 2)

وfoo <<= x; (ضرب من قبل قوة 2)

2) مبادله

x ^= y;
y = x ^ y;
x ^= y;

Answer 8

واعتدت مشغلي المختصة بالبت في تنفيذ بكفاءة الحسابات عن بعد ل bitstrings . في بلدي bitstrings تطبيق استخدمت لتمثيل المواقف في الفضاء discretised (وهي octree ، إذا كنت ' إعادة المهتمة، المشفرة مع مورتون ترتيب ). هناك حاجة حسابات المسافة إلى معرفة ما إذا كانت نقطة على الشبكة تقع ضمن دائرة نصف قطرها معينة.

Answer 9

وعد مجموعة بت، وإيجاد أدنى / أعلى مجموعة قليلا، وإيجاد نطة-من-أعلى / أسفل قليلا مجموعة وغيرها يمكن أن تكون مفيدة، وأنه يستحق النظر في في الخارقة-twiddling قليلا الموقع.

وقال ان هذا النوع من الشيء ليس يوما بعد يوم مهم. من المفيد أن يكون مكتبة، ولكن حتى ذلك الحين معظم الاستخدامات شيوعا هي غير مباشر (على سبيل المثال باستخدام الحاويات bitset). أيضا، من الناحية المثالية، هذه ستكون وظائف مكتبة القياسية - يتم التعامل مع الكثير منهم أفضل باستخدام إرشادات تتخصص وحدة المعالجة المركزية على بعض الأنظمة الأساسية

Answer 10

وحين ضرب / قسمة التحول يبدو أنيق، والشيء الوحيد الذي أنا في حاجة مرة واحدة في حين ضغط القيم المنطقية نتفا. لذلك تحتاج أحادي المعامل AND / OR، وربما قليلا تحويل / انقلاب.

Answer 11

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

i--;
i |= i >> 1;
i |= i >> 2;
i |= i >> 4;
i |= i >> 8;
i |= i >> 16;
i++;

وأنا استخدامها على نوع size_t. ربما لن يلعب بشكل جيد على أنواع الموقعة. إذا كنت قلقا حول قابلية لمنصات مع أنواع مختلفة الحجم، ويرش التعليمات البرمجية مع توجيهات #if SIZE_MAX >= (number) في الأماكن المناسبة.