Zahlen ohne Verwendung von logischen Operatoren sortieren?!

Ben04

Double post sorry

DEvent

wie soll man bitte zahlen sortieren ohne sie vergleichen zu dürfen

SirLant

Kann man Zahlen nicht mit den Bit-Operatoren vergleichen? Muss damit doch gehen.

Ben04

Klar geht das. Man durchläuft alle Bits von links nach rechts. Solange die Bits gleich sind weiter laufen, sind sie verschieden dann ist die Zahl wo das Bit gesetzt ist die grössere. Beispiel:

0101000
0100100

Die ersten 3 Bits sind gleich. Das 4te Bit is verschieden. Bei der ersten Zahl ist es gesetzt also ist das die grössere.

Killing me softly

Ben04 schrieb:

Klar geht das. Man durchläuft alle Bits von links nach rechts. Solange die Bits gleich sind weiter laufen...

Und der Test auf Gleichheit ist kein logischer Ausdruck?

Windalf

@Killing me softly

ja seh ich auch so... die ganze aufgabe scheint mir ziemlicher schwachsinn zu sein... vielleicht sollte der Fragensteller mal den genauen aufgabentext posten...

Ben04

Killing me softly schrieb:

Ben04 schrieb:

Klar geht das. Man durchläuft alle Bits von links nach rechts. Solange die Bits gleich sind weiter laufen...

Und der Test auf Gleichheit ist kein logischer Ausdruck?

Per bitwise operator. Oder macht sich das Leben leicht und macht es so wie ich es bereits gesagt habe.

bool IsSmallerOrEqual(unsigned a, unsigned b)
{
  while(a)
  {
    if(b)
    {
      --a;
      --b;
    }
    else
      return false;
  }
  return true;
}

Alle anderen Operatoren nachzubasteln is trivial.

Aber wie bereits gesagt glaub ich kann, dass der Aufgaben steller das gemeint hat da es 100% sinnfrei ist.

Walli

@ben04: sind auch logische vergleiche drin, deswegen scheidet das auch aus.

wenn ihr glück habt kommt volkard vorbei und sagt euch lässig wie das geht. wenn der es auch nicht weiß, dann geht es ziemlich sicher nicht...

mein tip ist: es geht nicht

camper

void Sort(unsigned& a, unsigned& b)
{
    unsigned temp = ( ~ ( ( a + 1 ) / ( b + 1 ) ) ) / ( ~0 ); // a < b ? 1 : 0
    unsigned smaller = a + ( b - a ) * temp;
    b = a + b - smaller;
    a = smaller;
}

setzt voraus, dass b != max_int ( bzw. != 0, wenn man das +1 weglässt )

Sunday

hier ne funktion die prüft ob a > b bzw a < b ist...

inline int Maximum(const int a, const int b)
{
  return (a - (((a - b) >> 31) & (a - b))); 
}

inline int Minimum(const int a, const int b) 
{
  return (a + (((b - a) >> 31) & (b - a))); 
}

das ganze setzt voraus, dass int 32Bit gross ist.

nebenbei bemerkt ist dieser vergleich sogar schneller als das normale a > b. allerdings fällt das bei heutigen rechnern erst bei ca. 100.000.000 vergleichen ins gewicht.

Walli

@Sunday: Das Problem an der ganzen Sache ist, dass man das Ergebnis auswerten muss . Dazu braucht man aber einen Vergleich.

@camper: Implementier mal damit einen Bubblesort ohne Vergleiche. Das scheitert spätestens an der Schleife . EDIT: Sorry, war ja nur von 3 Zahlen die Rede. Dachte die ganze Zeit, dass es sich um n Zahlen handelt .

camper

das ist nicht immer richtig richtig: wenn z.b. a<0 und b>0 und a-b zum überlauf führen würde, dann würde trotzdem a als maximum zurückgegeben werden, wenn der mögliche wertebereich kleiner ist, kann man es nat. so machen - auf assembler ebene geht es im übrigen einfacher (ab pentium pro - maximum):

inline int Maximum(const int a, const int b)
{
    __asm
    {
        mov    eax, a
        cmp    eax, b
        cmovl  eax, b
}

da es sich um keinen sprung handelt, muss im falle falscher vorhersage nicht die ganze pipeline gelöscht werden, lediglich alle ergebnisse die auf dem cmov beruhen müssen verworfen werden; insofern ist diese variante sehr schnell, insbes. wenn das ergebnis nicht gleich im nächsten befehl benötigt wird.
im übrigen bin ich nicht sicher ob das überhaupt portabel ist: nähmlich das shift auf jeder maschine arihmetisch und nicht logisch arbeitet (bei logisch könnte man & mit * ersetzen). jemand mit ahnung vom standard kann das sicher besser beurteilen.

@MaSTaH: wieso ich? war doch nicht meine idee
klar, beim bubblesort braucht man ja irgendwie eine abbruchbedingung, insofern ist dann wenigstens einmal ein logischer ausdruck notwendig (oder man nimmt immer die maximale anzahl von durchläufen: bei n elementen (n-1)(n-2)/2 lol)