חזקה של שתיים – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Yammesicka (שיחה | תרומות) |
אין תקציר עריכה |
||
שורה 14:
== אלגוריתם מהיר לבדיקה האם מספר חיובי הוא חזקה של שתיים ==
ההצגה הבינארית של מספרים מאפשרים ליצור אלגוריתם מאוד מהיר שמחליט האם מספר [[מספר חיובי|חיובי]] [[מספר שלם|שלם]] נתון ''x'' הוא חזקה של שתיים:
:המספר החיובי ''x'' הוא חזקה של שתיים ⇔ {{משמאל לימין|(''x'' & (''x'' - 1))}} שווה לאפס.
כאשר & הוא [[
== אלגוריתמים מהירים לעיגול כל מספר שלם לכפולה של חזקה של שתיים ==
עבור כל שלם ''x'' וחזקה של שתיים , ''y'', נציב ''z'' = ''y'' - 1,
* {{משמאל לימין|''x'' & (!''z'')}} מעגל כלפי מטה,
* {{משמאל לימין|(''x'' + ''z'') & (!''z'')}} מעגל כלפי מעלה,
* {{משמאל לימין|(''x'' + ''y'' / 2) & (!''z'')}} מעגל לחזקה הקרובה ביותר.
== ראה גם ==
| |||