3. Kleiner Coding-Contest

Kleiner Coding-Contest


  • Und ich meinte natürlich "so wie im 2. Block halt auch". Aber du bist ja auch ein Schlauer und hast es trotzdem verstanden 🙂

    0
  • B

    Toller Hacker Contest. 🙂

    Und morgen kommt der Wettbewerb "Wer schreibt zuerst ein kompilierbares Program".

    WinAPI Forum lässt grüßen.

    0
  • M

    Der Threadtitel bezieht sich nicht aufs Hacken, sondern auf den alten Forumsnamen von Arcoth. Und klein wahrscheinlich weil er noch ein Schüler ist/war.

    0
  • Mod

    Mechanics schrieb:

    Der Threadtitel bezieht sich nicht aufs Hacken, sondern auf den alten Forumsnamen von Arcoth.

    Völlig falsch.

    Und klein wahrscheinlich weil er noch ein Schüler ist/war.

    Ebenfalls völliger Unsinn.

    Ich habe den Titel entsprechend angepasst... hier muss man wirklich das niedrigste Niveau voraussehen.

    Edit: @Mehanics: Ich nehme an, dass du das nicht ernst gemeint hast?

    0
  • ?

    Ich verstehe denn code nicht kann ihn mir jemand kurz erklären?

    bool foo(unsigned u, unsigned v) {
    return !(u & (u - 1)) // bitweise UND sagt einen doch ob u und u-1 beide ein bit an der gleiche position auf 1 gesetzt haben?
        && !(v & (v - 1)) // gleiche
        && u != v // u ist nicht gleich v
        && u && v; // das hier verstehe ich nicht :/
}

bool bar(int u, int v) {
    int temp1 = u - 1;
    int temp2 = v - 1;

    return temp1 >= 0 && !(temp1 & u)    //EDIT: (temp1 & u) => !(temp1 & u)
        && temp2 >= 0 && !(temp2 & v)    //EDIT: (temp2 & v) => !(temp2 & v)
        && u != v;
}
    0

  • Ach, Leute...

    http://www.catb.org/jargon/html/H/hacker.html

    0
  • M

    Arcoth schrieb:

    Edit: @Mehanics: Ich nehme an, dass du das nicht ernst gemeint hast?

    Natürlich nicht. Sorry, ich konnte einfach nicht widerstehen.

    0

  • theconflict schrieb:

    Ich verstehe denn code nicht kann ihn mir jemand kurz erklären?

    bool foo(unsigned u, unsigned v) {
    return !(u & (u - 1)) // bitweise UND sagt einen doch ob u und u-1 beide ein bit an der gleiche position auf 1 gesetzt haben?
        && !(v & (v - 1)) // gleiche
        && u != v // u ist nicht gleich v
        && u && v; // das hier verstehe ich nicht :/
}

    (u & (u - 1))
    Wenn du dir "u - 1" binär anguckst, wirst du feststellen, dass dabei das erste 1er Bit (=das mit dem niedrigsten Stellenwert) zu 0 geflippt wird, und alle 0er Bits davor werden zu 1 geflippt:

    u           u - 1
--------------------
xxxxxxx1    xxxxxxx0
xxxxxx10    xxxxxx01
xxxxx100    xxxxx011
xxxx1000    xxxx0111

    etc.
    Wenn man jetzt die linke und rechte Seite bitweise verundet, dann kommt dabei raus:

    u           u - 1       u & (u - 1)
-------------------------------------------
xxxxxxx1    xxxxxxx0    xxxxxxx0
xxxxxx10    xxxxxx01    xxxxxx00
xxxxx100    xxxxx011    xxxxx000
xxxx1000    xxxx0111    xxxx0000

    D.h. u & (u - 1) setzt einfach das erste 1er Bit auf 0.

    Und wenn das Ergebnis von "erstes 1er Bit auf 0 setzen" 0 ist, dann war vorher maximal ein Bit gesetzt.

    D.h. !(u & (u - 1)) heisst: hat u genau ein 1er Bit oder ist u gleich 0?

    Den "oder ist u gleich 0" Teil will man aber nicht, es sind ja nur Werte erwünscht die genau ein 1er Bit haben.
    => !(u & (u - 1)) && u

    Das ganze dann nochmal für v , und dann noch den Test ob u und v ungleich sind drangehängt:

    !(u & (u - 1))
&& u
&& !(v & (v - 1))
&& v
&& u != v

    Etwas umsortiert:

    !(u & (u - 1))
&& !(v & (v - 1))
&& u != v
&& u && v

    Tadaaa.

    0
  • ?

    Danke jetzt habe ich es verstanden :}

    0
  • ?

    Aufbauend auf hustbaer's Ansatz komme ich auf folgendes:

    bool foo2(unsigned u, unsigned v) { 
    return !(u & (u - 1)) 
    && !(v & (v - 1)) 
    && (u | v) != u
    && u;
}

    So macht der Clang nur noch einen Sprung 🤡

    Warum reicht es? Wenn das bitweise Oder von u und v wieder u ergibt, gilt entweder u == v oder v == 0. Es bleibt also zu überprüfen, ob u == 0 ist.

    0
  • ?

    Anmerkung: Streicht das "entweder" in meiner Erklärung, es kann auch der Fall eintreten, das u == v == 0 ist.

    0
  • B

    Um mal dem niedrigen Niveau gerecht zu werden: 🤡

    Ich habe mal ein andere Idee für die Funktion ob ein
    unsigned long exakt ein Bit gesetzt hat. Hierzu wird
    der Wert in 4 Bytes unterteilt. Und jedes Byte in die
    oberen und unteren 4 Bits. Für jede 4 Bits stellen
    wir eine boolsche Funktion auf und minimieren diese
    mittels einem KV Diagramm. Die ergebende Formel F sagt
    uns ob nur ein Bit gesetzt wurde. Um nun zu prüfen
    ob nun ein Bit in einem Byte gesetzt ist, testet man
    ob entweder in den oberen 4 Bits ein Bit gesetzt wurde,
    oder in den unteren Bits. Also F(x) xor F(x 》4).
    Über die xor Verknüpfung kann entsprechend die 4 Bytes
    getestet werden.

    Alternativ könnte man auch ein künstlich neuronales Netz
    ausprobieren.

    0
  • C
    Mod

    Man kann auch einfach blsr verwenden, wenn der Prozessor kein avx unterstützt, muss halt aufgerüstet werden.

    0
  • Mod

    camper schrieb:

    Man kann auch einfach blsr verwenden, wenn der Prozessor kein avx unterstützt, muss halt aufgerüstet werden.

    Wenn wir plattformunabhängig werden wollen, können wir gleich __builtin_popcount verwenden.

    0
  • ?

    umbenannt 👍

    0
  • ?

    Ich werf der Vollständigkeit halber noch mal eine andere Methode in die Runde:

    int foo(uint32_t x, uint32_t y) {
  return (x & -x) == x &&
         (y & -y) == y && 
         (x | y)  != x &&
         x;
}

    Dabei mache ich mir zunutze, dass -x == ~x + 1, wodurch

    x      00001000    00001010
~x     11110111    11110101
-x     11111000    11110110
x & -x 00001000    00000010

    ...mit anderen Worten: x & -x isoliert das niederwertigste Bit von x, und das ist genau dann x, wenn x höchstens ein gesetztes Bit hat.

    Es sieht mir allerdings danach aus, als käme zumindest clang mit der !(x & (x - 1))-Variante besser zurecht, weil er da leal missbrauchen kann, um mit einer Instruction x - 1 in ein zweites Register zu schubsen; für -x braucht er movl und negl. Das wird für den gcc auf x86(-64) dann auch gelten. Wie das bei solchen Low-Level-Angelegenheiten immer so ist, YMMV auf anderen Architekturen.

    0
  • Mod

    Ich habe das ganze mal gemessen.

    #include <cstdint>

bool foo1(uint32_t u, uint32_t v)
{
	return !(u & (u - 1))
	    && !(v & (v - 1))
	    && u != v
	    && u && v;
}

bool foo2(int32_t u, int32_t v)
{
	int temp1 = u - 1;
	int temp2 = v - 1;

	return temp1 >= 0 && !(temp1 & u)
          && temp2 >= 0 && !(temp2 & v)
          && u != v;
}

int foo3(uint32_t x, uint32_t y)
{
  return (x & -x) == x &&
         (y & -y) == y &&
         (x | y)  != x &&
         x;
}

bool foo4(uint32_t u, uint32_t v)
{
	asm goto (
R"(
	mov %%eax, %%ecx
	sub $1, %%ecx
	js %l2
	test %%eax, %%ecx
	jnz %l2

	mov %%ebx, %%ecx
	sub $1, %%ecx
	js %l2
	test %%ebx, %%ecx
	jnz %l2

	test %%eax, %%ebx
	jnz %l2
)"
	:: "a"(u), "b"(v)
	: "%ecx"
	: RET_FALSE );

	return true;
	RET_FALSE: return false;
}

bool foo5(uint32_t u, uint32_t v)
{
	uint8_t B = 1;
	asm (
R"(
	blsr %%eax, %%ecx
	setz %%dl
	and %%dl, %0
	setnc %%dl
	and %%dl, %0

	blsr %%ebx, %%ecx
	setz %%dl
	and %%dl, %0
	setnc %%dl
	and %%dl, %0

	test %%eax, %%ebx
	setz %%dl
	and %%dl, %0
)"
	: "+r"(B)
	: "a"(u), "b"(v)
	: "%ecx", "%dl" );

	return B;
}

bool foo6(uint32_t u, uint32_t v)
{
	uint8_t B = 1;
	asm (
R"(
	popcnt %%eax, %%ecx
	cmp $1, %%ecx
	sete %%dl
	and %%dl, %0

	popcnt %%ebx, %%ecx
	cmp $1, %%ecx
	sete %%dl
	and %%dl, %0

	test %%eax, %%ebx
	setz %%dl
	and %%dl, %0
)"
	: "+r"(B)
	: "a"(u), "b"(v)
	: "%ecx", "%dl" );

	return B;
}

#include <random>
#include <iostream>
#include <iomanip>

template< typename F >
void test( F foo, char const* name, std::size_t N = 200000000 )
{
	auto first = clock();
	std::minstd_rand rng( time(nullptr) );
	std::uniform_int_distribution<uint32_t> dis( 0, 31 );

	while(N--)
	{
		auto d1 = (1 << dis(rng)),
		     d2 = (1 << dis(rng));
		foo( d1, d2 );
	}

	auto measured = 1. * (clock() - first) / CLOCKS_PER_SEC;
	std::cout << std::setw(15) << std::right << name << ": " <<  measured << '\n';
}

int main()
{
	test( foo1, "Arcoth" );
	test( foo2, "hustbaer" );
	test( foo3, "seldon" );
	test( foo4, "Marthog" );
	test( foo5, "Arcoth's BLSR" );
	test( foo6, "Arcoth's POPCNT" );
}

    g++ -O3 -std=c++1y:
         Arcoth: 8.46297
       hustbaer: 7.63319
         seldon: 7.58602
        Marthog: 8.56772
  Arcoth's BLSR: 8.89045
Arcoth's POPCNT: 8.67961

    Da ich von effizientem Assembler äußerst wenig Ahnung habe, habe ich einfach mal hustbaers Booyahh-Rufen gefolgt und die bedingten Sprünge eliminiert.
    Das Ergebnis scheint eindeutig, aber vielleicht kann jemand ja foo5 und foo6 verbessern (bzw. umschreiben 😉 ).

    0
  • V

    Die Messung macht jetzt bei den Sprüngen, ob eine Zahl genau ein Bit gesetzt hat, aber immer in eine Richtung, wodurch die bedingten Sprünge da so billig werden wie unbedingte, weils die Sprungvorhersage immer recht hat.

    Statt bis 200000000 zu messen miss lieber 1000 mal bis 200000 und nimm den schnellsten Lauf. Du willst nämlich das Reinhacken des BS in die Messung eliminieren, was damit viel viel zuverlässiger geht als mit Duchschnittsmessung.

    0
  • C
    Mod

    Die Varianten 5 und 6 sind schon mal falsch, weil jedesmal das gleiche Register mit set verwendet wird, damit wird das Ergebnis vorheriger set-Instruktionen überschrieben. uint8_t als lokale Variable ist auch keine gute Idee, so muss der Compiler beim return noch einen Vergleich mit 0 einbauen.
    Ich biete mal noch

    bool foo(uint32_t u, uint32_t v)
{
    bool res;
    uint32_t a, b;
    asm (
R"(
    popcnt %[u], %[u_cnt]
    popcnt %[v], %[v_cnt]
    dec %[u_cnt]
    dec %[v_cnt]
    or %[u_cnt], %[v_cnt]
    setz %[res]
    xor %[u], %[v]
    cmovz %[v], %k[res]
)"
    : [res]"=&r,r,r"(res)
    : [u]"r,r,r"(u), [v]"r,r,r"(v), [u_cnt]"r,0,r"(a), [v_cnt]"r,r,0"(b) );

    return res;
}

    an. Ist aber wahrscheinlich auch nicht schneller.

    0
  • Mod

    Die Varianten 5 und 6 sind schon mal falsch, weil jedesmal das gleiche Register mit set verwendet wird, damit wird das Ergebnis vorheriger set-Instruktionen überschrieben.

    😕 Kann es sein, dass du was falsch verstanden hast? Oder habe ich irgendwo einen Denkfehler?

    uint8_t als lokale Variable ist auch keine gute Idee, so muss der Compiler beim return noch einen Vergleich mit 0 einbauen.

    Ich dachte halt nur, bei einem bool ist es nicht definiert, wie true dargestellt wird.
    Und ich wende ja and drauf an.

    Statt bis 200000000 zu messen miss lieber 1000 mal bis 200000 und nimm den schnellsten Lauf. Du willst nämlich das Reinhacken des BS in die Messung eliminieren, was damit viel viel zuverlässiger geht als mit Duchschnittsmessung.

    Gottogott! Jetzt bekomme ich total verrückte Ergebnisse!

    Ich habe die Testfunktion zu

    template< typename F >
void test( F foo, char const* name, std::size_t N = 50000, std::size_t times = 10000 )
{
	std::minstd_rand rng( time(nullptr) );
	std::uniform_int_distribution<uint32_t> dis( 0, 31 );

	std::vector<clock_t> vec;
	vec.reserve(times);

	for (auto t = times; t--;)
	{
		auto first = std::chrono::high_resolution_clock::now();
		for (auto n = N; n--;)
		{
			auto d1 = (1 << dis(rng)),
			     d2 = (1 << dis(rng));
			foo( d1, d2 );
		}
		vec.push_back( (std::chrono::high_resolution_clock::now() - first).count() );
	}

	std::cout << std::setw(16) << std::right << name << ": " << *std::min_element(std::begin(vec), std::end(vec)) << '\n';
}

    umgeschrieben.

    Jetzt erhalte ich (mit campers Version) sowas

    g++ -O3
          Arcoth: 2007824
        hustbaer: 2043283
          seldon: 2022938
         Marthog: 1971211
   Arcoth's BLSR: 2066844
 Arcoth's POPCNT: 2042884
campers's POPCNT: 1975276

    Das heißt: Marthogs Version ist Top, gefolgt von camper und dann meiner ersten. Was allerdings total verdreht ist.

    0
Anmelden zum Antworten