שאלה מראיון עבודה

[ברנדל]

שאלה מראיון עבודה

יש byte שמכיל מספר כל שהוא לדוגמא 11001010 יש להפוך את ה byte, שיכיל : 01010011

 

[scalla]

מה השאלה?

 

[DNile]

באיזה סביבה?

תנאים מגבילים?

 

[ברנדל]

מתבקשים לשני פתרונות

אחד באסמבלר אחד ב C אין תנאים מגבילים, מתבקש פתרון מהיר ואלגנטי.

 

[DNile]

יש את הטריק הידוע:

(שגם אם הוא אינו ידוע, זה לא קשה להגיע אליו לבד קודם כל, עושים SWAP בין הנגיסה העליונה לנגיסה התחתונה של הבית, אח"כ עושים SWAP לשני ביטים העליונים והתחתונים בכל נגיסה, ובסוף עושים SWAP לכל ביט בתוך כל זוג ביטים. ובקוד?

byte reverse(byte b) { b = (0x0f & b >> 4) | (0xf0 & b << 4); b = (0x33 & b >> 2) | (0xcc & b << 2); b = (0x55 & b >> 1) | (0xaa & b << 1); return b; }​

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

 

[ברנדל]

וואלה יפה!

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

 

[gilad_no]

דוגמא

byte swap(byte b) { byte res=0; for (byte m=1;m;m<<=1) { res<<=1; res|=(b & m) ? 1 : 0; } return res; }​

 

[gilad_no]

וריאציה דומה:

byte swap(byte b) { byte res=0; for (byte m=1;m;m<<=1,b>>=1) { res<<=1; res|=(b & 1); } return res; }​

 

[scalla]

אם כבר

unsigned char swap (unsigned char b) { unsigned char t; t = ~b; return t; {

 

[scalla]

טעות שלי

 

[ברנדל]

יפה מאוד!

 

[אוֹריארד]

תשובה:../images/Emo26.gif

String before = "11001010"; String after = (new StringBuffer(before)).reverse().toString();​

 

[vinney]

ביטים אורי, ביטים.

חוצמזה, ביקשו C ו ASSEMBLY, לא #C. (או שזה JAVA?)

 

[עידו123456]

נו באמת

חשבתי שזה כבר common knowledge שאורי נוגע רק ב Java

אתה ממש מעליב אותו עם הקישור ל #C

 

[אוֹריארד]

../images/Emo13.gif לא רק... לא רק...

 

[אוֹריארד]

אההה.... בייטים... אז:../images/Emo26.gif

תוסיף:

Byte.decode(after);​

 

[אוֹריארד]

עם רמאות קטנה, כי זה בבינארי...

 

[DadleFish]

אם מדובר ב-BYTE בודד,

הפתרון הכי מהיר יהיה פשוט להחזיק טבלה. זה MOV אחד, 3 טיקים, ונגמר הסיפור. אין יותר מהיר מזה

 

[vinney]

לדעתי זה מה שנדרש

הייתה לי כזאת שאלה ברעיון עבודה גם, וזה מה שרצו

 

[ברנדל]

כן , זה גם פתרון נחמד

(וגם חוסך כאב ראש בראיון)