סיבוכיות מציאת מספר אחדים במספר בינארי

[Bsx]

שלום, נתון לי מספר בינארי, חוץ מ - O(n) ובעצם לעבור אחד אחד ולצבור,

האם יש רעיון לפתרון בסיבוכיות נמוכה יותר, למשל O(logn)?

(למי שלא הבין, נתון לי 101 ואני צריך להחזיר 2)

תודה רבה

[elrxx]

while(n) {
  if(n&1)
    count++;
  n>>=1;
}[code]
לא נראה לי שיש יותר יעיל מזה

[שניצל]

אם מראש המספר מוגבל בגודלו (כמו int רגיל, לדוגמה) אז אפשר לעשות את זה בזמן שהוא log של גודל המספר:

http://en.wikipedia.org/wiki/Hamming_weight

מבחינת סיבוכיות אסימפטוטית זה אין דרך יותר יעילה מלעבור על כל הספרות, ולכן זה לא פחות מ-(O(n (כאשר n הוא מספר הספרות, כן?), אבל האלגוריתם שבויקיפדיה הוא הכי יעיל מבחינה מעשית.

[בור ועם הספר]

שלום, נתון לי מספר בינארי, חוץ מ - O(n) ובעצם לעבור אחד אחד ולצבור,

אין דבר כזה "מספר בינארי". מספר הוא מספר. מה שבינארי הוא הייצוג. ייצוג עשרוני, ייצוג בינארי וכו'

לעניין חישוב הביטים:

היום במכונות x86 מודרניות יש הוראות חומרה לחישוב מהיר של מספר הביטים (POPCNT)

חישוב מהיר בתוכנה הוא פירוק המספר לבתים בודדים ומציאת ערך עבור כל אחד מטבלה, זה מצריך טבלאות סטטיות וקצת "לוגיסטיקה" בקוד וזה בטח לא אלגטי כמו הפתרון הבא (שמספר הלולאות כמספר הביטים):

unsigned int bit_count(unsigned int n)
{
  int count = 0;
  while (n) {
   ++count;
   n &= (n-1);
  }
  return count;
}

הוראות החומרה מאפשרות אופטימיזציות אגרסיביות למשל, הקוד הבא ב++C מיתרגם אחרי קומפילציה להוראת אסמבלי אחת (popcnt):

unsigned int bit_count(unsigned int n)
{
  return std::bitset<sizeof(int)* CHAR_BIT>(n).count();
}

[yigael_o]

אתה יכול ב O(1). אתה פשוט צריך זיכרון.

אם אתה מחזיק מערך (אני יוצא מתוך הנחה שהמספר שלך מוגבל) שכל מקום במערך מחזיק כמה אחדים יש בו (זמן אתחול ארוך יחסית כמובן)

אז אתה פשוט צריך לגשת למיקום הנכון ולקרוא את התשובה.