Präfixlänge von IPv4 Adressmasken berechnen.

TNA

Ich brauche von einer Adressmaske die Präfixlänge also auf gut deutsch: Die Anzahl an zusammenhängenden Einsen am Anfang eines Integers berechnen. Wie macht man das am geschicktesten?

Nexus

Schon auf Bit Twiddling Hacks nachgeschaut? (Zuerst negieren könnte helfen.)

TNA

Im Prinzip wäre das ja 32 - "Count the consecutive zero bits (trailing)". Finde ich jetzt nicht so schön aber dürfte es tun.

volkard

TNA schrieb:

Im Prinzip wäre das ja 32 - "Count the consecutive zero bits (trailing)". Finde ich jetzt nicht so schön aber dürfte es tun.

Hä? Bau Dir eine Funktion count_trailing_zeros und tausch ihre Implementierung per #ifdef gegebenenfalls gegen compilerintrinsics oder inline asm aus.

TNA

volkard schrieb:

TNA schrieb:

Im Prinzip wäre das ja 32 - "Count the consecutive zero bits (trailing)". Finde ich jetzt nicht so schön aber dürfte es tun.

Hä? Bau Dir eine Funktion count_trailing_zeros und tausch ihre Implementierung per #ifdef gegebenenfalls gegen compilerintrinsics oder inline asm aus.

Ich brauche ja eigentlich die Anzahl der Einsen und nicht die der Nullen und müsste das daher umrechnen. Mit deiner Antwort kann ich aber leider auch wenig anfangen.

Du kannst auch direkt die gesetzten Bits zählen?!
Nexus' Link hat einen ganzen Sack voll von Algorithmen zum Thema "Counting bits set".

volkard

TNA schrieb:

Mit deiner Antwort kann ich aber leider auch wenig anfangen.

Es gibt auf vielen Prozessoren einen eigenen Prozessorbefehl dafür.
http://en.wikipedia.org/wiki/Find_first_set
http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html __builtin_ctz

#if defined MSVC
int count_trailing_zeros(unsigned int x){
   __asm bsf x;
}
#elif defined GCC
int count_trailing_zeros(unsigned int x){
   return __builtin_ctz(x);
}
#else
int count_trailing_zeros(unsigned int x){
   //kopiert aus "bit twiddleing hacks"
}
#endif

Und dann ist

int getPrefixLength(int addr){
   return count_trailing_zeros(~addr);
}

recht schmerzfrei.

(Code nur zu Demonstrationszwecken, habe ihn nicht im Mindesten geprüft.)