Bits in UInt64 ermitteln

  • C#
  • .NET (FX) 1.0–2.0

Es gibt 5 Antworten in diesem Thema. Der letzte Beitrag () ist von RodFromGermany.

    Bits in UInt64 ermitteln

    Moin,
    Ich brauch mal etwas Hilfe, - stehe vor einem Problem und weiß nicht wie ichs coden soll :)
    Also, ich habe einen beliebigen UInt64, sagen wir 900001447.
    Ich muss nun die Anzahl der 1-Bits in der Zahl ermitteln und returnen, wobei der UInt64 der Input-Parameter der Funktion darstellen soll.
    Wenn ich 900001447 im Calculator eingebe sehe ich folgendes:



    Wenn man jetzt alle einsen Zählt kommt man auf 8.
    Für den Input 900001447 soll die Funktion also den Integer-Wert 8 returnen.
    Wie kann ich das am elegantesten und effizientesten lösen, iwie mit ein paar Bitshift Operatoren vllt?
    Hoffe mir kann jemand helfen.

    Lg
    Rikduo
    C# Developer
    Learning C++

    Artentus schrieb:

    Mit Bitshifting ist das machbar, ja. Shifte 64 mal um 1 Bit nach rechts und prüfe jeweils, ob das niedrigste Bit 1 ist (value & 0x1 == 1).


    Hey,
    Danke für die Antwort schonmal.
    Ich habe jetzt auch nochmal ein bisschen recherchiert, und bin mit folgendem zugange:

    C#-Quellcode

    1. ​ private static short CountBits(long x)
    2. {
    3. x = x - ((x >> 1) & 0x55555555);
    4. x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    5. x = (x + (x >> 4)) & 0x0F0F0F0F;
    6. x = x + (x >> 8);
    7. x = x + (x >> 16);
    8. return (short)(x & 0x0000003F);
    9. }


    Allerdings wird für den Input 0x900001447 die Zahl 6 returned, obwohl 8 returned werden sollte.
    Wenn man nochmal einen Blick auf mein Bild vom Calculator oben wirft, erweckt das stark den Eindruck das die Obere Reihe von Bits ausgelassen wurde? ;o
    C# Developer
    Learning C++

    Ich kann auch ehrlich gesagt deinem Code nicht folgen. Ich hätte das ja einfach so gemacht:

    C#-Quellcode

    1. ​int CountBits(long value)
    2. {
    3. int count = 0;
    5. for (int i = 0; i < 63; i++, value >>= 1)
    6. {
    7. if (value & 0x1 == 1)
    8. count++;
    9. }
    11. return count;
    12. }

    Sind zwar mehr Operationen als bei dir, aber funktioniert dafür. ^^

    Artentus schrieb:

    Ich kann auch ehrlich gesagt deinem Code nicht folgen. Ich hätte das ja einfach so gemacht:

    C#-Quellcode

    1. int CountBits(long value)
    2. {
    3. int count = 0;
    5. for (int i = 0; i < 63; i++, value >>= 1)
    6. {
    7. if (value & 0x1 == 1)
    8. count++;
    9. }
    11. return count;
    12. }

    Sind zwar mehr Operationen als bei dir, aber funktioniert dafür. ^^


    Danke schonmal, habe gerade noch ne andere Interessante Lösung gefunden, die ich - auch wenn sie super funzt, nicht ganze kapiere :D

    C#-Quellcode

    1. private static int CountBits(ulong i)
    2. {
    3. i = i - ((i >> 1) & 0x5555555555555555UL);
    4. i = (i & 0x3333333333333333UL) + ((i >> 2) & 0x3333333333333333UL);
    5. return (int)(unchecked(((i + (i >> 4)) & 0xF0F0F0F0F0F0F0FUL) * 0x101010101010101UL) >> 56);
    6. }


    EDIT:
    Habs jetzt auch, ziemlich interessant ^^

    C#-Quellcode

    1. static int HammingWeight(ulong x)
    2. {
    3. x = (x & 0x5555555555555555) + ((x >> 1) & 0x5555555555555555); //put count of each 2 bits into those 2 bits
    4. x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333); //put count of each 4 bits into those 4 bits
    5. x = (x & 0x0f0f0f0f0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f0f0f0f0f); //put count of each 8 bits into those 8 bits
    6. x = (x & 0x00ff00ff00ff00ff) + ((x >> 8) & 0x00ff00ff00ff00ff); //put count of each 16 bits into those 16 bits
    7. x = (x & 0x0000ffff0000ffff) + ((x >> 16) & 0x0000ffff0000ffff); //put count of each 32 bits into those 32 bits
    8. x = (x & 0x00000000ffffffff) + ((x >> 32) & 0x00000000ffffffff); //put count of each 64 bits into those 64 bits
    9. return (int)x;
    10. }


    Hier ists auch erklärt wies funzt : https://en.wikipedia.org/wiki/Hamming_weight

    EDIT2 :
    Hier ist noch ne schnellere Variante die nur 17 Bitshifting operationen durchführt ;)

    C#-Quellcode

    1. ​ static int HammingWeight(ulong x)
    2. {
    3. ulong m1 = 0x5555555555555555;
    4. ulong m2 = 0x3333333333333333;
    5. ulong m4 = 0x0f0f0f0f0f0f0f0f;
    6. x -= (x >> 1) & m1;
    7. x = (x & m2) + ((x >> 2) & m2);
    8. x = (x + (x >> 4)) & m4;
    9. x += x >> 8;
    10. x += x >> 16;
    11. x += x >> 32;
    12. return (int)x & 0x7f;
    13. }

    C# Developer
    Learning C++

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „Rikudo“ ()

    Rikudo schrieb:

    schnellere Variante die nur 17 Bitshifting operationen durchführt
    Grauselig.
    Ich denke mal, wenn ich Deinen Algo mit der von @Artentus vergleiche, würde ich immer seinen nehmen, auch wenn Deiner 2 Takte weniger braucht.
    Letztenendes ist entscheidend, wie lange ich brauche, diesen kryptischen Algorithmus oder den linearen zu verstehen und mit welchem Aufwand ich ggf. Änderungen implementieren müsste.
    Und mit wieviel Worten ich den einen oder anderen erklären könnte.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

Facebook