תהליך ארוך וקשה, ראיון של 3 שעות, התמקדות רבה בשאלות על ביטים וחידות הגיון
שאלות מתוך הראיון
1. איך בודקים שמספר הוא חזקה של 2 בסדר גודל של (1)O זמן ריצה
2. מספר האחדות שמופיעות במספר בינארי, ב-(1)O
תשובות
הוסף תשובה
|
לצפיה בתשובות
יוני 2021
Both questions rely on the same trick. If you take a number, and subtract 1, then you flip the rightmost bit set, and set the bits on the right to it. For example:
1101 - 1 --> 1100
1100 - 1 --> 1011
When doing bitwise or with the two numbers (x ^ (x - 1)), we get it leaves all the bits set to the left of the rightmost bit that was originally set. For example:
1101 & 1100 = 0x1100
1100 & 1011 = 0x1000
Now for the questions themselves:
1. A number is a power of 2 provided that it has only single bit set. So to figure out of a number is a power of two, simply need to check (x & (x-1) == 0).
For example, the number 4 (100) & 3 (0x011) = 0, but the 5 (101) & 4 (100) = 1.
This is also a base for the second question. In order to check the number of bits in a number, need to run in a loop (x & (x-1)), and count the number of the loop. Each time, this bitwise and will eliminate the rightmost bit, so this loop is bounded to the number of bits set:
int count = 1;
if (x = 0) return 0;
while (x = x & (x-1)) { count++;}
ראיון לתפקיד 
