Wie Finden Sie Die Führende Null In einer Reihe mit C

beispielsweise,wenn ich habe die Nummer 64,und dann seine binäre Darstellung wäre 0000 0000 0000 0000 0000 0000 0100 0000 also führende null ist 25.
denken Sie daran, ich habe um diese zu berechnen in O(1) Zeit.

bitte sagen Sie mir den richtigen Weg, das zu tun.auch wenn Ihre Komplexität ist >O(1) bitte posten Sie Ihre Antwort. danke

O(1) bedeutet, dass Sie variieren das problem, die Zeit zu berechnen die Lösung konstant bleibt (in etwa). Das macht keinen Sinn mit einer festen Größe problem wie deines.
Ist dies eine Hausaufgaben-Frage? Was haben Sie bereits versucht?
Ich bin nur jetzt zu bemerken, das [funktionale-Programmierung] tag-ist dies wirklich funktionale Programmierung oder benötigen Sie nur eine Funktion, die dies tut?
Sie können beliebig viele 0EN vor jede Zahl in einer beliebigen Basis, ohne es zu verändern. Sind Sie auf der Annahme einer 32-bit-integer-Typ? Wenn dem so ist, dann sagen Sie es. Bitte beachten Sie, dass C ist nicht verpflichtet, einen Typ mit genau 32 bits bei allen: die Größen der char/short/int/long angegeben sind nur als minima und relativ zu einander.
mit O(1) ist richtig hier, wenn Sie erwägen, die Größe des Problems, die Anzahl der führenden Nullen in der Binärdarstellung. Viele algorithmen dieser Komplexität abhängig von der Anzahl der führenden Nullen in der tatsächlichen Anzahl.

InformationsquelleAutor user609306 | 2011-06-04

Ich fand gerade dieses problem an der Spitze der Suchergebnisse, und dieser code:

int pop(unsigned x) {
    unsigned n;
    n = (x >> 1) & 033333333333;
    x = x - n;
    n = (n >> 1) & 033333333333;
    x = x - n;
    x = (x + (x >> 3)) & 030707070707;
    return x % 63;
}

int nlz(unsigned x) {
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >>16);
    return pop(~x);
}

wo pop zählt 1-bits ist ein Vielfaches schneller als die erste (von Ihnen positiv bewertet werden) zu beantworten.

Konnte ich nicht feststellen, die Frage war über-64-bit-zahlen, also hier:

int nlz(unsigned long x) {
    unsigned long y;
    long n, c;
    n = 64;
    c = 32;
    do {
        y = x >> c;
        if (y != 0) {
            n = n - c;
            x = y;
        }
        c = c >> 1;
    } while (c != 0);
    return n - x;
}

ist eine 64-bit-Algorithmus, mehrmals wieder schneller als die oben genannten.

InformationsquelleAutor

1

Rechte shift - ist dein Freund.
```
    int input = 64;
    int sample = ( input < 0 ) ? 0 : input;
    int leadingZeros = ( input < 0 ) ? 0 : 32;

    while(sample) {
        sample >>= 1;
        --leadingZeros;
    }
    printf("Input = %d, leading zeroes = %d\n",input, leadingZeros);
```
- danke john ....ich wollte die gleiche Sache.. aber seine big O ist O(log n) base 2. wenn Sie 64, dann müssen Sie verschieben von bits, die vom log 64-mal 6-mal eine andere Zahl n, für die while-Schleife ausgeführt würde, log n mal
- als das größte n ist hier 32 (oder 64 für 64-bit-Nummern) sollten Sie sehr vorsichtig sein mit ceil. Konstanten Zeiten hinter Aufruf ceil kann größer als die Zeit für die Ausführung der 64 loops oder weniger.
- Vermeiden Sie die Zweige in code wie diesem, es wird nicht benötigt!
InformationsquelleAutor Prince John Wesley

Sehen hier für die 32-bit-version und andere große bit-twiddling hacks.

//this is like doing a sign-extension
//if original value was   0x00.01yyy..y
//then afterwards will be 0x00.01111111
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
x |= (x >> 32);

und nach, die Sie gerade brauchen, um zurückzukehren 64 - numOnes(x).
Ein einfacher Weg, dies zu tun, ist numOnes32(x) + numOnes32(x >> 32), wo numOnes32 ist definiert als:

int numOnes32(unsigned int x) {
    x -= ((x >> 1) & 0x55555555);
    x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
    x = (((x >> 4) + x) & 0x0f0f0f0f);
    x += (x >> 8);
    x += (x >> 16);
    return(x & 0x0000003f);
}

Ich habe nicht versucht, aus diesem code, aber das sollte numOnes64 direkt (in weniger Zeit):

int numOnes64(unsigned long int x) {
     x = ((x >> 1) & 0x5555555555555555L) + (x & 0x5555555555555555L);
     x = ((x >> 2) & 0x3333333333333333L) + (x & 0x3333333333333333L);
     //collapse:
     unsigned int v = (unsigned int) ((x >>> 32) + x);
     v = ((v >> 4) + v) & 0x0f0f0f0f) + (v & 0x0f0f0f0f);
     v = ((v >> 8) & 0x00ff00ff) + (v & 0x00ff00ff);
     return ((v >> 16) & 0x0000ffff) + (v & 0x0000ffff);
}

InformationsquelleAutor MotiN

Ich würde gehen mit:

unsigned long clz(unsigned long n) {
    unsigned long result = 0;
    unsigned long mask = 0;
    mask = ~mask;
    auto size = sizeof(n) * 8;
    auto shift = size / 2;
    mask >>= shift;
    while (shift >= 1) {
        if (n <= mask) {
            result += shift;
            n <<= shift;
        }
        shift /= 2;
        mask <<= shift;
    }
    return result;
}

InformationsquelleAutor Tomasz Gawel

-1

Weil der Logarithmus zur Basis 2 etwa stellt die Anzahl der bits, die erforderlich ist, um eine Zahl darstellen, könnte es sinnvoll sein in die Antwort:
```
irb(main):012:0> 31 - (Math::log(64) / Math::log(2)).floor()
=> 25
irb(main):013:0> 31 - (Math::log(65) / Math::log(2)).floor()
=> 25
irb(main):014:0> 31 - (Math::log(127) / Math::log(2)).floor()
=> 25
irb(main):015:0> 31 - (Math::log(128) / Math::log(2)).floor()
=> 24
```
Natürlich ein Nachteil bei der Verwendung log(3) ist, dass es eine floating-point routine; es gibt wahrscheinlich einige höchst clever bit-tricks zu finden, die Anzahl der führenden null-bits in Integer-zahlen, aber ich kann mir nicht vorstellen, das man aus der Spitze von meinem Kopf...

InformationsquelleAutor sarnold
-1

Verwendung von floating-points ist nicht die richtige Antwort....

Hier ist ein algo, den ich verwenden, um die Anzahl der TRAILING-0... ändern Sie es für Führende...
Dieser Algorithmus ist in O(1) - (wird immer ausgeführt wird ~ die gleiche Zeit oder die gleiche Zeit auf einer CPU).
```
int clz(unsigned int i)
{
  int zeros;
  if ((i&0xffff)==0) zeros= 16, i>>= 16; else zeroes= 0;
  if ((i&0xff)==0) zeros+= 8, i>>= 8;
  if ((i&0xf)==0) zeros+= 4, i>>= 4;
  if ((i&0x3)==0) zeros+= 2, i>>= 2;
  if ((i&0x1)==0) zeros+= 1, i>>= 1;
  return zeroes+i;
}
```
- Verzweigungen im code für diese Art der Sache nicht sinnvoll. Unter Verwendung von bit-twiddling Techniken, Sie können dies tun, ohne abzweigungen, siehe z.B. aggregate.org/MAGIC/#Leading Null Zählen
- Eigentlich, diese Zweige sind sinnvoll auf ARM-chips geben, die bedingte Ausführung, und wo jede Zeile code wird ersetzt durch 3 Anleitungen (2 davon bedingt) von der Art: ANDS R4, R0, #0xff addeq R1, R1, #8, moveq R0, R0 shl 8. Dann die gesamte Funktion wird in 3*5 Anleitung mit präziser Ausführung. Bit twideling wird wahrscheinlich nicht besser sein. Natürlich, der ARM-chips haben CLZ Anweisungen, die Sie verwenden können!
InformationsquelleAutor user3256556

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.