Schnelle binäre Algorithmen

Manchmal tauchen in Foren richtig nette Sachen, die einen in Erstaunen setzen, wie schnell und einfach manches zu lösen ist. (siehe Thread)
Zwei interessante Fragen, die mich auch schon öfter beschäftigt haben sind hier mal erwähnt und als C++ Code wiedergegeben. Bisher habe ich diese immer mit einer entsprechenden Schleife und Shift-Operatoren gelöst.

1. Wie kann man schnell prüfen ob ein Integer eine 2er Potenz ist?

Der Algorithmus ist so verblüffend einfach, dass man sich fragen muss, warum man noch nicht von selbst drauf gekommen ist:

bool IsPowerOf2(int n) 
{ 
 return (n & (n - 1))==0; 
}

Tricky: Wenn mehr als zwei Bits gesetzt sind, bleibt bei der gegebenen Arithmetik mindestens das höchste Bit stehen.

❗ Nach diesem Algorithmus ist 0 übrigens auch eine Power of 2!

2. Wie findet man die nächste 2er Potenz einer gegebenen Zahl?

Diese Frage stellt sich für mich immer wieder, wenn ich binäre Suchen durchführe.
Auch hier gibt es eine statische Lösung, die ich hier mal wiedergebe und die sowohl für 32bit als auch für 64bit funktioniert und direkt in entsprechende Assembler Befehle umgesetzt wird.
Der Code vermeidet einen 32bit shift, da das Ergebnis in einem 32bit C++ Compiler undefiniert ist (Warning C4293).

int GetNextPowerOf2(int n) 
{ 
 // Code works for 32bit and 64bit 
 ­­­­-­-n;    
 n |= n >> 1; 
 n |= n >> 2; 
 n |= n >> 4; 
 n |= n >> 8; 
 n |= n >> 16; // Sufficient for 32bit 
 n |= n >> 16; // for a 64bit System we need a new 32bit shift (n>>32) 
 n |= n >> 16; // but this operation is undefined on a 32bit system 
               // so we use 2 16bit shifts. (C4293) 
 return n+1; 
}

Oft genug wird das höchste gesetzte Bit gesucht. In diesem Fall einfach den Startwert oder das Ergebnis um eine Bitposition shiften.

Tricky: Das höchste Bit wird nach der Subtraktion einfach auf alle niederen Bits übertragen.

❗ Auch hier ist das Verhalten bei 0 eigentümlich. Die nächste 2er Potenz auf 0 ist mit diesem Algorithmus 0!

Die entsprechenden Algorithmen sind hier auf dieser Seite beschrieben:
http://en.wikipedia.org/wiki/Power_of_two#Fast_algorithm_to_check_if_a_number_is_a_power_of_two

Google Code Search…

Irgendwie ist das total an mir vorbeigegangen: Google Code Search.
Ich glaube ich gehe zu wenig auf Entdeckungsreise im Netz ;)…

Genial einfach nach Code suchen! Wirklich beeindruckend, vor allem auch durch die Nutzungsmöglichkeit von Regular Expressions.
Mich begeistert vor allem, die Möglichkeit den Sourcecode direkt einsehen zu können. Auch die Nachbardateien aus der Projektstruktur zu sind nur einen Mausklick weit entfernt. Man kann ganze Projekte zu studieren ob sie einem bei einem Problem helfen können ohne das man sie gleich herunter lädt und entpacken muss.

Einzig die Reihenfolge (Ranking) ist irgendwie suboptimal. Man muss schon einiges an Code ansehen oder entsprechend viel Stichworte angeben um die vielen Hits effektiv zu reduzieren.

Warum eigentlich CallWindowProc aufrufen, wenn man einen Zeiger auf die alte WndProc hat?

Wenn man mit GetWindowLong(Ptr) und GWL_WNDPROC die Adresse einer Fenster Prozedur ermittelt hat, warum muss man eigentlich CallWindowProc aufrufen und nutzt nicht direkt den Zeiger? Geht das denn überhaupt? 😕

Nein es geht nicht und man sollte es gar nicht versuchen ❗

In Win16 ging das noch. Aber das was durch GWL_WNDPROC geliefert wird ist seit Einführung von Win32 nicht unbedingt ein Funktionszeiger mehr.  Oft ist es eine Struktur.
Warum? Das ganze wurde gemacht um Unicode Kompatibilität zu erreichen.
Fenster sind nicht nur Thread afin, nein, sie sind auch Unicode bzw. MBCS afin (wenn man das so sagen kann). Je nachdem ob es eben mit CreateWindow(Ex)A oder CreateWindow(Ex)W erzeugt wurde.

Wenn also ein Unicode Fenster von einer Nicht-Unicode Fenster-Prozedur gesubclassed wird (oder umgekehrt), dann muss hier eine Konvertierung stattfinden. Seit dem wir Themed Style mit XP bekommen haben, tritt dies übrigens häufig auf. Denn die Fenster im XP-Stil werden meistens intern als Unicode Fenster verwaltet oder angelegt.
Für diese Konvertierungsarbeit wird eine Struktur angelegt und diese Struktur wird dann in GWL_WNDPROC eingetragen. Dann haben wir eben keinen Funktionszeiger mehr, sondern eher ein Handle. Und nur CallWindowProc weiß wie man eben damit umzugehen hat…

Details hier in dem Artikel Safe Subclassing in Win32

VS-Tipps & Tricks: Insert Tracepoint, der nette Helfer beim Debuggen

Breakpoints kennt jeder, aber Tracepoints!?!

Den Menüpunkt Insert Tracepoint findet man im Kontext Menü des Editors.
Wer kennt das nicht? Man ist mitten in einer Debug-Session, aber man müsste jetzt eine Variable beobachten, wie sie sich entwickelt. Manchmal ist es einfach ungünstig einen Breakpoint zu stetzen, weil der Timing, Focus und manches andere ändert. Zudem, Breakpoints sind lahm und die F5-Taste will man auch icht kaputt machen. Ein TRACE Statement wäre super. Aber jetzt den Code ändern? Evtl. klappt das Edit&Continue nicht oder man kann es nicht einrichten, weil man eine Release Version debuggt.

Hier ist ein Tracepoint ideal. Er leistet das, was ein TRACE Statement auch leistet, nur ohne Code Änderung. Einfach Insert Tracepoint auswählen und angeben was man gerne sehen möchte.
z.B.: $FUNCTION bReset={bResetClipRegion} bEmpty={bEmptyClipRect}

Es stehen einige Makros zur Verfügung, die direkt im Dialog erklärt werden. Gigantisch nützlich sind die Variablen $FUNCTION , $CALLER, und $CALLSTACK. Das geht auch mit Variablen, die sich im aktuellen Kontext befinden, wie in meinem Beispiel zu sehen. Einfach die Variablen in geschweifte Klammern setzten und das war es schon.

Die Ausgabe erfolgt umgehend in der Debug-Ausgabe:
RedirectEraseBkgndToParent(CWnd *, CDC *) bReset=true bEmpty=true
RedirectEraseBkgndToParent(CWnd *, CDC *) bReset=true bEmpty=true
RedirectEraseBkgndToParent(CWnd *, CDC *) bReset=true bEmpty=true

Absolut super ist, dass man dazu noch nicht mal einen Breakpoint setzen muss. D.h. man kann während der Laufzeit einfach so einen Tracepoint setzen ohne große Eingriffe in die Software.

Und ganz ohne Probleme lässt sich auch ein Breakpoint in einen Tracepoint umwandeln und umgekehrt. Bei den Eigenschaften eines Breakpoints im Kontextmenü kann man die Eigenschaft When hit… entsprechend bearbeiten. Nimmt man den Haken bei Continue Execution heraus, dann hat man einen normalen Breakpoint. Setzt man den Haken bei Continue Execution, so macht man aus einem Breakpoint einen Tracepoint, man muss nur noch eine entsprechende Nachricht nach Wunsch angeben, die in der Debug Ausgabe angezeigt werden soll.

❗ Beachten muss man jedoch, dass die Performance schlechter ist als bei einem eingebauten TRACE. Denn ein Breakpoint wird ausgelöst und der Debugger übernimmt kurzfristig die Kontrolle.

VS-Tipps & Tricks: Edit.GotoBrace (Strg+´) kann noch mehr

Mit Strg+´ kann man ja bekannterweise die nächste passende schließende bzw. geöffnete Klammer finden. Mit Umschalt+Strg+´ kann man diesen Bereich auch direkt markieren. Diese Funktion ist nicht unbedingt eine Neuigkeit.

Viele wissen jedoch nicht, dass man auch passende #if, #ifdef, #ifndef, #else, #elif, #endif Direktiven damit anspringen kann. Man muss dazu das Caret einfach nur auf die entsprechende Direktive platzieren und mit Strg+´ springt man zum nächsten #else, #endif oder wieder an den Kopf des ersten #if Blockes.

Auch in diesem Fall kann man auf einfache Weise mit Umschalt+Strg+´ den entsprechenden Codeblock markieren.

„Elevated“ Programme unter Vista / Windows 7 / Windows 8 / Windows 10 haben auf einmal keine gemappten Laufwerke mehr

Ist man Administrator unter Vista, Windows 7, Windows 8 oder Windows 10 und UAC ist aktiviert, dann existieren technisch zwei Sicherheits -Tokens. Ein Token mit den vollen Administrativen Rechten und ein reduziertes gefiltertes Token, ohne Admin-Rechte.

Wenn man sich anmeldet und Netzwerklaufwerke (Freigaben/Shares) zugeordnet werden, dann erfolgen diese Laufwerksmappings in dem Token mit den reduzierten Rechten.

Startet man nun eine Session mit angehobenen, vollen administrativen Rechten, dann sind die vorher zugeordneten Netzwerklaufwerke in dieser Session nicht sichtbar.
Ein etwas ungewöhnliches aber durchaus logisches Verhalten.
Das Logon Skript läuft eben nicht in dem selben Sicherheitskontext, wie Prozesse, die man mit vollen angehobenen Rechten startet. Defakto sind es wirklich zwei verschiedene Logon’s mit zwei verschiedenen Logon-ID’s.

Mit einem einfachen setzen eines Registry Keys kann man jedoch erreichen, dass auch die angehobenen Admin-Sessions die gleichen Laufwerkmappings erhalten:

HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Policies\System
EnableLinkedConnections = 1 (DWord)

Aber leider ist dieser Schalter nicht als Standard gesetzt.
Ärgerlich wird dies, wenn man ein kleines Setup-Programm schreiben will, dass einige Daten aus dem Nezwerk kopieren soll und dem man ein entsprechendes requireAdministrator-Manifest gibt. Startet man dieses Programm findet es auf einmal nicht mehr die Laufwerke, die eben noch verfügbar waren. Umgehen kann man das ganze nur in dem man UNC-Dateinamen verwendet.

Beschrieben wird dies auch hier auch in diesem KB Artikel und besonders dieser TechNet Artikel.

9. Award als deutscher MVP für Visual C++

Es ist zwar schon wieder 8 Tage her, seit ich die Email erhalten habe, aber es ist für mich, wie für jeden anderen MVP, immer wieder spannend ob ein MVP-Titel erneuert wird.
Selbstverständlich ist das nicht. Gerade in den letzten beiden Jahren sind viele meiner „alten“ Kollegen als MVPs ausgeschieden.

Dies ist nun mein neunter Award als deutscher C++ MVP. Die Urkunde lässt untypischer Weise zwar noch auf sich warten, aber die Bestätigung habe ich bereits. 🙂

BTW: Wer mich mal persönlich kennen lernen will, der kann mich voraussichtlich in Frankfurt beim großen Launch „Ready for take off“ von Windows Server 2008, SQL Server 2008 und Visual Studio 2008 vom 19.-21. Februar 2008 treffen.

Nachtrag vom 19.10.2007:
MVP Award

Gibt es einen Unterschied zwischen HMODULE und HINSTANCE?

Ja! Wenn man noch Windows 16bit programmiert. 😉

Nein! Wenn es sich um Win32 dreht.

In Kurzfassung:
❗ Seit Win32 ist HMODULE/HINSTANCE nichts anderes als die Ladeadresse des Modules, egal ob es sich hier um eine EXE oder DLL handelt.
HMODULE und HINSTANCE sind austauschbar in jeder Beziehung.

Wer mehr darüber lesen will findet bei The Old New Thing, diesen Artikel der den historischen Aspekt erläutert.

VS-Tipps & Tricks: Die Combobox im Property Fenster des Dialog Editors

Unscheinbar aber sehr effektiv zum Ändern von großen Dialogen ist die Combobox im Eigenschaftsfenster.
In den meisten Fällen steht in dieser Combobox nur der Name des Objektes, das ausgewählt ist und eine weitere Auswahl ist dann oft hier nicht möglich.

Editiert man jedoch einen Dialog, dann kann man mit dieser Combobox, sehr effektiv und schnell Controls gezielt auswählen. Besonders wenn man Controls übereinander legt weil diese ein oder ausgeblendet werden wird es schwierig diese Controls gezielt mit der Maus zu markieren.
Mit der Combobox kein Problem.
Die Reihenfolge in der Combobox ist die alphabetisch sortiert nach den Namen der Control IDs. Auch das erleichtert die Auswahl, wenn man ein Control direkt anhand seiner ID finden will. Hat man den Dialog nicht designed und will ein Control identifizieren, dass durch einen bestimmten Code gesteuert wird, ist das mit dieser Combobox ein Klax.

Auch wenn man die Maus nicht verwenden will kann man mit dieser Combobox schnell navigieren:
Alt+Eingabetaste, wählt das Eigenschaftsfenster, mit 3 x Tab oder 2 x Umschalt+Tab kommt man in die Combobox, die man dann mit den Cursor-Tasten, bzw. Alt+Pfeilrunter bedienen kann. Mit der Escape-Taste kommt man zurück in die Editoroberfläche.