العثور على نمط من الأرقام الثنائية باستخدام shift اليمين و المعامل و ؟

Question

أحاول كتابة الوظيفة في الجمعية العامة التي سيتم الكشف عن إذا كان أطول عدد ثنائي يحتوي على أصغر ثنائي النمط.

على سبيل المثال:
لا 100111 تحتوي على 1001?

عندما قرأت هذه المشكلة اعتقدت أنه بإمكاني فعل أحادي المعامل و مع عدد كبير و أصغر نمط حين تحول الحق (منطقية) في كل مرة في حلقة.

حتى في رأسي أعتقد أنها ستفعل:

100111 AND 1001 = 0  
Shift-right 1  
010011 AND 1001 = 0  
Shift-right 1  
001001 AND 1001 = 1 // Pattern FOUND!  

وكرر هذا حتى إما عدد تحول حتى كان من صفر أو وعاد 1.

ومع ذلك, أعتقد أنني يجب أن يكون شيء من الخلط لأن هذا هو العودة 1 معظم الأشياء التي كنت وضعت في في الجولة الأولى من الحلقة.أنا الخلط على استخدام و ؟

Answer 1

المشكلة هي أن "تطابق" أيضا إرجاع قيمة غير صفرية الخاص بك والتحقق من:

100111 AND 001001 = 000001

لذلك هذه الاختبارات إذا أي من أجزاء المباراة, ولكن تريد التأكد من كل بت هي نفسها.نتيجة و يجب أن يكون مساويا نمط كنت تبحث عن:

x = 100111
if (x AND 1001 == 1001)
  print "found"

Answer 2

يجب ثم اختبار ضد نمط البحث:

if ((TestPattern & SearchPattern) == SearchPattern)
{
   // then match
}

(حيث & يمثل المعامل AND)

Answer 3

المعامل و لا تعمل بالطريقة التي تتوقعها (انطلاقا من عينات تجاهل الرموز التي يبدو أن أقترح عليك استخدام المعامل و المنطقية و بت).فقط يأخذ بت التي تم تعيينها إلى 1 "بعين الاعتبار".E. g 1111 1001 == 1001.

تحتاج إلى استخدام XOR ومقارنة ضد 0 مباراة (تذكر قناع بت أنت لا تقارن من النتيجة).في المثال الخاص بك يتم العثور على تطابق عندما (ن ^ 1001) & 1111 == 0000

Answer 4

من أجل التأكد من أن كلا من 0 و 1 بت تطابق بحثك نمط ، تحتاج أن تفعل شيئا مثل هذا:

if ((InputPattern AND SearchMask) == SearchPattern)
{
    // then match
}

على SearchMask يجب أن يكون كل 1 بت من طول تساوي SearchPattern.على سبيل المثال ، يمكن أن يكون SearchMask == 1111, SearchPattern == 1001.