Blog | Holger Stehle

Zahl auf Zweierpotenz prüfen 👍 👎

Für manche Algorithmen bestehen Optimierungsansätze, wenn eine zu untersuchende Zahl eine Zweierpotenz ist. Daher möchte ich mit diesem Beitrag aufzeigen, wie sich diese Problemstellung möglichst effizient lösen lässt.

Naive Ansätze arbeiten mit Schleifen und prüfen schrittweise alle in Frage kommenden Zweierpotenzen – es ist leicht einzusehen, dass dieses Vorgehen insbesondere für größere Zahlen eher mäßig effizient ist. Alternativ könnte man auf die Idee kommen, das Problem mit Logarithmen zu lösen – hier kann es jedoch zu Rundungsproblemen kommen. Wir sollten uns daher die Struktur entsprechender Zahlen einmal genauer ansehen:

Zweierpotenzen

010203040506

                  Dualzahl     Dezimalzahl--------------------------------------------       2⁰               1            1       2¹              10            2       2²             100            4       2³            1000            8

Offensichtlich ist bei einer Zweierpotenz 2ⁿ demnach das (n + 1)-te Bit auf 1 gesetzt und alle ggf. nachfolgenden Stellen besitzen den Wert 0 – was kaum eine Überraschung darstellen sollte. Wir müssen nun jedoch nicht jedes Bit einzeln prüfen, ob die Zahl auf dieses "Muster" passt, sondern können uns das Bitmuster der Zahl 2ⁿ – 1 zu Nutze machen:

Voränger von Zweierpotenzen

010203040506

                  Dualzahl     2ⁿ – 1 (dual)--------------------------------------------       2⁰               1            0       2¹              10           01       2²             100          011       2³            1000         0111

Wie selbstverständlich zu erwarten war, muss der Vorgänger ein inverses Bitmuster besitzen. Dies hilft uns insofern weiter, als dass wir diese beiden Zahlen mit einem bitweisen UND verknüpfen und auf Gleichheit mit 0 prüfen können, was bei Zweierpotenzen zutreffen muss.

In C# könnte die Implementierung beispielsweise wie folgt aussehen:

Zahl auf Zweierpotenz prüfen (Basis)

public static bool IsPowerOfTwo(uint number) {    return ((number & (number – 1)) == 0);}

Dieses Vorgehen liefert jedoch auch für die Zahl 0 den Wert true zurück. Wir prüfen diesen Fall daher separat:

Zahl auf Zweierpotenz prüfen (Erweiterung)

01020304050607

public static bool IsPowerOfTwo(uint number) {    return (        (number != 0)          &&        ((number & (number – 1)) == 0)    );}

Aufrufer-Informationen für Methoden in C# 👍 👎

Manchmal kann es sinnvoll sein, sich Informationen über den Aufrufer einer Methode übermitteln zu lassen. Wir werden dies im Folgenden mit zwei praxisnahen Beispielen genauer untersuchen.

Zuerst möchten wir ein (einfaches) Logging-System implementieren:

Logging implementieren

010203040506070809

public static class Logging {    public static void Enter(string caller) {        Trace.WriteLine(caller + " betreten");    }
    public static void Leave(string caller) {        Trace.WriteLine(caller + " verlassen");    }}

Diese Klasse können wir nun beispielsweise wie folgt verwenden:

Logging verwenden

010203040506070809

static void Main(string[] args) {    Logging.Enter("Main");
    /**     * Aktionen ausführen    **/
    Logging.Leave("Main");}

Nun stellt uns jedoch das .NET-Framework ein spezielles Attribut CallerMemberName zur Verfügung, um diesen Prozess ein wenig zu optimieren – dazu müssen wir unsere Klasse minimal ergänzen:

Logging-Implementierung erweitern

010203040506070809

public static class Logging {    public static void Enter([CallerMemberName] string caller = "") {        Trace.WriteLine(caller + " betreten");    }
    public static void Leave([CallerMemberName] string caller = "") {        Trace.WriteLine(caller + " verlassen");    }}

Der Parameter caller wird nun beim Aufruf automatisch festgelegt, so dass die explizite Angabe in Main bei gleichem Ergebnis entfallen kann.

Ich möchte noch einen weiteren praktischen Anwendungsfall mit INotifyPropertyChanged demonstrieren:

INotifyPropertyChanged mit impliziten Aufruferinformationen

01020304050607080910111213141516171819202122232425262728293031323334353637

public class Person : INotifyPropertyChanged {    public event PropertyChangedEventHandler PropertyChanged;

    private string name;    public string Name {        get {            return this.name;        }        set {            if(this.name != value) {                this.name = value;
                this.OnPropertyChanged();            }        }    }
    private int age;    public int Age {        get {            return this.age;        }        set {            if(this.age != value) {                this.age = value;
                this.OnPropertyChanged();            }        }    }

    private void OnPropertyChanged([CallerMemberName] string propertyName = "") {        this?.PropertyChanged(this, new PropertyChangedEventArgs(propertyName));    }}

Dies vereinfacht die Verwendung dieser Schnittstelle, die insbesondere zur Datenbindung im Rahmen der WPF Verwendung findet – vor allem bei Refaktorierungsmaßnahmen. Das Verhalten ist wie erwartet:

Objekt verwenden

0102030405060708091011121314151617

Person ich = new Person() {    Name = "Holger",    Age = 25};
ich.PropertyChanged += (sender, e) => {    Debug.WriteLine("Der Wert der Eigenschaft '{0}' hat sich geändert!",        (object) e.PropertyName    );};
ich.Age = 26;
/** * Das Ereignis "PropertyChanged" wird ausgelöst * und "PropertyName" implizit auf "Age" gesetzt.**/

Weitere Informationen (und hilfreiche Attribute) lassen sich im MSDN nachlesen.

Tracker für Projekte von CODERS-ONLINE 👍 👎

Zur effizienten Handhabung von Fehlern, Fragen und Vorschlägen zu meinen Projekten steht nun auch ein zentrales Tool bereit. Dieses ist für meine öffentlichen Projekte von jedem frei einsehbar und auch nutzbar.

Die meisten meiner Projekte bieten bereits eine integrierte Möglichkeit zur Meldung von Fehlern. Dies trifft u. a. auf die Übersetzung der Lua-Dokumentation und das Städteportal zu. Diese Projekte sind nun in der Lage, Einträge über einen Webservice direkt einzureichen. Ihr könnt deren Funktionen hierfür also weiterhin wie gewohnt nutzen. Es ist außerdem geplant, die Integration auf Feedback für diese Webpräsenz hier auszudehnen.

Zum Schutz vor Spam bitte ich um Verständnis dafür, dass Einträge und Kommentare nicht sofort ersichtlich sind, sondern erst freigeschaltet werden müssen. Konstruktive Kritik wird jedoch selbstverständlich gerne freigegeben.

» Tracker besuchen

Quelltext des .NET-Frameworks veröffentlicht 👍 👎

Einige werden es bereits erfahren haben, dennoch möchte auch ich darauf hinweisen, dass Microsoft weitere große Teile des .NET-Frameworks öffentlich zur Verfügung stellt. Unterstützt wird das Vorhaben durch Roslyn.

Die Inhalte sind dabei durchgängig interaktiv gestaltet und stehen unter der Reference Source License.

Dateisystem mit C# überwachen 👍 👎

Manchmal kann es sinnvoll sein, ein Verzeichnis auf Änderungen zu überwachen – beispielsweise, um festzustellen, ob eine Datei hinzugefügt oder entfernt wurde. Statt nun periodisch das Verzeichnis zu durchsuchen und selbst eine Sammlung der jeweiligen Zustände und eine anschließende Überprüfung auf Änderungen durch Vergleich dieser durchzuführen, bietet sich die Verwendung der FileSystemWatcher-Klasse an.

Für unser konkretes Beispiel möchten wir das Verzeichnis "X:\Server\Logs" auf neue *.log-Dateien überwachen und erzeugen dazu eine entsprechende Instanz der o. g. Klasse:

FileSystemWatcher instanziieren und konfigurieren

01020304

FileSystemWatcher fileSystemWatcher = new FileSystemWatcher(@"X:\Server\Logs") {    EnableRaisingEvents = true,    Filter = "*.log"};

Abschließend abonnieren wir das Ereignis Created, welches bei neuen Dateien ausgelöst wird:

Ereignis abonnieren

010203040506

fileSystemWatcher.Created += (sender, e) => {    /**     * e.Name enthält nun den     * Namen der neuen Datei.    **/};

Selbstverständlich bietet die Klasse die Möglichkeit einer detaillierteren Konfiguration und weitere Ereignisse.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23 24 25 26

Projektverweise

BitStadt – Stadtportal
Berlin · Hamburg · Amsterdam

Kategorien / Archiv | Übersicht

PHP-Funktionen in C# (136)
Wörterbuch (257)