{"id":145,"date":"2007-10-28T17:38:09","date_gmt":"2007-10-28T16:38:09","guid":{"rendered":"http:\/\/blog.m-ri.de\/index.php\/2007\/10\/28\/schnelle-binaere-algorithmen\/"},"modified":"2008-03-01T21:37:44","modified_gmt":"2008-03-01T20:37:44","slug":"schnelle-binaere-algorithmen","status":"publish","type":"post","link":"http:\/\/blog.m-ri.de\/index.php\/2007\/10\/28\/schnelle-binaere-algorithmen\/","title":{"rendered":"Schnelle bin\u00e4re Algorithmen"},"content":{"rendered":"<p>Manchmal tauchen in Foren richtig nette Sachen, die einen in Erstaunen setzen, wie schnell und einfach manches zu l\u00f6sen ist. (siehe <a href=\"http:\/\/groups.google.de\/group\/microsoft.public.de.vc\/browse_thread\/thread\/da1e4c107f25ec23\">Thread<\/a>)<br \/>\nZwei interessante Fragen, die mich auch schon \u00f6fter besch\u00e4ftigt haben sind hier mal erw\u00e4hnt und als C++ Code wiedergegeben.\u00a0Bisher habe ich diese immer mit einer entsprechenden Schleife und Shift-Operatoren gel\u00f6st.<\/p>\n<p><strong>1. Wie kann man schnell pr\u00fcfen ob ein Integer eine 2er Potenz ist?<\/strong><\/p>\n<p>Der Algorithmus ist so verbl\u00fcffend einfach, dass man sich fragen muss, warum man noch nicht von selbst drauf gekommen ist:<\/p>\n<pre line=\"1\" lang=\"cpp\">bool IsPowerOf2(int n) \r\n{ \r\n\u00a0return (n & (n - 1))==0; \r\n}<\/pre>\n<p>Tricky: Wenn mehr als zwei Bits gesetzt sind, bleibt bei der gegebenen Arithmetik mindestens das h\u00f6chste Bit stehen.<\/p>\n<p>\u2757 Nach diesem Algorithmus ist 0 \u00fcbrigens auch eine Power of 2!<\/p>\n<p><strong>2. Wie findet man die n\u00e4chste 2er Potenz einer gegebenen Zahl?<\/strong><\/p>\n<p>Diese Frage stellt sich f\u00fcr mich immer wieder, wenn ich bin\u00e4re Suchen durchf\u00fchre.<br \/>\nAuch hier gibt es eine statische L\u00f6sung, die ich hier mal wiedergebe und die sowohl f\u00fcr 32bit als auch f\u00fcr 64bit funktioniert und direkt in entsprechende Assembler Befehle umgesetzt wird.<br \/>\nDer Code vermeidet einen 32bit shift, da das Ergebnis in einem 32bit C++ Compiler undefiniert ist (Warning C4293).<\/p>\n<pre line=\"1\" lang=\"cpp\">int GetNextPowerOf2(int n) \r\n{ \r\n\u00a0\/\/ Code works for 32bit and 64bit \r\n\u00a0\u00ad\u00ad\u00ad\u00ad-\u00ad-n;\u00a0\u00a0\u00a0 \r\n\u00a0n |= n >> 1; \r\n\u00a0n |= n >> 2; \r\n\u00a0n |= n >> 4; \r\n\u00a0n |= n >> 8; \r\n\u00a0n |= n >> 16;\u00a0\/\/ Sufficient for 32bit \r\n\u00a0n |= n >> 16;\u00a0\/\/ for a 64bit System we need a new 32bit shift (n>>32) \r\n\u00a0n |= n >> 16;\u00a0\/\/ but this operation is undefined on a 32bit system \r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/ so we use 2 16bit shifts. (C4293) \r\n\u00a0return n+1; \r\n}<\/pre>\n<p>Oft genug wird das h\u00f6chste gesetzte Bit gesucht. In diesem Fall einfach den Startwert oder das Ergebnis um eine Bitposition shiften.<\/p>\n<p>Tricky: Das h\u00f6chste Bit wird nach der Subtraktion einfach auf alle niederen Bits \u00fcbertragen.<\/p>\n<p>\u2757 Auch hier ist das Verhalten bei 0 eigent\u00fcmlich. Die n\u00e4chste 2er Potenz auf 0 ist mit diesem Algorithmus 0!<\/p>\n<p>Die entsprechenden Algorithmen sind hier auf dieser Seite beschrieben:<br \/>\n<a href=\"http:\/\/en.wikipedia.org\/wiki\/Power_of_two#Fast_algorithm_to_check_if_a_number_is_a_power_of_two\">http:\/\/en.wikipedia.org\/wiki\/Power_of_two#Fast_algorithm_to_check_if_a_number_is_a_power_of_two<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Manchmal tauchen in Foren richtig nette Sachen, die einen in Erstaunen setzen, wie schnell und einfach manches zu l\u00f6sen ist. (siehe Thread) Zwei interessante Fragen, die mich auch schon \u00f6fter besch\u00e4ftigt haben sind hier mal erw\u00e4hnt und als C++ Code wiedergegeben.\u00a0Bisher habe ich diese immer mit einer entsprechenden Schleife und Shift-Operatoren gel\u00f6st. 1. Wie kann &hellip; <a href=\"http:\/\/blog.m-ri.de\/index.php\/2007\/10\/28\/schnelle-binaere-algorithmen\/\" class=\"more-link\"><span class=\"screen-reader-text\">\u201eSchnelle bin\u00e4re Algorithmen\u201c <\/span>weiterlesen<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[30,3],"tags":[51,370],"class_list":["post-145","post","type-post","status-publish","format-standard","hentry","category-c","category-programmieren","tag-algorithmen","tag-c"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/posts\/145","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/comments?post=145"}],"version-history":[{"count":0,"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/posts\/145\/revisions"}],"wp:attachment":[{"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/media?parent=145"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/categories?post=145"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/tags?post=145"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}