كيف يمكنني التحقق من المبالغة الوزن دون تحويل ثنائي ؟

Question

كيف يمكنني الحصول على عدد "1"s في تمثيل ثنائي عددا من دون تحويل الواقع و العد ؟

على سبيل المثال

  def number_of_ones(n):
      # do something
      # I want to MAKE this FASTER (computationally less complex).
      c = 0
      while n:
        c += n%2
        n /= 2
      return c


>>> number_of_ones(5)
    2
>>> number_of_ones(4)
    1

Answer 1

والمنظمة البحرية الدولية، نهج جيد ستكون لاستخدام جدول نظرة متابعة - إنشاء قاموس الذي يحول بايت لعدد من 1 ل (يمكنك استخدام الرمز الذي نشر لتوليد ذلك، فإنه سيحتاج فقط لتشغيل مرة واحدة)، و ثم استخدام شيء مثل هذا:

def number_of_ones(n):
    sum = 0
    while n != 0:
        sum += lookup_table[n & 0xff]
        n >>= 8
    return sum

وأعتقد أن هذا هو مفاضلة جيدة إلى حد ما بين الفضاء وتشغيل الوقت.

Answer 2

وأنا لست مبرمج الثعبان، ولكن أتمنى أن يكون ذلك كافيا بالنسبة لك لمتابعة.

c = 0
while n:
    c += 1
    n &= n - 1

return c

وعلى الرغم قليلا غامضة، انها ميزة الابتدائية والسرعة والبساطة. وكرر حلقة بينما مرة واحدة فقط عن كل بت تعيين إلى 1 في ن.

Answer 3

لا يمكنك جعل هذا حسابيا أقل تعقيدا.سيكون O(n) عدد البتات ، أو كما الجواب مع & خدعة أظهرت O(n) عدد البتات تعيين إلى 1;ولكن ما لم يكن كل من الأرقام التي تستخدم هي حالة خاصة ، هذا الأخير أن في المتوسط تكون n/2 ، لذلك كل من تلك O(n) الأرقام هي نفسها.

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

الآن, أعتقد أنني كونها قذرة قليلا لأن العديد من هذه الأمثلة هي في الواقع O(n^2) حيث في بيثون عليك أن تدرس كل رقم مرة واحدة في الوقت ، حتى مع بيثون عدد صحيح طويل من 100 بايت, a + أو & أو / العملية سوف ننظر في كل بايت على الأقل مرة واحدة ، وهذا لن يحدث أكثر وأكثر حتى الرقم ينخفض إلى الصفر (في المخططات المذكورة أعلاه) ، لذلك هذه مرة أخرى ، حقا O(n^2) العمليات.أنا لست متأكدا من الثعبان سوف تسمح صحيح O(n) الحل هنا.

على أي حال:إذا كنت حقا يسأل عن الحسابية التعقيد ، وهي على وجه التحديد يعني big-O تحليل هذا الجواب.:-)

Answer 4

إذا كنت تريد أن تفعل ذلك في سطر واحد، هل يمكن استخدام:

sum( [x&(1<<i)>0 for i in range(32)] )

Answer 5

إذا كنت قلقا فعليا عن السرعة، رمز عنه في C (انظر <لأ href = "https://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of- ضبط-بت-في-32-بت عدد صحيح "> هذا السؤال للحصول على كيف)، والتفاعل مع تنفيذ C باستخدام شيء من هذا القبيل <لأ href =" http://docs.python.org/library /ctypes.html "يختلط =" نوفولو noreferrer "> ctypes .

Answer 6

وهنا:

ومواطنه bitCount (int_no):

c = 0
while(int_no):
    int_no &= (int_no - 1)
    c += 1
return c

وهذا قد يكون وسيلة قديمة وفعالة للقيام بذلك ... implementated أصلا في C (ALGO له اسم لا أستطيع أن أتذكر). أنه يعمل بشكل جيد بالنسبة لي آمل أن يفعل أي شخص آخر

Answer 7

ص = امدا ن: ن و 1 + ص (ن و (ن 1))

وهذا يستخدم قصيرة في الدائرة والعودية، عندما n هو أكبر من 0، فإنه يتحول إلى حساب 1 + ص (ن و (ن 1)) حيث ص (ن و (ن 1)) ويسمى وهلم جرا، عندما n غير 0 فإنها ترجع 0. التعقيد كونها O (ن) منذ تشغيله عدد المرات عدد منها موجودة في ثنائي.

مثال: ع (9) = 1 + ص (8) = 1 + 1 + ص (0) = 1 + 1 + 0 = 2