09-01-2009, 20:30
|
|
|
|
חבר מתאריך: 21.12.04
הודעות: 30,021
|
|
אני לא יכול להעביר לך שיעור שלם בנוגע לאיך תו נראה מבחינת זיכרון (8 ביט), ועל פעולות של SHIFT... זה צריך ללמוד בשלב מסויים כדי להבין את הפתרון לבעיה שלך.
אני למדתי את זה בשיעורי אסמבלי, אבל אני מניח שב-C זה עלול להראות בצורה קצת שונה.
כיוון שלא עבדתי מעולם עם ביטים ב C (מה שמצאתי בשבילך היה מחיפוש בגוגל), אני לא יודע בדיוק איך ה syntax יראה, אבל ברגע שאת מבינה את הרעיון, חיפוש בגוגל יפתור את רוב הבעיות.
אני אנסה לתאר בצורה דיאגרמית את הבעיה שלך.
כל תו במערך מורכב מ 8 ביט, כאשר הביט הראשון (מספר 0) הוא תמיד 0 (הנחת התרגיל):
נניח שיש לך מערך של 6 תווים, כך הם יראו לפני דחיסה:
תהליך הדחיסה למעשה יזיז את כל הביטים של התו הראשון פעם אחת שמאלה:
כיוון שבפעם הראשונה של ההזזה - אין לך סיבית נשא (Carrier) (זאת אומרת, יש אבל היא תמיד 0 ואנחנו רוצים להתעלם ממנה) לא צריך לשמור את הביט שיוצא בהזזה בשום מקום.
בפעם השניה, את תזיזי את כל הביטים פעמיים, ואז יהיה לך בפעם הראשונה Carry שאת מתעלמת ממנו, ובפעם השניה (ההזזה השניה) יהיה לך Carry (נשא) שאת רוצה לשים במקום הפנוי בבית הקודם (הראשון).
ניתן לראות בתרשים כי הביט הראשון לא מקבל התייחסות, הביט השני (מספר 1) נהפך להיות הנשא (Carry) ואותו נשים במקום מספר 7 בתו הראשון, ואילו כל שאר הסיביות יזוזו 2 מקומות שמאלה.
בפעם השלישית את תזיזי את כל הביטים מהתו השלישי, שלוש פעמים שמאלה. בהזזה הראשונה נתעלם מהנשא, בפעם השניה נשים את הנשא במקום הפנוי הפנימי בתו השני, ובהזזה השלישית נשים את הנשא במקום הפנוי השני בתו השני וכן הלאה...
בפעם השמינית, מה שיקרה זה שנזיז את כל הביטים 8 פעמים שמאלה ואז יקרה משהו מאוד מעניין... אנחנו למעשה נזיז את כל התו שמאלה מה שאומר שהוא יהיה ריק לגמרי (יהיה NULL) ונשים את 7 התווים האחרונים שלו ב 7 המקומות הפנויים שיש לנו בתו השביעי.
כיוון שהתו השמיני יהיה ריק לגמרי, נוכל להעמיס עליו מחדש את כל התו התשיעי, ואת כל התו העשירי נזיז על התו התשיעי וכך למעשה חסכנו בית אחד שלם לכל 8 תווים (לכל 8 בתים).
הדבר היחיד שאני לא מצליח למצוא באינטרנט זה איפה אני שומר את הנשא.
כיוון שאת צריכה לשים אותו בתו הקודם בכל הזזה (מלבד הראשונה) את צריכה לשמור אותו איפה שהוא, ואז את ההשמה את עושה ע"י OR
נגיד שהנשא שלך הוא "0" כמו בדוגמא מעלה, אז את צריכה לשים אותו בתא הפנוי הראשון (תא 7 בתו הראשון), אז את עושה OR בין התו הראשון לנשא שלך שהוא 00000000.
התו הראשון בדוגמא שלנו (אחרי ההזזה הראשונית) הוא: 10011100, ולכן אחרי OR נקבל:
10011100 OR
00000000
--------------
10011100
(לא מפתיע כיוון שאנחנו מוסיפים 0 לתא שכבר היה בו 0, אז התוצאה לא השתנתה).
בפעם השניה אנחנו נעשה BIT SHIFT שמאלה פעמיים ולכן התא השני יהיה: 00101000.
לתו השלישי נבצע BIT SHIFT שלוש פעמים ולכן הוא יהיה: 01011000 ונקבל נשא "01".
את הנשא "01" (שהוא למעשה גם 00000001 בבינארי) נשים ב 2 הסיביות הפנויות בתו השני באמצעות OR ונקבל:
10011100 OR
00000001
--------------
10011101
וכך העברנו את הסיביות מהתו השלישי לתו השני.
אם תבצעי את הפעולה הזו 8 פעמים, את תקבלי בפעם השמינית תו ריק לגמרי, ופה את חוסכת ודוחסת מידע.
נערך לאחרונה ע"י Narxx בתאריך 09-01-2009 בשעה 20:35.
|