צודק לגבי הגלישה, בחישוב גס 38 ביטים יספיקו לסכום הרגיל ו- 59 ביטים יספיקו לסכום הריבועי.

לכן 2 משתנים עם 64 BIT יספקו את הסחורה.

^^ בהחלט. צריך לדאוג להשתמש ב-long long (שהוא 64 ביט).

סתם בשביל ידע כללי, סביר שזה לא יפריע לפותר באופן מעשי, אבל למעשה ANSI C89 לא מגדיר long long בכלל. זה טיפוס שהוסיפו אח"כ (C99 הכניס אותו רשמית, וקבע שגודלו לפחות 64 סיביות).

אוקיי , אחרי מיבחן בתקשורת חזרתי לחשוב על הפיתרון לבעייה. ועלה לי בראש הרעיון הבא, ליבנות מערך בוליני בעל מיליון ביטים '0' , מה שניקרה bitarray , עבור כל מיספר שניקלט מהקובץ הביט במיקום הזה מישתנה ל '1'. ואז בבדיקה מחפשים אחר הביט שערכו נישאר '0', המיקום שלו זהו בעצם המיספר החסר.

אכשיו הבעייה היא להעביר את זה מהחלק של הרעיון למשהו כתוב...

רעיונות התקבלו בברכה.

תחשוב על זה ככה: נניח שאתה רוצה לייצג מערך בוליאני בגודל 8 בצורה חסכונית - כלומר, באמצעות בייט אחד בלבד. נקרא לו x.

איך ניגשים לביט במקום ה-i בבייט הזה (כאשר i הוא מספר בין 0 ל-7)? ע"י:

(x >> i) & 1

ההזזה דואגת להביא את הביט שאנחנו רוצים להיות הביט הימני ביותר, ואז ה-& דואג להשאיר רק את הביט הזה.

באותו אופן, על מנת להדליק את הביט במקום ה-i, צריך לעשות:

x |= (1 << i)

(בשביל לכבות ביט צריך לעשות פעולה אחרת, אבל זה לא נחוץ בתרגיל הזה)

מה קורה כשאתה רוצה לייצג יותר מ-8 ביט? תשתמש במערך של בייטים. כשאתה רוצה לגשת לביט במקום ה-i (או לשנות אותו), קודם כל תבדוק באיזה מקום במערך הוא נמצא, ואז תבדוק בתוך הבייט הזה איפה הוא נמצא בדיוק.

נ.ב.: אפשר להשתמש גם במערך של int, כאשר כל int מייצג 32 ביט. תכל'ס זה לא ממש משנה (אתה לא עושה שום פעולות שהייצוג הזה משנה להן).

הנה פונקציה שמדליקה את הביט במיקום ה-index ב-Buffer כלשהו:

#include <windows.h>

#define BITS_IN_BYTE (8)

void SetBit(PBYTE pcBuffer, DWORD dwIndex)
{
	DWORD dwByteIndex = 0;
	BYTE cBitMask = 0;

	if (NULL == pcBuffer)
	{
		return;
	}

	dwByteIndex = dwIndex / BITS_IN_BYTE;
	cBitMask = (1 << (dwIndex % BITS_IN_BYTE));

	pcBuffer[dwByteIndex] |= cBitMask;
}

כדי לייעל את החיפוש אתה לא חייב לעבור ביט ביט, אלא אתה יכול לקרוא כל פעם ארבעה בתים כ-DWORD לדוגמא ואז לבדוק אם הערך שונה מ-0xFFFFFFFF, אם כן אז הביט הכבוי נמצא באחד מארבעת הבתים האלו ונשאר לך רק לחשב את המיקום המדויק שלו.

אהם, אני מניח שהכותב לא ממש משתמש ב-windows API...

(אם מותר לו להשתמש בדברים כאלה, כבר יותר פשוט היה להשתמ ב-BitSet או <vector<bool ולסגור עניין...)

אני לא משתמש ב windows api.

כרגע נימצא בשלבי הסיום של כתיבת התוכנית וניתקלתי בבעיה , נגיד יש לי תביטוי הבא: y=2^x

ויש לי את y , איך אני מוצא את החזקה (x) , חשבתי על הפונקציה log , אבל היא פועלת לפי בסיס 10.

אתה יכול להשתמש בנוסחת מעבר בין בסיסים:

חוץ מזה, אם אתה יודע ש-x הוא חזקה של 2, יש דרכים יותר פשוטות ומדוייקות (בלי להתעסק עם לוגים) - פשוט תמצא את הביט הדלוק במספר (או ע" חיפוש פשוט, או ע"י קיצורי דרך כלשהם).

ועוד דרך נראלי ,לא זוכר בטוח X=LN2/LNY

אבל יש מצב זה עובד רק עם e..

מזתומרת עוד דרך? זו בדיוק הנוסחה שהראיתי.

התוכנית עובדת , לאחר שהפונקציה log עשתה לי בעיות ולא הייה לי כוח להתחיל לריב איתה מצאתי את החזקה על ידי חילוק המיספר ב 2 וספירת מיספר הפעמים שהמיספר מיתחלק עד שהוא מגיע ל 0.

תודה רבה על העזרה!

מזתומרת עוד דרך? זו בדיוק הנוסחה שהראיתי.

לא ... =\

מזתומרת לא?

lnY/ln2 זה:

(log_e (y) / log_e (2

תחליף את y ב-x, את 2 ב-b ואת e ב-k וקיבלת את הנוסחה.

אמנם בדרישות השאלה היו צריכים לעשות פעולות על ביטים.

אבל לגבי תיאוריית המערך שהוצעה בהתחלה, למה לא לייצר מערך char-ים בגודל מיליון?

char ממילא תופס ביט אחד בודד.

char תופס BYTE אחד ולא BIT אחד...