Zählen, umgekehrt Bitmuster

https://stackoverflow.com/questions/259212

06-07-2019
|

Frage

Ich versuche, einen Algorithmus zu finden, von 0 bis 2 ^{zählen n} -1 aber ihre Bitmuster umgekehrt. Ich kümmere mich um nur n LSB ein Wort. Wie Sie vielleicht schon erraten kann ich nicht.

Für n = 3:

000 -> 0
100 -> 4
010 -> 2
110 -> 6
001 -> 1
101 -> 5
011 -> 3
111 -> 7

Sie erhalten die Idee.

Antworten in Pseudo-Code ist groß. Codefragmente in jeder Sprache sind willkommen, Antworten ohne Bit-Operationen bevorzugt werden.

Bitte poste nicht nur ein Fragment, ohne auch nur eine kurze Erklärung oder ein Zeiger auf eine Quelle.

Edit: Ich habe vergessen, in der, ich habe bereits eine naive Implementierung, die nur ein Zählvariable Bit-umkehrt. In gewissem Sinne ist diese Methode nicht wirklich zählen.

Lösung

Das ist, glaube ich am einfachsten mit Bit-Operationen, auch wenn Sie sagte, dies nicht bevorzugt wurde

32 Bit ints Unter der Annahme, hier ist ein raffiniertes Stück Code, das rückgängig machen kann alle des Bits, ohne es in 32 Schritten zu tun:

 unsigned int i;
 i = (i & 0x55555555) <<  1 | (i & 0xaaaaaaaa) >>  1;
 i = (i & 0x33333333) <<  2 | (i & 0xcccccccc) >>  2;
 i = (i & 0x0f0f0f0f) <<  4 | (i & 0xf0f0f0f0) >>  4;
 i = (i & 0x00ff00ff) <<  8 | (i & 0xff00ff00) >>  8;
 i = (i & 0x0000ffff) << 16 | (i & 0xffff0000) >> 16;
 i >>= (32 - n);

Im Wesentlichen das bedeutet eine verschachtelte shuffle aller Bits. Jedes Mal, um die Hälfte der Bits im Wert wird mit der anderen Hälfte vertauscht.

Die letzte Zeile ist notwendig, die Bits, so dass ist „n“ ist das bedeutendste Bit neu auszurichten.

Kürzere Versionen dieses möglich sind, wenn "n"

Andere Tipps

Bei jedem Schritt findet die linke 0 Ziffer des Wertes. Stellen Sie ihn, und deaktivieren Sie alle Ziffern links davon. Wenn Sie nicht über eine 0 Ziffer finden, dann haben Sie überschwemmt. Return 0, oder stoppen, oder abstürzen, oder was auch immer Sie wollen

Dies ist, was auf einem normalen binären Schritt geschieht (und damit meine ich es die Wirkung ist, nicht, wie es in Hardware implementiert ist), aber wir tun es auf der Stelle des rechts nach links.

Ob Sie dies in Bit-ops, Strings zu tun, oder was auch immer, ist Ihnen überlassen. Wenn Sie es in bitops tun, dann ein clz (oder rufen Sie zu einem äquivalenten hibit-Style-Funktion) auf ~value könnte die effizienteste Art und Weise sein: __builtin_clz wo verfügbar. Aber das ist eine Implementierung Detail.

Diese Lösung wurde ursprünglich in binären und umgewandelt zu herkömmlicher Mathematik als Anforderer angegeben.

Es würde mehr Sinn als binäres machen, zumindest die mit 2 multiplizieren und dividieren durch 2 sein sollte << 1 und >> 1 für die Geschwindigkeit, die Additionen und Subtraktionen wahrscheinlich keine Rolle spielt die eine oder die andere.

Wenn Sie in der Maske übergeben statt nBits, und verwenden Sie bitshifting statt Multiplikation oder Division, und die Endrekursion zu einer Schleife ändern, wird dies wahrscheinlich die performante Lösung, die Sie da jeder anderen finden nennen wird es nichts sondern ein einziger Zusatz, wäre es nur so langsam wie Alnitak Lösung einmal all 4, vielleicht sogar acht Anrufe.

int incrementBizarre(int initial, int nBits)
    // in the 3 bit example, this should create 100
    mask=2^(nBits-1)
    // This should only return true if the first (least significant) bit is not set
    // if initial is 011 and mask is 100
    //                3               4, bit is not set
    if(initial < mask)
        // If it was not, just set it and bail.
        return initial+ mask // 011 (3) + 100 (4) = 111 (7)
    else
        // it was set, are we at the most significant bit yet?
        // mask 100 (4) / 2 = 010 (2), 001/2 = 0 indicating overflow
        if(mask / 2) > 0
            // No, we were't, so unset it (initial-mask) and increment the next bit
            return incrementBizarre(initial - mask, mask/2)
        else
            // Whoops we were at the most significant bit.  Error condition
            throw new OverflowedMyBitsException()

Wow, das stellte sich heraus, irgendwie cool. Ich habe nicht vorstellen in der Rekursion, bis zur letzten Sekunde da.

Es fühlt sich falsch - wie es einige Operationen, die nicht funktionieren sollte, aber sie tun wegen der Natur dessen, was Sie tun (wie es sich anfühlt, wie Sie in Schwierigkeiten geraten sollten, wenn Sie auf ein bisschen und einige Bits arbeiten auf der linken Seite nicht Null, aber es stellt sich heraus, Sie nicht immer auf ein wenig in Betrieb sein kann, wenn nicht alle Bits auf der linken Seite gleich Null sind -., welche eine sehr seltsame Zustand ist, aber wahr

Beispiel für Fluss zu erhalten 110-001 (rückwärts rückwärts 3 bis 4):

mask 100 (4), initial 110 (6); initial < mask=false; initial-mask = 010 (2), now try on the next bit
mask 010 (2), initial 010 (2); initial < mask=false; initial-mask = 000 (0), now inc the next bit
mask 001 (1), initial 000 (0); initial < mask=true;  initial + mask = 001--correct answer

Hier ist eine Lösung aus meiner Frage , die ohne Looping den nächsten Bit-Index umgekehrt berechnet. Es stützt sich stark auf Bit-Operationen, though.

Die Schlüsselidee ist, dass eine Reihe einfach Zunehmen eine Folge von Bits mit geringster Wertigkeit Flips, zum Beispiel von nnnn0111 nnnn1000. Also, um den nächsten Bit-Index umgekehrt zu berechnen, haben Sie eine Folge von höchstwertigen Bits kippen. Wenn Ihre Zielplattform eine CTZ ( „count nachgestellte Nullen“) Anweisung hat, kann dies effizient durchgeführt werden.

Beispiel in C GCC __builtin_ctz mit:

void iter_reversed(unsigned bits) {
    unsigned n = 1 << bits;

    for (unsigned i = 0, j = 0; i < n; i++) {
        printf("%x\n", j);

        // Compute a mask of LSBs.
        unsigned mask = i ^ (i + 1);
        // Length of the mask.
        unsigned len = __builtin_ctz(~mask);
        // Align the mask to MSB of n.
        mask <<= bits - len;
        // XOR with mask.
        j ^= mask;
    }
}

Ohne CTZ Anweisung, können Sie auch Integer-Division verwenden:

void iter_reversed(unsigned bits) {
    unsigned n = 1 << bits;

    for (unsigned i = 0, j = 0; i < n; i++) {
        printf("%x\n", j);

        // Find least significant zero bit.
        unsigned bit = ~i & (i + 1);
        // Using division to bit-reverse a single bit.
        unsigned rev = (n / 2) / bit;
        // XOR with mask.
        j ^= (n - 1) & ~(rev - 1);
    }
}

void reverse(int nMaxVal, int nBits)
{
   int thisVal, bit, out;

   // Calculate for each value from 0 to nMaxVal.
   for (thisVal=0; thisVal<=nMaxVal; ++thisVal)
   {
      out = 0;

      // Shift each bit from thisVal into out, in reverse order.
      for (bit=0; bit<nBits; ++bit)
         out = (out<<1) + ((thisVal>>bit) & 1)

   }
   printf("%d -> %d\n", thisVal, out);
}

Vielleicht von 0 bis N erhöhen (die "üblichen" Weg ") und tun ReverseBitOrder () für jede Iteration. Sie können mehrere Implementierungen finden hier (Ich mag die LUT eine der am besten). Sollte wirklich schnell.

Hier ist eine Antwort in Perl. Sie sagen nicht, was nach dem alle diejenigen Muster kommt, so kehre ich Null gerade. Ich nahm die bitweise Operationen, so dass es leicht sein, sollte in einer anderen Sprache zu übersetzen.

sub reverse_increment {
  my($n, $bits) = @_;

  my $carry = 2**$bits;
  while($carry > 1) {
    $carry /= 2;
    if($carry > $n) {
      return $carry + $n;
    } else {
      $n -= $carry;
    }
  }
  return 0;
}

Hier ist eine Lösung, die nicht versucht, tatsächlich jede zusätzlich zu tun, sondern nutzt die Ein- / Aus-Muster des seqence (die meisten sig Bit wechselt jedes Mal, nächst sig Bit wechselt jede andere Zeit, etc.), stellen n als gewünscht:

#define FLIP(x, i) do { (x) ^= (1 << (i)); } while(0)

int main() {
    int n   = 3;
    int max = (1 << n);
    int x   = 0;

    for(int i = 1; i <= max; ++i) {
        std::cout << x << std::endl;
        /* if n == 3, this next part is functionally equivalent to this:
         *
         * if((i % 1) == 0) FLIP(x, n - 1);
         * if((i % 2) == 0) FLIP(x, n - 2);
         * if((i % 4) == 0) FLIP(x, n - 3);
         */
        for(int j = 0; j < n; ++j) {
            if((i % (1 << j)) == 0) FLIP(x, n - (j + 1));
        }                       
    }
}

Wie etwa 1 bis höchstwertigen Bit hinzufügen, dann auf den nächsten (kleineren) Bit tragen, falls erforderlich. Man könnte dies durch den Einsatz auf Bytes beschleunigen:

Precompute eine Lookup-Tabelle in zum Zählen Bit-Rückwärts-0-256 (00000000 -> 10000000, 10000000 -> 01000000, ..., 11111111 -> 00000000).
Stellen Sie alle Bytes in Ihrem Multi-Byte-Zahl auf Null.
Erhöhen Sie die höchstwertigen Bytes auf die Nachschlag-Tabelle. Wenn das Byte 0 ist, erhöht das nächste Byte auf die Nachschlag-Tabelle. Wenn das Byte 0 ist, erhöht das nächste Byte ...
Gehen Sie zu Schritt 3.

Mit n als Potenz von 2 und x die Variable, die Sie Schritt wollen:

(defun inv-step (x n)       ; the following is a function declaration
  "returns a bit-inverse step of x, bounded by 2^n"    ; documentation
  (do ((i (expt 2 (- n 1))  ; loop, init of i
          (/ i 2))          ; stepping of i
       (s x))               ; init of s as x
      ((not (integerp i))   ; breaking condition
       s)                   ; returned value if all bits are 1 (is 0 then)
    (if (< s i)                         ; the loop's body: if s < i
        (return-from inv-step (+ s i))  ;     -> add i to s and return the result
        (decf s i))))                   ;     else: reduce s by i

, bemerkte ich es gründlich, da Sie nicht mit dieser Syntax vertraut sind.

Bearbeiten : hier ist der Schwanz rekursive Version. Es scheint ein wenig schneller zu sein, vorausgesetzt, dass Sie einen Compiler mit Endrekursion Optimierung haben.

(defun inv-step (x n)
  (let ((i (expt 2 (- n 1))))
    (cond ((= n 1)
           (if (zerop x) 1 0))         ; this is really (logxor x 1)                                                 
          ((< x i)
           (+ x i))
          (t
           (inv-step (- x i) (- n 1))))))

Wenn Sie 0 to 2^n-1 aber ihre Bitmuster umgekehrt umgekehrt, Sie so ziemlich die gesamte 0-2^n-1 Sequenz abdecken

Sum = 2^n * (2^n+1)/2

O(1) Betrieb. Keine Notwendigkeit, etwas zu tun, Umkehrungen

Edit: Natürlich ursprüngliche Plakat Frage nach war durch Erhöhung zu tun (umgekehrt) ein, die als das Hinzufügen von zwei zufälligen Werten Dinge einfacher macht. So nwellnhof beantworten den Algorithmus enthält bereits.

Fassen zwei Bit-Umkehr-Werte

Hier ist eine Lösung in PHP:

function RevSum ($a,$b) {

    // loop until our adder, $b, is zero
    while ($b) {

        // get carry (aka overflow) bit for every bit-location by AND-operation
        // 0 + 0 --> 00   no overflow, carry is "0"
        // 0 + 1 --> 01   no overflow, carry is "0"
        // 1 + 0 --> 01   no overflow, carry is "0"
        // 1 + 1 --> 10   overflow! carry is "1"

        $c = $a & $b;


        // do 1-bit addition for every bit location at once by XOR-operation
        // 0 + 0 --> 00   result = 0
        // 0 + 1 --> 01   result = 1
        // 1 + 0 --> 01   result = 1
        // 1 + 1 --> 10   result = 0 (ignored that "1", already taken care above)

        $a ^= $b;


        // now: shift carry bits to the next bit-locations to be added to $a in
        // next iteration.
        // PHP_INT_MAX here is used to ensure that the most-significant bit of the
        // $b will be cleared after shifting. see link in the side note below.

        $b = ($c >> 1) & PHP_INT_MAX;

    }

    return $a;
}

Side Hinweis: Siehe diese Frage über negative Werte verschieben.

Und wie für den Test; Start von Null und Inkrementwert von 8-Bit umgekehrt ein (10000000):

$value = 0;
$add = 0x80;    // 10000000 <-- "one" as bit reversed

for ($count = 20; $count--;) {      // loop 20 times
    printf("%08b\n", $value);       // show value as 8-bit binary
    $value = RevSum($value, $add);  // do addition
}

... AUSGABE:

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow