Bit Manipulationbinary · AND OR XOR NOT shifts · 32-bit JS · x & (x − 1) · x & −x · XOR · bitmasks

كل رقم جوه الكمبيوتر صف من 0 و 1. لما تشتغل على الصف ده مباشرة، حاجات كانت محتاجة hash map أو loop بتتحل في سطر، وبـ O(1) memory. الفصل ده بيعلّمك الـ operators، والفخاخ بتاعتها في JS، وخمس حيل بتتكرر في كل مسائل الـ bits.

قبله: Greedy و Big-O بيمهّد لـ: خطة الانترفيو

هتطلع من الفصل ده وإنت عارف

  • تقرا أي رقم صغير بالـ binary في دماغك، وتعرف كل bit قيمته كام.
  • AND و OR و XOR و NOT و << و >> و >>>، والفخ بتاع الـ 32-bit signed في JS، وإمتى تكتب >>> 0.
  • الحيل: x & 1، و x & (x - 1)، و x & -x، و XOR بيلغي الأزواج، وإزاي رقم يمثّل set.
  • تحل Single Number و Missing Number و Number of 1 Bits و Power of Two و Counting Bits و Reverse Bits و Subsets بالـ bitmask.

الرقم من جوه: binary

في الفصل اللي فات كنا بناخد قرارات على الأرقام كقيم. هنا آخر أداة في الدليل: بدل ما تبص للرقم كقيمة، هتبص لـ الـ 0 و 1 اللي جواه.

في الـ decimal كل خانة قيمتها 10 أضعاف اللي على يمينها: آحاد، عشرات، مئات. في الـ binary كل خانة قيمتها ضعف اللي على يمينها: 1، 2، 4، 8، 16... وكل خانة فيها 0 أو 1 بس. الخانة دي اسمها bit، وبنرقّمها من اليمين: bit 0 هو خانة الـ 1، و bit 3 هو خانة الـ 8.

تشبيه صف لمبات في عمارة، كل لمبة مكتوب جنبها رقم: 128، 64، 32، 16، 8، 4، 2، 1. الرقم اللي العمارة بتمثّله هو مجموع أرقام اللمبات المنوّرة بس. 13 يعني لمبة الـ 8 ولمبة الـ 4 ولمبة الـ 1 منوّرين، والباقي طافي.

بص إزاي 13 بيتكتب: من الخانة الكبيرة للصغيرة، لو الخانة تكفّي الباقي نولّعها ونطرحها:

لاحظ إنها نفس فكرة الكاشير من فصل الـ greedy: أكبر خانة تكفّي الأول. وهنا الـ greedy دايمًا صح، لأن كل خانة أكبر من مجموع كل اللي على يمينها (8 > 4 + 2 + 1).

طب إزاي تعرف إن المسألة عايزة bits؟ ده الجزء الجاي.

إزاي تعرفه من المسألة

لما تشوف: every element appears twice except onewithout extra spacepower of twocount set bits binary representationXORmissing number in 0..nall subsets, n ≤ 20without + or *
ومش هو غالبًا لو: أرقام أكبر من 2³¹ في JSappears k times مع k كبيرعمليات حسابية عادية بتكفّي وأوضح

الـ bits بتظهر في نوعين من المسائل: يا المسألة عن الـ bits نفسها (عدّها، اقلبها)، يا حيلة bit بتوفّر memory (XOR بدل hash set). والإشارة الأقوى للنوع التاني: "O(1) extra space" في مسألة حلها الطبيعي Set.

الحيلةبتعمل إيهمسائل
a ^ a = 0الأزواج بتلغي بعضSingle Number، Missing Number
x & (x - 1)بتطفي أوطى bit منوّرNumber of 1 Bits، Power of Two
x & -xبتسيب أوطى bit منوّر لوحدهSingle Number III، Fenwick tree
x >> 1، x & 1نص الرقم، وآخر bitCounting Bits، Reverse Bits
mask & (1 << i)الرقم كـ set: bit i منوّر = العنصر i موجودSubsets، bitmask DP

قبل الحيل، لازم تعرف الأدوات نفسها: الـ operators.

الـ operators: AND و OR و XOR و NOT والـ shifts

كل operator بيشتغل على كل bit لوحده: bit 0 مع bit 0، و bit 1 مع bit 1، وهكذا. مفيش "شيل" زي الجمع.

aba & b (AND)a | b (OR)a ^ b (XOR)
00000
01011
10011
11110

احفظها كده: AND = "الاتنين"، OR = "واحد على الأقل"، XOR = "مختلفين". والـ XOR كمان = جمع من غير شيل.

  1. AND بيستخدم كـ فلتر (mask): x & 1 بيسيب آخر bit بس، والباقي يتصفّر.
  2. OR بيستخدم عشان تولّع bit: x | (1 << i).
  3. XOR بيستخدم عشان تقلب bit: x ^ (1 << i)، أو عشان تلغي الأزواج.
  4. NOT بيقلب كل الـ 32 bit، مش الـ 4 بتوع 1100 بس، فالنتيجة سالبة. ده الجزء الجاي.
  5. كل خانة لليمين قيمتها ضعف، فالزق للشمال بخانة = × 2، وبيدخل 0 من اليمين.
  6. الزق لليمين بيرمي آخر bits. 12 >> 2 = Math.floor(12 / 4) = 3. ده اللي استخدمناه في (lo + hi) >> 1 في الـ binary search والـ heap.

ليه ~12 طلعت -13؟ ده محتاج نفهم JS بتخزّن السالب إزاي.

فخ JS: الـ bits دايمًا 32-bit signed

الأرقام في JS أصلًا doubles (64-bit floating point). بس أول ما تستخدم أي bit operator، JS بتحوّل الرقم لـ 32-bit signed integer، تعمل العملية، وترجّع النتيجة 32-bit signed. معنى كده حاجتين:

  1. bit 31 هو الإشارة: لو منوّر الرقم سالب. والسالب متخزّن بطريقة اسمها two's complement: -x هو ~x + 1. يعني -1 كل الـ 32 bit فيه منوّرين.
  2. أي حاجة فوق 32 bit بتترمي: رقم زي 3 مليار مش هيدخل، وهيتحوّل لرقم سالب غريب.
  1. أكبر bit (31) لما يتولّع الرقم يبقى سالب. عشان كده 1 << 31 سالب، و 1 << 32 بيطلع 1 (الـ shift بيتعمل % 32).
  2. من الـ two's complement: -x = ~x + 1، يعني ~x = -x - 1. احفظها كده وخلاص.
  3. الفرق المهم: >> بيحافظ على الإشارة (سالب يفضل سالب)، و >>> بيدخّل أصفار دايمًا (unsigned shift). لو بتلف على bits رقم ممكن يكون سالب، استخدم >>>.
  4. x >>> 0 مبيحرّكش حاجة، بس النتيجة بتتقري unsigned. دي الطريقة اللي بترجّع بيها رقم 32-bit "موجب" لما المسألة عايزة unsigned.
  5. رقم أكبر من 32 bit بيتقص. عشان كده x | 0 للـ floor خطر على الأرقام الكبيرة.
  6. toString(2) على سالب بيحط علامة سالب قدام الـ binary بتاع القيمة المطلقة. عشان تشوف الـ bits الحقيقية، حوّل لـ unsigned الأول.

الـ 32 bit كتير على الرسمة، فالـ animation دي بتعمل نفس الحاجة على 8 bits بس (نفس القواعد بالظبط، bit 7 هو الإشارة):

لو محتاج أكتر من 32 bit استخدم BigInt: (1n << 40n) شغالة. أو استخدم الحساب العادي: 2 ** 40 و Math.floor(x / 2). في مسائل LeetCode اللي فيها int عادي، الـ 32 bit كفاية.

كده عندك الأدوات وفخاخها. يلا للحيل اللي بتتكرر في كل المسائل.

الحيل الأساسية

  1. bit 0 هو خانة الـ 1، وكل الخانات التانية زوجية (2، 4، 8...). فالرقم فردي لو bit 0 منوّر. أسرع من x % 2، والأهم إنه صح مع السالب (-3 % 2 بـ -1 مش 1).
  2. ليه بتطفي أوطى bit؟ الـ - 1 بيستلف من أوطى 1: بيطفيه، وبيولّع كل الأصفار اللي على يمينه. فالـ AND بيصفّر الحتة دي كلها، والباقي فوق زي ما هو.
  3. -x = ~x + 1: الـ ~ بيقلب كل حاجة، والـ + 1 بيرجّع أوطى 1 بس لمكانه. فالـ AND بيلاقي bit واحد مشترك.
  4. XOR أي رقم مع نفسه صفر، ومع الصفر هو نفسه، والترتيب مش فارق. فأي رقم متكرر مرتين بيختفي.
  5. التلاتة دول هتستخدمهم كتير: 1 << i هو mask فيه bit i بس، و AND يقرا، و OR يولّع، و AND مع NOT يطفي.

1. x & 1: فردي ولا زوجي

2. x & (x - 1): اطفي أوطى bit منوّر

كرر الحيلة لحد ما الرقم يبقى صفر، وعدّ: كده عرفت عدد الـ bits المنوّرة.

3. x & -x: سيب أوطى bit منوّر لوحده

4. XOR بيلغي الأزواج

أول مسألة: XOR على array كاملة.

مثال محلول 1: Single Number

Single Number

easyLeetCode 136

كل رقم في الـ array موجود مرتين، ما عدا رقم واحد موجود مرة. رجّعه، في O(n) وقت و O(1) memory.

Input: nums = [7, 3, 5, 3, 7] Output: 5

نفكّر فيها مع بعض

  1. أول حل: Map يعدّ، أو Set تضيف وتشيل. O(n) وقت، بس O(n) memory، والمسألة عايزة O(1).
  2. الـ key insight: XOR الأرقام كلها. كل زوج بيلغي نفسه (a ^ a = 0)، والترتيب مش فارق، فاللي بيفضل هو الرقم اللي مالوش زوج.
  3. ليه الترتيب مش فارق؟ XOR بيشتغل على كل bit لوحده، وكل bit بيتقلب مرة لكل رقم فيه الـ bit ده. فالنتيجة عند كل bit = هل عدد الأرقام اللي فيها الـ bit ده فردي؟ الأزواج بتدّي عدد زوجي دايمًا.
  4. الحالات الطرفية: عنصر واحد، أرقام سالبة (XOR شغال عادي على الـ two's complement).
  1. 0 هو الـ "محايد" بتاع XOR زي ما 0 محايد للجمع. لو بدأت بـ nums[0] لازم الـ loop تبدأ من 1.
  2. بعد أول 7، الـ acc فيه 7. لما تيجي الـ 7 التانية، بتلغيها في أي وقت جت.
  3. مفيش أي data structure، والـ memory O(1).

التعقيد: O(n) وقت و O(1) memory.

هنا الأزواج كانت جوه نفس الـ array. طب لو الأزواج نعملها إحنا، بين الـ indices والقيم؟

مثال محلول 2: Missing Number

Missing Number

easyLeetCode 268

عندك n رقم مختلفين من الرينج 0..n (يعني n + 1 رقم ممكن). رقم واحد ناقص. هو مين؟

Input: nums = [3, 0, 4, 1] (n = 4, range 0..4) Output: 2

نفكّر فيها مع بعض

  1. الجديد هنا: مفيش أزواج جاهزة. إحنا اللي بنعمل الزوج: كل رقم من 0 لـ n يدخل مرة كـ "المفروض يبقى موجود"، ومرة كـ "موجود فعلًا".
  2. حل بالجمع: مجموع 0..n هو n(n + 1) / 2، اطرح منه مجموع الـ array. ده صح وسهل، وفي JS مفيش overflow هنا.
  3. حل بالـ XOR: XOR كل الأرقام من 0 لـ n، و XOR كل الـ array. كل رقم موجود بيظهر مرتين ويلغي نفسه، والناقص بيظهر مرة.
  4. الحيلة: الـ indices من 0 لـ n - 1 بتدّيك تقريبًا الرينج كله، وناقص n بس. فنبدأ الـ acc بـ n.
  1. ليه nums.length؟ الرينج 0..n فيه n + 1 رقم، والـ indices بتغطي 0..n-1 بس. الـ n الناقص بنحطه من الأول.
  2. i < nums.length عادي، لأن الـ indices هي اللي بنلف عليها.
  3. بندخّل الـ index والقيمة في نفس اللفة. الترتيب مش فارق، فالـ 3 اللي في index 0 هتلاقي الـ index 3 بعدين.

التعقيد: O(n) وقت و O(1) memory.

الـ XOR خلص شغله. الحيلة الجاية بتشتغل على bits الرقم الواحد: نعدّهم.

مثال محلول 3: Number of 1 Bits

Number of 1 Bits

easyLeetCode 191

رجّع عدد الـ bits المنوّرة (الـ 1s) في رقم موجب. الرقم ده اسمه كمان popcount أو Hamming weight.

Input: n = 52 (110100) Output: 3

نفكّر فيها مع بعض

  1. الجديد هنا: loop بتطفي bit في كل لفة، فعدد اللفات = عدد الـ 1s بالظبط.
  2. أول حل: بص على آخر bit (n & 1) وزق لليمين (n >>>= 1)، 32 مرة بالكتير. ده صح وكويس.
  3. أحسن شوية: n &= n - 1 بتطفي أوطى 1 مرة واحدة، وبتنط فوق الأصفار. فلو الرقم فيه 3 bits منوّرين، 3 لفات بس مهما كان طوله.
  1. !== 0 مش > 0: لو الرقم bit 31 فيه منوّر، بعد أول & هيبقى سالب في JS، و > 0 هيوقف بدري.
  2. نفس الحيلة 2. كل لفة الرقم بيخسر bit منوّر واحد بالظبط.
  3. فعدد اللفات هو الإجابة.

التعقيد: O(عدد الـ 1s) للأول، و O(32) للتاني. الاتنين O(1) عمليًا.

لو عدد الـ 1s طلع واحد بالظبط، الرقم ده شكله إيه؟ ده المثال الجاي في سطر واحد.

مثال محلول 4: Power of Two

Power of Two

easyLeetCode 231

هل n قوة لـ 2 (1، 2، 4، 8، ...)؟ الـ n ممكن يكون صفر أو سالب.

Input: n = 16 → true Input: n = 12 → false Input: n = 0 → false

نفكّر فيها مع بعض

  1. الجديد هنا: نفس حيلة n & (n - 1)، بس كاختبار في سطر واحد بدل loop.
  2. الـ key insight: قوة الـ 2 فيها bit واحد بس منوّر (16 = 10000). فلو طفّينا أوطى bit، لازم يفضل صفر.
  3. الحالات الطرفية: n = 0: 0 & -1 = 0 فهيقول true غلط، عشان كده n > 0 الأول. والسالب كمان مش قوة لـ 2.
  1. المسألة بتقول إن n ممكن يبقى صفر أو سالب، والاتنين مش قوة لـ 2.
  2. n > 0 الأول: لو false، الـ && بتقف وترجّع false. من غيره 0 & -1 = 0 وهيقول true.
  3. القوسين حوالين n & (n - 1) مش ديكور. في JS الـ === أقوى من الـ &، فمن غيرهم السطر بيتقري n & ((n - 1) === 0)، وده بيرجّع 0 لكل n أكبر من 1، حتى 16.

التعقيد: O(1).

طب لو عايز عدد الـ 1s لكل رقم من 0 لـ n، مش لرقم واحد؟ ممكن نستخدم إجابات الأرقام الأصغر.

مثال محلول 5: Counting Bits

Counting Bits

easyLeetCode 338

رجّع array طولها n + 1، الخانة i فيها عدد الـ 1s في i، لكل i من 0 لـ n.

Input: n = 8 Output: [0, 1, 1, 2, 1, 2, 2, 3, 1]

نفكّر فيها مع بعض

  1. الجديد هنا: bits + DP: إجابة i مبنية على إجابة رقم أصغر محسوب خلاص.
  2. أول حل: hammingWeight لكل رقم: O(n × 32) أو O(n log n). شغال، بس المسألة بتطلب O(n).
  3. الـ key insight: i >> 1 هو i من غير آخر bit. يعني bits الـ i = bits الـ i >> 1 + آخر bit (i & 1). و i >> 1 أصغر من i، فإجابته محسوبة خلاص.
  4. مثال: 6 = 110. الـ 6 >> 1 = 3 = 11 فيه 2، وآخر bit في 6 صفر، فالإجابة 2.
  1. n + 1 مش n: الأرقام من 0 لـ n عددها n + 1. ده نفس فخ FizzBuzz: الرينج inclusive.
  2. i <= n مش i < n: الـ n نفسها مطلوبة. ونبدأ من 1 لأن dp[0] = 0 جاهزة من الـ fill.
  3. القوسين حوالين (i & 1) لازم، لأن الـ + أقوى من الـ &. من غيرهم السطر بيتقري (dp[i >> 1] + i) & 1.

التعقيد: O(n) وقت، والـ memory هي الإجابة نفسها.

لحد دلوقتي كنا بنقرا الـ bits. المثال الجاي بيبني رقم جديد bit bit.

مثال محلول 6: Reverse Bits

Reverse Bits

easyLeetCode 190

اقلب ترتيب الـ 32 bit بتوع رقم: bit 0 يبقى bit 31، و bit 1 يبقى bit 30، وهكذا. الرقم والنتيجة unsigned.

Input: n = 1 (000...0001) Output: 2147483648 (100...0000)

نفكّر فيها مع بعض

  1. الجديد هنا: بنبني رقم من الصفر: كل لفة نزق النتيجة خانة شمال ونحط bit جديد في الآخر. وبعدين نصلّح الإشارة بـ >>> 0.
  2. الـ key insight: آخر bit في n لازم يبقى أول bit في النتيجة. لو أخدنا bits الـ n من اليمين واحد واحد، وكل مرة زقّينا النتيجة شمال وحطينا الـ bit في آخرها، أول bit دخل هيتزق 31 مرة ويوصل لأقصى الشمال.
  3. الفخ: بعد 32 لفة، bit 31 في النتيجة ممكن يكون منوّر، فـ JS هتقراها سالبة. >>> 0 في الآخر بتقراها unsigned.
  1. i < 32: 32 لفة بالظبط، حتى لو n بقى صفر بدري، لأن الأصفار لازم تتحط برضه عشان النتيجة تتزق لمكانها.
  2. res << 1 بيعمل خانة فاضية (0) على اليمين، و | (n & 1) بيحط فيها آخر bit من n.
  3. >>> مش >>: لو n جه أكبر من 2³¹، الـ >> هيدخّل 1s من الشمال ويبوّظ الـ bits.
  4. من غير >>> 0، أي نتيجة bit 31 فيها منوّر هتطلع سالبة، والـ judge هيقول Wrong Answer.

الـ animation بتشغّل نفس الكود على 8 bits بدل 32 عشان يكفّي في الشاشة:

التعقيد: 32 لفة دايمًا: O(1).

آخر فكرة: رقم ممكن يمثّل set. كل bit منوّر = عنصر موجود.

مثال محلول 7: Subsets بالـ bitmask

Subsets

mediumLeetCode 78

رجّع كل الـ subsets بتاعة array أرقامها مختلفة، بأي ترتيب.

Input: nums = [1, 2, 3] Output: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

حليناها في فصل الـ backtracking بـ recursion: لكل عنصر "آخده ولا لأ". هنا نفس القرار، بس متخزّن في bits.

نفكّر فيها مع بعض

  1. الجديد هنا: الرقم مش قيمة، الرقم set. لو n = 3، أي رقم من 0 لـ 7 (3 bits) بيوصف subset: bit i منوّر يعني nums[i] موجود.
  2. ليه بالظبط 2ⁿ؟ كل عنصر ليه اختيارين، فـ 2 × 2 × 2 = 8. والأرقام من 0 لـ 2ⁿ - 1 هي كل الـ combinations بتاعة n bits، كل واحدة مرة.
  3. الخطة: لف على كل mask من 0 لـ (1 << n) - 1، ولكل mask شوف أنهي bits منوّرة.
  4. الحد: 1 << n شغالة لحد n = 30. والـ 2ⁿ subsets أصلًا مستحيلة لو n كبير، فالـ constraints دايمًا صغيرة (n ≤ 20 تقريبًا).
  1. < مش <=: 1 << 3 = 8، والـ masks من 0 لـ 7. مع <= هتعمل mask رقم 8 (1000): الـ bit المنوّر فيه رقم 3، والـ loop مش بتبص عليه، فهتطلع subset فاضية مكررة.
  2. 1 << i هو mask فيه bit i بس، والـ AND بيقول هل الـ bit ده منوّر في الـ mask. النتيجة رقم (مش true/false)، بس أي رقم غير صفر بيتحسب true في الـ if.
  3. كل mask بيطلّع subset مختلفة، فمفيش تكرار ومحتاجين نشيّك.

خلي بالك: الـ mask مرسوم زي ما بنكتب الأرقام (bit 0 على اليمين)، والـ nums مرسومة من الشمال. فـ bit 0 (أقصى اليمين) هو nums[0]:

التعقيد: 2ⁿ mask × n bit = O(n × 2ⁿ) وقت، وده نفس الـ backtracking. الفرق إن مفيش recursion، فأسهل في الكتابة وفي الـ debugging.

في كل مثال كان فيه سطر واحد لو اتكتب غلط الحل بيقع. يلا نجمعهم.

غلطات مشهورة

1. الأقواس والـ precedence

الـ bit operators (& و | و ^) أضعف من === و + و <. القاعدة: أي bit operator جوه تعبير أكبر، حطه بين قوسين.

2. >> في loop على رقم ممكن يبقى سالب

استخدم >>>= 1، بيدخّل أصفار، فالرقم لازم يوصل صفر بعد 32 لفة بالكتير.

3. نسيت >>> 0 في الآخر

4. masks فوق bit 30

5. x | 0 أو ~~x عشان تعمل floor لرقم كبير

الحيلة دي شغالة بس للأرقام اللي بين -2³¹ و 2³¹ - 1. أي حاجة بره ده، استخدم Math.floor أو Math.trunc.

6. toString(2) على سالب

دلوقتي جرّب نفسك: كام سؤال سريع، وتمرين تفكّر فيه قبل ما تفتح الحل.

اختبر نفسك

6 = 110 و 3 = 011. إيه 6 & 3 و 6 | 3 و 6 ^ 3؟

  • 2 و 7 و 7
  • 2 و 7 و 5
  • 9 و 7 و 5
  • 1 و 7 و 6

AND: الخانة الوحيدة المشتركة هي bit 1، يعني 010 = 2. OR: 111 = 7. XOR: المختلفين bit 2 و bit 0، يعني 101 = 5.

40 = 101000. إيه 40 & 39؟

  • 39
  • 8
  • 32
  • 0

ده x & (x - 1): أوطى bit منوّر في 40 هو bit 3 (قيمته 8)، والحيلة بتطفيه. 40 - 8 = 32 = 100000.

في JS، إيه قيمة -1 >>> 0؟

  • -1
  • 0
  • 1
  • 4294967295

-1 كل الـ 32 bit فيه منوّرين. الـ >>> 0 مبيحرّكش حاجة، بس بيقرا نفس الـ bits كـ unsigned: 2³² - 1.

في Counting Bits ليه new Array(n + 1) و i <= n؟

  • عشان الـ arrays في JS بتبدأ من 1
  • عشان المطلوب إجابة لكل رقم من 0 لـ n، يعني n + 1 رقم، والـ n نفسه منهم
  • عشان نتجنب error في dp[i >> 1]
  • مش لازم، n و i < n نفس النتيجة

الرينج 0..n inclusive. ده نفس غلطة FizzBuzz: لو المطلوب لحد n "شامل"، يبقى <= n، والعدد n + 1.

في Subsets على [1, 2, 3]، أنهي mask بيمثّل [1, 3]؟

  • 3 (011)
  • 5 (101)
  • 6 (110)
  • 4 (100)

الـ 1 هو nums[0] يعني bit 0، والـ 3 هو nums[2] يعني bit 2. الاتنين منوّرين: 101 = 5.

تمرين: فكّر قبل ما تفتح

Single Number III

mediumLeetCode 260

كل رقم موجود مرتين، ما عدا رقمين كل واحد مرة. رجّعهم، في O(n) و O(1) memory.

[6, 2, 9, 2, 6, 4] → [9, 4] (any order)
تلميح 1

لو عملت XOR للكل، الأزواج هتختفي، وهيفضل a ^ b. ده مش a ولا b، بس فيه معلومة: كل bit منوّر فيه هو bit الاتنين مختلفين فيه.

تلميح 2

خد أي bit منوّر في a ^ b، مثلًا أوطى واحد: x & -x. قسّم الأرقام كلها لمجموعتين حسب الـ bit ده. a في مجموعة و b في التانية، وكل زوج بيقع كامل في مجموعة واحدة. يبقى XOR كل مجموعة لوحدها = Single Number العادية.

الحل

على المثال: xor = 9 ^ 4 = 13 = 1101، و low = 1. المجموعة اللي فيها bit 0 هي 9 بس (6 و 2 و 4 زوجيين)، فـ a = 9، و b = 13 ^ 9 = 4. لفتين، O(n)، ومن غير أي memory.

لو الأسئلة عدّت معاك، روح على LeetCode بالترتيب اللي تحت.

اتمرن على LeetCode بالترتيب

المسائل دي قصيرة، فحل كذا واحدة في القعدة. ولو مسألة فيها "unsigned" أو "32-bit"، افتكر >>>.

وآخر حاجة: الفصل كله في صفحة واحدة ترجعلها قبل أي انترفيو.

الخلاصة

في جملة واحدة الرقم صف bits، وكل operator بيشتغل على كل bit لوحده. XOR بيلغي الأزواج، و x & (x - 1) بتطفي أوطى bit، و x & -x بتسيبه لوحده، والـ mask بيمثّل set. وفي JS كله 32-bit signed، فـ >>> و >>> 0 صحابك.
السؤالالإجابة
>> ولا >>>؟>> للقسمة على 2 مع إشارة. >>> لما بتلف على bits أو المسألة unsigned.
أعدّ الـ 1s إزاي؟n &= n - 1 لحد الصفر، وعدّ اللفات.
"كل رقم مرتين ما عدا واحد"؟XOR للكل. ولو اتنين، x & -x يقسّمهم.
أرقام فوق 2³¹؟الـ bit operators مش هتنفع. حساب عادي أو BigInt.
الأقواس؟دايمًا حوالين أي & أو | أو ^ جوه مقارنة أو جمع.

الفصل الجاي: كده كل الأدوات معاك، من الـ arrays لحد الـ bits. الفصل الأخير، خطة الانترفيو، بيلمّ كل ده: إزاي تتكلم وإنت بتحل، وإزاي تختار الـ pattern من أول دقيقة، وترتيب رجوعك لـ LeetCode.