איך הופכים סדר סיביות בשפת C?

[tom123]

מה הדרך הכי אלגנטית להפוך סיביות בבית כלומר אם יש ביית:

11010010

להפוך ל-

01001011

[שניצל]

הדרך הכי נאיבית היא להשתמש בלולאה פשוטה, שמוציאה מהמספר ביט אחר ביט ומכניסה אותו למספר אחר (בכל איטרציה הלולאה מוציאה את הביט התחתון במספר, ומכניסה אותו לתוצאה).

דרך יותר יעילה היא כל פעם להחליף חצי מהביטים בחצי אחר מהביטים: בהתחלה מחליפים את 4 הביטים התחתונים עם 4 העליונים, ככה:

x = ((x & 0x0f) << 4) | ((x & 0xf0) >> 4) 

ואז להחליף זוגות ביטים - בכל רביעיית ביטים, להחליף את 2 הביטים העליונים עם 2 הביטים התחתונים:

x = ((x & 0x33) << 2) | ((x & 0xcc) >> 2) 

ואז להחליף את הביטים בין כל זו ביטים סמוכים:

x = ((x & 0x55) << 1) | ((x & 0xaa) >> 1) 

דרך שלישית, והכי יעילה, היא להשתמש ב-lookup table: להכין מראש מערך שמכיל את התוצאות עבור כל אחת מ-256 האפשרויות, ופשוט לגשת למערך במקום המתאים.

[tom123]

לא הבנתי את הדרך השניה אשמח אם תסביר יותר, ברגע שאתה מזיז סיביות נכנס 0 לא? זה לא הורס את המידע?

[שניצל]

השיטה השנייה הולכת ככה:

נניח שהבית שלך הוא abcdefgh (אלה מייצגים ביטים).

כשעושים x&0x0f נשאר 0000efgh, וכשעושים x&0xf0 נשאר abcd0000.

השיפטים (>> ו-<<) וה-or (ה-|) מחליפים בין שני החלקים, ונשארים עם efghabcd

עכשיו, כשעושים x&0x33 נשאר 00gh00cd, וכשעושים x&0xcc נשאר ef00ab00

השיפטית וה-or שוב מחליפים בין שני החלקים, ונשארים עם ghefcdab.

הצעד האחרון מחליף בין כל זוגות ביטים סמוכים, באותו אופן.

[tom123]

תודה על ההסבר והתשובה המהירה, הבנתי.

[liordavid]

כתבתי קובץ לפני כמה חודשים - צירפתי אותו - אתה מסובב לפי מספר הסיבובים שאתה בוחר

האלגוריתם הוא לספור את מספר הסיביות, לחלק ב- 10 ולהכפיל את השארית ב- 10 בחזקת מספר הסיביות וכך הסיבית מסתובבת...

[attachment deleted by admin]

[matteo]

http://www.daniweb.com/forums/thread108181.html

[Zelig]

מספר שיטות כאן:

http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious