testen ob Zweierpotenz

[len]

kann man irgendwie testen, ob eine Zahl ein Produkt aus 2^x ist? Aktuelle teile ich rekursiv solange durch 2 bis ein Ergebnis mit Rest nicht 0 rauskommt (=false), oder die Zahl selber 1 ist (=true) - dann ist dieses eine Zweierpotenz. Das dauert aber bei großen Zweierpotenzen recht lange bis man das weiß. Kann man das schneller machen?

[Neomi]

Floating Point: wenn die Mantisse nur aus Nullen besteht (implizite 1 mal außen vor), ist es 2^x, wobei x in den Exponenten-Bits mit Bias enthalten ist und auch kleiner als 0 sein kann.

Integer: n & (n - 1) == 0

[ollix]

Integer: n & (n - 1) == 0 für n > 0

[Coda]

2^x sollte immer positiv sein, nicht? ;)

[Neomi]

für n > 0

2^x ist immer positiv (Überlauf zählt nicht). Und Integer können auch vorzeichenlos sein.

[ollix]

Jo, ich meinte im Speziellen nur direkt n=0. Hatte nämlich schonmal einen Bug, der im Endeffekt direkt darauf zurückzuführen war, daß 0 eine Zweierpotenz war.

[I & me feat. myself]

2 hoch x ist in Bitsicht vorne mal ne 1 und dan (x-1) Nullen -- brauch mal nun die einzelnen Bits prüfen.

muss man halt gucken, ob die Berechnung von n & (n-1) teurer ist.

Beide Lösungen dürften aber eleganter sein als die rekursive Variante.

[ollix]

2 hoch x ist in Bitsicht vorne mal ne 1 und dan (x-1) Nullen -- brauch mal nun die einzelnen Bits prüfen. Das macht n & (n-1) doch?

[rotalever]

Jo, ich meinte im Speziellen nur direkt n=0. Hatte nämlich schonmal einen Bug, der im Endeffekt direkt darauf zurückzuführen war, daß 0 eine Zweierpotenz war.
Für welches x ist denn 2^x == 0? Beziehungsweise warum soll 0 überhaupt eine Zweierpotenz sein.

[ollix]

Gar nicht, der Binärtest ob Zweipotenz liefert bei 0 aber eben true zurück. Das ist ja nicht sooo :) schlimm und klar ist die kleinste ganzzahlige Zweierpotenz 1. Häufig werden diese Tests aber ja für Dimensionen von Feldern/Matrizen gebraucht und da kann man sich schon versehen wenn man für eine Dimension 0 false erwartet. Nichtsdestotrotz ist die Binäroperation natürlich der Weg es zu machen, irrelevant schnell, schick und konstant.

[Gast]

thx Neomi (und auch Ollix)!

Die lösung ist geil :)

[daflow]

Edit: Ups .... 2er Potenz... hätte vorm Posten meinen ersten Kaffee trinken sollen...
mein Freudscher Verdenker war Produkt von 2*x :O .. da wäre Modulo erste Wahl gewesen ;)

[Gast]

aber eine Zahl ist nur eine Zweipotenz, wenn sich sich "nur" zu Zweien faktorisieren läßt. Einmal durch 2 teilen reicht ja nicht. 10 % 2 = 0, aber 10 ist keine Zweierpotenz.

[rotalever]

Gibt es eigentlich auch so einen "Trick" wie man die nächste Zweierpotenz zu einer Zahl errechnen kann? Also eine Zahl n gegeben und man will die kleinste Zweierpotenz haben die Größer oder Gleich der Zahl ist:
511=>512
512=>512
513=>1024

[Kinman]

Gibt es eigentlich auch so einen "Trick" wie man die nächste Zweierpotenz zu einer Zahl errechnen kann? Also eine Zahl n gegeben und man will die kleinste Zweierpotenz haben die Größer oder Gleich der Zahl ist:
511=>512
512=>512
513=>1024

EDIT: Hmmm.. irgendwo hab ich beim zusammenkürzen einen Fehler gemacht...
Hier die "lange" Version


<?php
$num = 220;
$hiBit = 8;


$compare = 1;
$max = pow(2, $hiBit);
$i = 1;
$numBits = 0;

do
{
if (($num & $compare) > 0)
{
$hiBit = $i;
$numBits++;
}
$i++;
$compare = $compare << 1;
}
while ($compare <= $max);

if ($numBits <= 1) $retVal = $num;
else $retVal = pow(2, $hiBit);

echo ($retVal);
?>

PHP ist für sowas wirklich nicht die geeignetste Programmiersprache ;D

Mögliche Lösung in PHP (hab in der Fa. nix anderes zur Verfügung)

//Klappt leider nicht
$num = 220; //Zu prüfende Zahl
$hiBit = 8; //Höchstes zu prüfende Bit

$compare = 1;
$i = 1;
$numBits = 0;

do
{
if (($num & $compare) > 0)
{
$hiBit = $i;
$numBits++;
}
$i++;
$compare <<= 1;
}
while ($i <= ($hiBit + 1));

if ($numBits <= 1) $retVal = $num;
else $retVal = pow(2, $hiBit);

echo ("Nächste 2er Potenz: $retVal<br />");


mfg Kinman

[Coda]

http://en.wikipedia.org/wiki/Power_of_two#Fast_algorithm_to_find_the_next-highest_power_of_two_to_a_number_in_the_ring_of_integers_modulo_a_fixed_power_of _two

[Chris Lux]

http://en.wikipedia.org/wiki/Power_of_two#Fast_algorithm_to_find_the_next-highest_power_of_two_to_a_number_in_the_ring_of_integers_modulo_a_fixed_power_of _two
ich wollte es gestern noch schreiben ;)

inline unsigned next_power_of_two(unsigned x)
{
assert(sizeof(x) == 4);

--x;

x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;

return (++x);
}


da gibt es aber auch eine assembler variante:

// asm trickery, assume N = 244 (11110100)
__declspec( naked ) int NearestPowerOf2_6( int n )
{
__asm
{
// ecx = n
dec ecx // n-=1; n= 243 (111100110)
mov eax,1 // store 1 in eax
bsr ecx,ecx // get the number of the first bit that is set to 1, scanning from MSB to LSB (eg. 000111100110 would give you 8)
inc ecx // ecx = 9
shl eax, cl // shift left 1 by 9 gives you 256
ret
}
}


find ich persoenlich die beste variante, leider will ich meinen code sehr portabel haben und will nicht x assembler varianten pflegen, deshalb bleib ich beim ersten beispiel...

[Gast]

assert(sizeof(x) == 4);Kann man eigentlich auch abhängig kompilieren von der Architektur bzw. besser der Größe eines INT? Also wenn #if sizeof(int)==8 /* ... */ #endif. Wie macht man sowas? Dies funktioniert nicht.

[Chris Lux]

assert(sizeof(x) == 4);Kann man eigentlich auch abhängig kompilieren von der Architektur bzw. besser der Größe eines INT? Also wenn #if sizeof(int)==8 /* ... */ #endif. Wie macht man sowas? Dies funktioniert nicht.
du koenntest einfach zwei versionen programmieren:

#include <boost/cstdint.hpp>

inline boost::uint32_t next_power_of_two(boost::uint32_t x)
{
--x;

x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;

return (++x);
}

inline boost::uint64_t next_power_of_two(boost::uint64_t x)
{
--x;

x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
....

return (++x);
}

[Trap]

AMDs Barcelona CPUs haben eine "leading zero count" Instruktion, die eignet sich für solche Sachen ziemlich gut.

[transstilben]

AMDs Barcelona CPUs haben eine "leading zero count" Instruktion, die eignet sich für solche Sachen ziemlich gut.

OK, aber Bit Scan Reverse hat O(1), also was soll das ?

[Trap]

OK, aber Bit Scan Reverse hat O(1), also was soll das ?
BSR behandelt 0 nicht sinnvoll.

Sonst hab ich keine Erklärung für die Einführung der neuen Instruktion gefunden.

[transstilben]

BSR behandelt 0 nicht sinnvoll


Stimmt. Das ist eine gewisse Einschränkung. Allerdings finde ich, daß die Behandlung von 0 durch BSR schon sinnvoll ist. Das Zero-Flag wird gesetzt
und das Ergebnis ist undefiniert. Macht doch Sinn, oder ? ;)
Wenn man hier gern 32 oder 64 sehen würde, sollte das mit einem bedingten "move" (CMOVZ) machbar sein, ohne die Sprungvorhersage
in Schwierigkeiten zu bringen. :)