Präprozessor-Trick gesucht

darum nicht

#define shifted(x) ((x&0x30)>>4)

Das mit der Turing-Vollständigkeit halte ich für eine urbane Legende. 
Aber ich mag mich irren. Gib doch mal an, wo Du das gelesen hast.

Das Problem ist, das Du mit dem Preprozessor nur Textersatz machen 
kannst. Auch Parameter werden nur textuell ersetzt. Die Berechnungen 
erfolgen durch den Compiler. Dabei werden nur konstante Ausdrücke 
berechnet.

Letzlich suchst Du also nach einer Funktion, die zur Laufzeit das nötige 
tut.
Da wird die Sache dann schon etwas einfacher.
Zunächst kannst Du eine Tabelle benutzen. Das ist das schnellste.
Es geht ja darum die Bitnummer des niederwertigsten gesetzten Bits zu 
ermitteln, nicht wahr?

1

/* Die bits zahlen ab 1 und nicht ab null, weil sonst der Fall, das kein Bit gesetzt ist nicht erkannt werden kann */

2

3

/* dezimal:           0, 1, 2, 3, 4, 5, 6, 7, 8, ...

4

uint8 bitnummer [] = {0, 1, 2, 1, 3, 1, 2, 1, 4, ...}

Mir fallen da auf Anhieb zwei berechnende Verfahren ein mit denen man 
auch die Tabelle erzeugen könnte.

Das wiederum einfachste wäre selbst ein Bit durchzuschieben, und zu 
zählen, wann denn die Und-Verknüpfung ungleich Null ist.

Das etwas komplizierter würde den Logarithmus zur Basis 2 errechnen, 
wobei vorher die höherwertigen Bits entfernt werden müssen.

Oh. Das von Peter ist natürlich recht auch möglich und sogar recht 
hübsch.

@ Vlad

>>Letzlich suchst Du also nach einer Funktion, die zur Laufzeit das nötige  tut.
>Ebend nicht, es soll zur Compiletime gemacht werden.
>Das von Peter sieht mir am gesten aus.

Na aber, das von Peter rennt ja auch erst zur Laufzeit. Das kann nicht 
schon zur Compilezeit vereinfacht werden.

>> Na aber, das von Peter rennt ja auch erst zur Laufzeit. Das kann nicht
>> schon zur Compilezeit vereinfacht werden.

>Das ist falsch. #define wird vom CPP abgearbeitet und alle Parameter
>dafür müssen zur Übersetzungszeit bekannt sein.

So? Na, mit der Ansicht komme ich seit 20 Jahren durchs 
Programmiererleben. Wenn sie also auch falsch sein sollte, dann 
funktioniert es wenigstens wenn man davon ausgeht das sie richtig ist.

>Das ist falsch. #define wird vom CPP abgearbeitet und alle Parameter
>dafür müssen zur Übersetzungszeit bekannt sein.

Was fürn Ding?
Der Präprozessor machrt doch nichts anderes als eine Textersetzung, 
ausser wenn es sich um eine Berechnung mit Konstanten handelt. Dann 
rechnet er sich auch aus. Deswegen nennt sicjh das Ding ja auch Makro 
und erhöht die Übersichtlichkeit.

>Das ist falsch. #define wird vom CPP abgearbeitet und alle Parameter
>dafür müssen zur Übersetzungszeit bekannt sein.

Das ist noch falscher. Der CPP ersetzt grundsätzlich nur Text. Und 
solange da eine Variable x oder i drin ist, die erst zur Laufzeit 
bekannt ist, macht den Rest der Compiler.

Wenn alle Werte schon zur Compilezeit definiert wären, würde das 
narütlich auch zur Compilezeit berechnet, aber nicht durch den CPP, 
sondern durch den Compiler. Allerdings kann bei der Aufgabenstellung 
eigentlich nicht alles bekannt sein.


Oliver

Der Präprozessor rechnet wenig bis garnix. Selbst wenn man mit dem so 
einen ternären Operator vergewaltigt, ersetzt er nur die Variablen und 
lässt den Compiler rechnen. Wenns nachher konstant ist, optimiert der 
Compiler es, wenn nicht, läufts wohl auf irgendeine verzweigte 
Konstruktion raus und gut ist.

Wo der Präprozessor 'rechnet', das sind z.B. die Bedingungen hinter 
'#if' und '#elif'.

>Dann lies nochmal das Eingangsposting: Dort steht nichts von einer
>Bitmaske, die erst zur Laufzeit bekannt ist, sondern es ist nach einem
>Präprozessormakro gefragt, das die Verschiebung für die Maske berechnet.
>Damit ist implizit, daß die Maske zur Übersetzungszeit bekannt sein
>muß.

Weder der Text von Dir, den ich hier zitiere, noch die Fragestellung 
implizieren, dass der Makroparameter bekannt sein muss .
Man kann ihn so verstehen und das habe ich übersehen. Es wäre aber auch 
möglich gewesen, dass das "signal" der Makroparameter ist und so habe 
ich es aufgefasst.

Es wäre für mich viel hilfreicher gewesen wenn Du geschrieben hättest.
"Ich verstehe die Fragestellung so, das das gesuchte Makro mit einem 
konstanten Wert aufgerufen werden soll".

Mein Irrtum basierte nicht darauf, das ich nicht wusste, das bei 
konstanten Ausdrücken, der Compiler vereinfachen kann. Die Nennung des 
Grundes, warum Du annimmst, das die die Vereinfachung in diesem Fall 
greift, hätte mehr gebracht als allgemeine (und dazu noch unpräzise) 
Aussagen.

Ooops: Das vorherige ist an Uhu gerichtet.

Der Assembler-Text sollte das klarstellen.

Die bereits geposteten Makros werden etwas unhandlich, wenn man auch 16-
oder 32-Bit-Masken verarbeiten will. Kompakter geht es so:

1

#define CTZ2(x) (~(x)&0x01)

2

#define CTZ4(x) ((x)&0x0003 ? CTZ2(x) : 2+CTZ2((x)>> 2))

3

#define CTZ8(x) ((x)&0x000f ? CTZ4(x) : 4+CTZ4((x)>> 4))

4

#define CTZ16(x) ((x)&0x00ff ? CTZ8(x) : 8+CTZ8((x)>> 8))

5

#define CTZ32(x) ((x)&0xffff ? CTZ16(x) : 16+CTZ16((x)>>16))

CTZ32 verhält sich im Wesentlichen wie __builtin_ctz auf 32-Bit-
Rechnern. Zu beachten: CTZ32(0) liefert 31, obwohl unendlich oder 32
logischer wären. Man könnte diesen Fall durch eine zusätzlich Abfrage
abfangen, was aber für Vlads Anwendung nicht nötig ist, da dort 0 nie
als Argument vorkommt. Auch __builtin_ctz sollte nicht mit dem Argument
0 aufgerufen werden, da dann das Ergebnis "undefined" ist.

Wenn man nur 8 Bits benötigt, kann man die beiden letzten Zeilen
weglassen.

Man könnte die Berechnung / Schiebeoperation noch etwas beschleunigen.
In der Lösung oben werden bis zu 7 Shiftoperationen fällig. Wenn man 
beispielsweise die Daten zunächst mit 0b00001111 verodert und prüft ob 
der Wert größer als null ist, befindet sich das erste lsb im unteren 
Nibble sonst möglicherweise im oberen. Danach werden nur noch maximal 4 
Shifts notwendig.

Zugegeben bei 8bit ist der Performancegewinn nicht so groß, bei 16 / 
32bit bringt das einiges.

Wenn der Code portabel sein sollte, ev auch bei versch GCC gibt es mit
der optimierung von ?: probleme, bzw wird diese zur Laufzeit und nicht
zur Kompilerzeit gemacht.
Also, bits zählen mit | oder +, ein ?: kann sehr schnell zu einem 
if/else
ausarten.

Meines Wissens ist nicht vorgeschrieben, dass der Compiler konstante
Ausdrücke immer zur Compilezeit berechnet (habe jetzt aber auch nicht
nachgeschaut). In einigen Fällen kann er aber gar nicht anders, bspw.
bei der Dimensionierung von Arrays:

1

static int arr[5>3 ? 4*5 : 5*6];  // legal -> Array mit 20 Elementen

Wenn der Compiler in der Lage ist, obigen Ausdruck auszurechnen, gibt es
keinen Grund, warum er das nicht auch in folgendem Fall tun sollte:

1

x = 5>3 ? 4*5 : 5*6;

Und weil der Compiler die Auswertung konstanter Ausdrücke sowieso können
muss, zählt diese üblicherweise auch nicht zu den Optimierungen. So
macht der GCC (aber wahrscheinlich auch jeder andere C-Compiler) auch
bei ausgeschalteter Optimierung aus dem zweiten Beispiel einfach x=20.
Das gleiche gilt für die in diesem Thread geposteten Makros, wenn das
Argument eine Konstante ist.

@Turing Vollständigkeit des Preprozessors
Ist er auch nicht:

Der Präprozessor erzeugt kontextfreie Gramatik (Genau ein nicht 
terminalsymbold wird durch eine beliebige Menge von terminal- und nicht 
terminalsymbolen ersetzt)

Damit ist der Preprozessor gleichmächtig zu nicht-determistischen 
Kellerautomaten. Diese sind bekanntlich nicht turingmächtig. Allerdings 
mächtiger als endliche Automaten.
Für viele nicht triviale Dinge also durchaus brauchbar :-D

Oh, den "Beweis" hab ich schon gefunden. Aber leider hat der einen 
Fehler.

Es reicht für die Turing-Vollständigkeit nicht eine große Menge von 
Turing-Maschinen nachbauen zu können, sondern muss zeigen, dass er alle 
TMs nachbilden kann.

Der seit Gödel standardisierte Weg dazu ist die UTM zu implementieren. 
In dem "Beweis" kann ich keine solche entdecken, oder irgendeine andere 
Induktion.

Es muss natürlich "eine UTM" heissen.

Ja, beim IOCCC gibt's schon krankes Zeug :-)
Schade dass der anscheinend überhaupt nicht mehr stattfindet; die 
bringen es nicht mal mehr fertig den Code der letztmaligen Gewinner 
(2006?) zu posten.