Bit-Umkehr einer ganzen Zahl zu ignorieren integer Größe und endianness

Gegeben eine Ganzzahl typedef:

typedef unsigned int TYPE;

oder

typedef unsigned long TYPE;

Ich habe den folgenden code zum umkehren der bits eines integer:

TYPE max_bit= (TYPE)-1;

void reverse_int_setup()
{
    TYPE bits= (TYPE)max_bit;

    while (bits <<= 1)
        max_bit= bits;
}

TYPE reverse_int(TYPE arg)
{
    TYPE    bit_setter= 1, bit_tester= max_bit, result= 0;

    for (result= 0; bit_tester; bit_tester>>= 1, bit_setter<<= 1)
        if (arg & bit_tester)
            result|= bit_setter;
    return result;
}

Muss man nur noch zuerst ausführen reverse_int_setup () - speichert eine ganze Zahl mit dem höchsten bit eingeschaltet, dann wird jeder Aufruf zum reverse_int(arg) gibt arg mit seine bits invertiert (werden als Schlüssel verwendet, um einen binären Baum, ergriffen von einer zunehmenden Zähler, aber das ist mehr oder weniger irrelevant).

Gibt es eine Plattform-unabhängige Art und Weise zu haben, in compile-time den richtigen Wert für max_int nach dem Aufruf reverse_int_setup(); Ansonsten gibt es einen Algorithmus, den Sie betrachten besser/schlanker als die, die ich habe für reverse_int()?

Dank.

InformationsquelleAutor tzot | 2008-09-15

bit-manipulation c integer

#include<stdio.h>
#include<limits.h>

#define TYPE_BITS sizeof(TYPE)*CHAR_BIT

typedef unsigned long TYPE;

TYPE reverser(TYPE n)
{
    TYPE nrev = 0, i, bit1, bit2;
    int count;

    for(i = 0; i < TYPE_BITS; i += 2)
    {
        /*In each iteration, we  swap one bit on the 'right half' 
        of the number with another on the left half*/

        count = TYPE_BITS - i - 1;  /*this is used to find how many positions 
                                    to the left (and right) we gotta move 
                                    the bits in this iteration*/

        bit1 = n & (1<<(i/2)); /*Extract 'right half' bit*/
        bit1 <<= count;         /*Shift it to where it belongs*/

        bit2 = n & 1<<((i/2) + count);  /*Find the 'left half' bit*/
        bit2 >>= count;         /*Place that bit in bit1's original position*/

        nrev |= bit1;   /*Now add the bits to the reversal result*/
        nrev |= bit2;
    }
    return nrev;
}

int main()
{
    TYPE n = 6;

    printf("%lu", reverser(n));
    return 0;
}

Dieser Zeit habe ich die "Anzahl der bits, die' Idee von der TK, sondern machte es ein wenig mehr tragbar, indem Sie nicht davon ausgehen, dass ein byte enthält 8 bits und stattdessen über das macro CHAR_BIT. Der code effizienter ist nun (mit der inneren for-Schleife entfernt). Ich hoffe, der code ist auch etwas weniger kryptisch aus dieser Zeit. 🙂

Die Notwendigkeit für die Verwendung von count ist, dass die Anzahl der Positionen, die wir haben, um shift ein bit ändert sich bei jeder iteration - wir verschieben das bit ganz rechts um 31 Positionen (davon 32 bit-Zahl), die zweite am weitesten rechts liegenden bit um 29 Positionen und so weiter. Daher zählen müssen, verringern sich mit jeder iteration, wie ich erhöht.

Hoffe, dass bisschen info beweist hilfreich, den code zu verstehen...

Vielen Dank; ich habe keine Probleme nach der Logik des code, aber dieser code konnte von anderen gesehen werden, so Neige ich dazu, zu vermeiden, kryptischen code, vor allem, nachdem ich fiel in der Liebe mit Python, aber das ist eine andere Geschichte.
Vielen Dank für joggen meine Erinnerung wieder. CHAR_BIT!

InformationsquelleAutor sundar

Folgende Programm dient zu zeigen, ein schlanker Algorithmus die Umkehrung der bits, die kann leicht erweitert werden, um zu behandeln 64bit zahlen.

#include <stdio.h>
#include <stdint.h>
int main(int argc, char**argv)
{
        int32_t x;
        if ( argc != 2 ) 
        {
                printf("Usage: %s hexadecimal\n", argv[0]);
                return 1;
        }

        sscanf(argv[1],"%x", &x);
        /* swap every neigbouring bit */
        x = (x&0xAAAAAAAA)>>1 | (x&0x55555555)<<1;
        /* swap every 2 neighbouring bits */
        x = (x&0xCCCCCCCC)>>2 | (x&0x33333333)<<2;
        /* swap every 4 neighbouring bits */
        x = (x&0xF0F0F0F0)>>4 | (x&0x0F0F0F0F)<<4;
        /* swap every 8 neighbouring bits */
        x = (x&0xFF00FF00)>>8 | (x&0x00FF00FF)<<8;
        /* and so forth, for say, 32 bit int */
        x = (x&0xFFFF0000)>>16 | (x&0x0000FFFF)<<16;
        printf("0x%x\n",x);
        return 0;
}

Dieser code sollte keine Fehler enthalten, und wurde getestet mit 0x12345678 zu produzieren 0x1e6a2c48 welche Antwort richtig ist.

Interessant, aber hat ein Problem: es ist code, der variiert je nach TYP, Größe.

InformationsquelleAutor freespace

3
```
typedef unsigned long TYPE;

TYPE reverser(TYPE n)
{
    TYPE k = 1, nrev = 0, i, nrevbit1, nrevbit2;
    int count;

    for(i = 0; !i || (1 << i && (1 << i) != 1); i+=2)
    {
        /*In each iteration, we  swap one bit 
            on the 'right half' of the number with another 
            on the left half*/

        k = 1<<i; /*this is used to find how many positions 
                    to the left (or right, for the other bit) 
                    we gotta move the bits in this iteration*/

        count = 0;

        while(k << 1 && k << 1 != 1)
        {
            k <<= 1;
            count++;
        }

        nrevbit1 = n & (1<<(i/2));
        nrevbit1 <<= count;

        nrevbit2 = n & 1<<((i/2) + count);
        nrevbit2 >>= count;

        nrev |= nrevbit1;
        nrev |= nrevbit2;
    }
    return nrev;
}
```
Dies funktioniert gut in gcc unter Windows, aber ich bin mir nicht sicher, ob es völlig Plattform-unabhängig. Ein paar Orte von Interesse sind:
- die Bedingung in der for-Schleife - es wird davon ausgegangen, dass wenn Sie mit der linken shift 1 über das bit ganz Links, bekommen Sie entweder eine 0 mit der 1 'Herausfallen' (was ich erwarten würde, und was die guten alten Turbo-C gibt iirc), oder die 1. Kreise um und erhalten Sie eine 1 (was zu sein scheint der gcc-Verhalten).
- die Bedingung in der inneren while-Schleife: siehe oben. Aber es ist schon eine seltsame Sache passiert hier: in diesem Fall gcc scheint lassen Sie die 1 fallen und nicht Kreis rund!
Den code könnte sich als kryptisch: wenn Sie interessiert sind und benötigen eine Erklärung, bitte zögern Sie nicht zu Fragen - ich werde es bis irgendwo.
- Dies ist sicher nicht der trick, die sowohl für 32-bit und 64-bit, obwohl es scheint in der Tat kryptisch. Ich werde warten, für den Fall, dass jemand produziert etwas weniger dunkel vor der Beurteilung auf beste Antwort. Danke!
InformationsquelleAutor sundar

@ΤΖΩΤΖΙΟΥ

In der Antwort zu ΤΖΩΤΖΙΟΥ 's Kommentare, ich präsentiere modifizierte version von oben, das hängt davon ab, eine Obere Grenze für die bit-Breite.

#include <stdio.h>
#include <stdint.h>
typedef int32_t TYPE;
TYPE reverse(TYPE x, int bits)
{
    TYPE m=~0;
    switch(bits)
    {
        case 64:
            x = (x&0xFFFFFFFF00000000&m)>>16 | (x&0x00000000FFFFFFFF&m)<<16;
        case 32:
            x = (x&0xFFFF0000FFFF0000&m)>>16 | (x&0x0000FFFF0000FFFF&m)<<16;
        case 16:
            x = (x&0xFF00FF00FF00FF00&m)>>8 | (x&0x00FF00FF00FF00FF&m)<<8;
        case 8:
            x = (x&0xF0F0F0F0F0F0F0F0&m)>>4 | (x&0x0F0F0F0F0F0F0F0F&m)<<4;
            x = (x&0xCCCCCCCCCCCCCCCC&m)>>2 | (x&0x3333333333333333&m)<<2;
            x = (x&0xAAAAAAAAAAAAAAAA&m)>>1 | (x&0x5555555555555555&m)<<1;
    }
    return x;
}

int main(int argc, char**argv)
{
    TYPE x;
    TYPE b = (TYPE)-1;
    int bits;
    if ( argc != 2 ) 
    {
        printf("Usage: %s hexadecimal\n", argv[0]);
        return 1;
    }
    for(bits=1;b;b<<=1,bits++);
    --bits;
    printf("TYPE has %d bits\n", bits);
    sscanf(argv[1],"%x", &x);

    printf("0x%x\n",reverse(x, bits));
    return 0;
}

Hinweise:

gcc eine Warnung aus, die auf die 64-bit-Konstanten
die printfs wird Warnungen generieren zu
Wenn Sie mehr als 64bit, der code sollte einfach genug sein, um verlängern

Entschuldige ich mich im Voraus für die Codierung Verbrechen ich begangen oben Gnade guter Herr!

InformationsquelleAutor freespace

1

Gibt es eine schöne Sammlung von "Bit Twiddling Hacks", einschließlich einer Vielzahl von einfachen und nicht so einfachen bit-Umkehr-algorithmen codiert C an http://graphics.stanford.edu/~seander/bithacks.html.

Mir persönlich gefällt das "Offensichtliche" algorigthm ( http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious ), weil, gut, das ist klar. Einige andere mögen, erfordern Sie weniger Anweisungen ausführen. Wenn ich wirklich brauchen, um zu optimieren, das heck aus, was ich wählen kann, die nicht so offensichtlich, aber schnellere Versionen. Ansonsten, für die Lesbarkeit, Wartbarkeit und Portabilität, die ich wählen würde, die Offensichtlich einen.

InformationsquelleAutor mxg

Hier ist eine allgemein nützliche Variante. Sein Vorteil ist seine Fähigkeit, in Situationen zu arbeiten, wo die bit-Länge des Wertes rückgängig gemacht werden -- das Codewort -- ist unbekannt, aber garantiert nicht mehr als einen Wert nennen wir maxLength. Ein gutes Beispiel für diesen Fall ist der Huffman-code kennen.

Den code unten funktioniert auf Codewörter von 1 bis 24 bit Länge. Es wurde optimiert für die schnelle Ausführung auf einem Pentium D. Hinweis, dass der Zugriff auf die lookup-Tabelle so viele wie 3 mal pro verwenden. Ich experimentierte mit viele Variationen, reduziert sich diese Zahl auf 2, auf Kosten einer größeren Tabelle (4096 und 65.536 Einträge). Diese version mit der 256-byte-Tabelle, war der klare Sieger, teilweise, weil es so vorteilhaft für die Tabelle Daten in die caches, und vielleicht auch, weil der Prozessor verfügt über einen 8-bit-lookup-Tabelle/übersetzung-Anweisung.

const unsigned char table[] = {  
0x00,0x80,0x40,0xC0,0x20,0xA0,0x60,0xE0,0x10,0x90,0x50,0xD0,0x30,0xB0,0x70,0xF0,  
0x08,0x88,0x48,0xC8,0x28,0xA8,0x68,0xE8,0x18,0x98,0x58,0xD8,0x38,0xB8,0x78,0xF8,  
0x04,0x84,0x44,0xC4,0x24,0xA4,0x64,0xE4,0x14,0x94,0x54,0xD4,0x34,0xB4,0x74,0xF4,  
0x0C,0x8C,0x4C,0xCC,0x2C,0xAC,0x6C,0xEC,0x1C,0x9C,0x5C,0xDC,0x3C,0xBC,0x7C,0xFC,  
0x02,0x82,0x42,0xC2,0x22,0xA2,0x62,0xE2,0x12,0x92,0x52,0xD2,0x32,0xB2,0x72,0xF2,  
0x0A,0x8A,0x4A,0xCA,0x2A,0xAA,0x6A,0xEA,0x1A,0x9A,0x5A,0xDA,0x3A,0xBA,0x7A,0xFA,  
0x06,0x86,0x46,0xC6,0x26,0xA6,0x66,0xE6,0x16,0x96,0x56,0xD6,0x36,0xB6,0x76,0xF6,  
0x0E,0x8E,0x4E,0xCE,0x2E,0xAE,0x6E,0xEE,0x1E,0x9E,0x5E,0xDE,0x3E,0xBE,0x7E,0xFE,  
0x01,0x81,0x41,0xC1,0x21,0xA1,0x61,0xE1,0x11,0x91,0x51,0xD1,0x31,0xB1,0x71,0xF1,  
0x09,0x89,0x49,0xC9,0x29,0xA9,0x69,0xE9,0x19,0x99,0x59,0xD9,0x39,0xB9,0x79,0xF9,  
0x05,0x85,0x45,0xC5,0x25,0xA5,0x65,0xE5,0x15,0x95,0x55,0xD5,0x35,0xB5,0x75,0xF5,  
0x0D,0x8D,0x4D,0xCD,0x2D,0xAD,0x6D,0xED,0x1D,0x9D,0x5D,0xDD,0x3D,0xBD,0x7D,0xFD,  
0x03,0x83,0x43,0xC3,0x23,0xA3,0x63,0xE3,0x13,0x93,0x53,0xD3,0x33,0xB3,0x73,0xF3,  
0x0B,0x8B,0x4B,0xCB,0x2B,0xAB,0x6B,0xEB,0x1B,0x9B,0x5B,0xDB,0x3B,0xBB,0x7B,0xFB,  
0x07,0x87,0x47,0xC7,0x27,0xA7,0x67,0xE7,0x17,0x97,0x57,0xD7,0x37,0xB7,0x77,0xF7,  
0x0F,0x8F,0x4F,0xCF,0x2F,0xAF,0x6F,0xEF,0x1F,0x9F,0x5F,0xDF,0x3F,0xBF,0x7F,0xFF};  


const unsigned short masks[17] =  
{0,0,0,0,0,0,0,0,0,0X0100,0X0300,0X0700,0X0F00,0X1F00,0X3F00,0X7F00,0XFF00};  


unsigned long codeword;   //value to be reversed, occupying the low 1-24 bits  
unsigned char maxLength;  //bit length of longest possible codeword (<= 24)  
unsigned char sc;         //shift count in bits and index into masks array  


if (maxLength <= 8)  
{  
   codeword = table[codeword << (8 - maxLength)];  
}  
else  
{  
   sc = maxLength - 8;  

   if (maxLength <= 16)  
   {
      codeword = (table[codeword & 0X00FF] << sc)  
               |  table[codeword >> sc];  
   }  
   else if (maxLength & 1)  //if maxLength is 17, 19, 21, or 23  
   {  
      codeword = (table[codeword & 0X00FF] << sc)  
               |  table[codeword >> sc] |  
                 (table[(codeword & masks[sc]) >> (sc - 8)] << 8);  
   }  
   else  //if maxlength is 18, 20, 22, or 24  
   {  
      codeword = (table[codeword & 0X00FF] << sc)  
               |  table[codeword >> sc]  
               | (table[(codeword & masks[sc]) >> (sc >> 1)] << (sc >> 1));  
   }  
}

InformationsquelleAutor The Neocompressionist

0

Wie etwa:
```
long temp = 0;
int counter = 0;
int number_of_bits = sizeof(value) * 8; //get the number of bits that represent value (assuming that it is aligned to a byte boundary)

while(value > 0)            //loop until value is empty
{
    temp <<= 1;             //shift whatever was in temp left to create room for the next bit
    temp |= (value & 0x01); //get the lsb from value and set as lsb in temp
    value >>= 1;            //shift value right by one to look at next lsb

    counter++;
}

value = temp;

if (counter < number_of_bits)
{
    value <<= counter-number_of_bits;
}
```
(Ich gehe davon aus, dass Sie wissen, wie viele bits mit dem Wert hält und es ist gespeichert in number_of_bits)

Offensichtlich temp benötigt, um die längste vorstellbare Daten-Typ und beim kopieren von temp wieder in Wert, alle die überflüssigen bits, die in temp sollte auf Magische Weise verschwinden (denke ich!).

Oder, das 'c' Weg wäre, zu sagen :
```
while(value)
```
Ihrer Wahl
- was würde Ihr Algorithmus die Ausgabe bei 1 als Eingabe-Wert? Es scheint mir, als würde es wieder 1 wieder, was nicht richtig ist.
- Sie auch verwendet werden &= wo Sie gemeint |=
- Sie sind richtig 1 produzieren würde 1 offensichtlich um etwas anderes, würden Sie brauchen, zu wissen, welche Art von Wert (also die Anzahl der bits). Man könnte einen Zähler und Verschiebung nach Links durch (Anzahl der bit - Zähler) nach der Schleife. guter Punkt ... |= ist korrekt, es zahlt sich aus, den code zu überprüfen offensichtlich!
InformationsquelleAutor TK.
0

Können wir speichern Sie die Ergebnisse auf die Umkehrung aller möglichen 1-byte-Sequenzen in einem array (256 verschiedene Einträge), dann verwenden Sie eine Kombination von lookups in dieser Tabelle und einige oring-Logik zu erhalten, das Gegenteil von integer ist.
- Nicht diese Methode ein wenig speicherintensiv? Denken Sie nicht, dass eine mehr programmatische Lösung wäre die Arbeit besser/effizienter?
InformationsquelleAutor

Hier ist eine variation und Korrektur der TK-Lösung, die könnte klarer sein als die Lösungen von sundar. Es braucht einzelne bits von t und schiebt Sie in return_val:

typedef unsigned long TYPE;
#define TYPE_BITS sizeof(TYPE)*8

TYPE reverser(TYPE t)
{
    unsigned int i;
    TYPE return_val = 0
    for(i = 0; i < TYPE_BITS; i++)
    {/*foreach bit in TYPE*/
        /* shift the value of return_val to the left and add the rightmost bit from t */
        return_val = (return_val << 1) + (t & 1);
        /* shift off the rightmost bit of t */
        t = t >> 1;
    }
    return(return_val);
}

InformationsquelleAutor Frosty

0

Den generischen Ansatz hat, würde die Arbeit für die Objekte von jedem Typ in jeder Größe wäre eine Umkehrung der bytes des Objekts, und die umgekehrte Reihenfolge der bits in jedem byte. In diesem Fall wird die bit-Ebene-Algorithmus ist an eine konkrete Anzahl von bits (ein byte), während die "variable" - Logik (hinsichtlich der Größe) angehoben wird, auf der Ebene von ganzen bytes.

InformationsquelleAutor AnT

Hier ist meine Verallgemeinerung von freespace Lösung (im Falle, dass wir eines Tages 128-bit-Maschinen). Es ergibt sich im Sprung-gratis-code bei der Kompilierung mit gcc -O3, und ist offensichtlich unempfindlich für die definition von foo_t auf vernünftige Maschinen. Leider es hängt nicht von shift wird eine Kraft von 2!

#include <limits.h>
#include <stdio.h>

typedef unsigned long foo_t;

foo_t reverse(foo_t x)
{
        int shift = sizeof (x) * CHAR_BIT / 2;
        foo_t mask = (1 << shift) - 1;
        int i;

        for (i = 0; shift; i++) {
                x = ((x & mask) << shift) | ((x & ~mask) >> shift);
                shift >>= 1;
                mask ^= (mask << shift);
        }

        return x;
}       

int main() {
        printf("reverse = 0x%08lx\n", reverse(0x12345678L));
}

InformationsquelleAutor Bernd Jendrissek

0

Bei bit-Umkehr ist mal kritisch, und vor allem in Verbindung mit FFT, ist der beste store das ganze etwas Umgekehrt array. In jedem Fall, dieses array wird in der Größe kleiner als die Wurzeln der Einheit, die vorausberechnete in FFT, Cooley-Tukey-Algorithmus. Eine einfache Möglichkeit zur Berechnung des array ist:
```
int BitReverse[Size]; //Size is power of 2
void Init()
{
   BitReverse[0] = 0;
   for(int i = 0; i < Size/2; i++)
   {
      BitReverse[2*i] = BitReverse[i]/2;
      BitReverse[2*i+1] = (BitReverse[i] + Size)/2;
   }
} //end it's all
```
- Ich bin mir nicht sicher, was Ihr code versucht zu erreichen. Der Algorithmus vor, für Größe==16, erzeugt eine BitReverse: [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15].
InformationsquelleAutor ivan

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.