Bit Auflösung einer ganzen Zahl, ignoriert integer Größe und endianness
https://stackoverflow.com/questions/63776
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
eine ganze Zahl typedef Gegeben:
typedef unsigned int TYPE;
oder
typedef unsigned long TYPE;
Ich habe den folgenden Code, um die Bits einer ganzen Zahl zu umkehren:
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;
}
Man muss halt nur ersten reverse_int_setup () ausgeführt werden, die speichert eine ganze Zahl mit dem höchsten Bit eingeschaltet, dann jeder Anruf reverse_int ( arg ) gibt arg mit seinem Bits umgekehrt (als Schlüssel zu einem binären Baum verwendet wird, von einem zunehmenden Zähler genommen, aber das ist mehr oder weniger irrelevant).
Gibt es eine plattformunabhängige Art und Weise den richtigen Wert für MAX_INT nach dem Aufruf in der Kompilierung Zeit, um reverse_int_setup (); Ansonsten ist es ein Algorithmus man bedenkt, besser / schlanker als die, die ich für reverse_int haben ()?
Danke.
Lösung
#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;
}
Dieses Mal habe ich Idee, die ‚Anzahl von Bits‘ von TK verwendet haben, aber machte es etwas mehr tragbar, indem kein Byte enthält 8 Bit und stattdessen mit dem CHAR_BIT Makro annimmt. Der Code ist effizienter nun (mit der inneren for-Schleife entfernt). Ich hoffe, dass der Code auch etwas weniger kryptischen diesmal. :)
Die Notwendigkeit Zählung für die Verwendung ist, dass die Anzahl der Positionen, mit denen wir einem wenig variiert in jeder Iteration verschieben - wir das Bit ganz rechts von 31 Positionen (unter der Annahme, 32-Bit-Zahl) zu bewegen, wobei das zweite Bit ganz rechts um 29 Positionen und so weiter. Daher zählen bei jeder Iteration wie i erhöht verringern müssen.
Ich hoffe, dass wenig Informationen hilfreich erweist sich den Code zu verstehen ...
Andere Tipps
Das folgende Programm dient eine schlankere Algorithmus zum Umkehren Bits zu demonstrieren, die leicht erweitert werden kann, um 64-Bit-Zahlen zu verarbeiten.
#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 mit 0x12345678 getestet 0x1e6a2c48 zu erzeugen, die die richtige Antwort ist.
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 in gcc unter Windows in Ordnung, aber ich bin mir nicht sicher, ob es vollständig plattformunabhängig ist. Einige Orte von Interesse sind:
-
die Bedingung in dem for-Schleife - es wird davon ausgegangen, dass, wenn Sie Schicht 1 über die am weitesten links stehenden Bit nach links, Sie erhalten entweder ein 0 mit den 1 ‚herausfallen‘ (was ich erwarten würde und was für gute alte Turbo C gibt iirc) oder die 1 umkreist und Sie erhalten eine 1 (was gcc Verhalten) zu sein scheint.
-
die Bedingung in der inneren while-Schleife: siehe oben. Aber es ist eine seltsame Sache passiert hier: in diesem Fall gcc scheint die 1 herausfallen zu lassen und nicht umkreisen
Der Code könnte kryptischen beweisen. Wenn Sie interessiert sind und benötigen eine Erklärung zögern Sie bitte nicht fragen - ich werde es irgendwo setzen
@ ΤΖΩΤΖΙΟΥ
In Antwort auf ΤΖΩΤΖΙΟΥ ‚s Kommentare, präsentiere ich Version von modifizierten oben, die für Bit-Breite auf einer oberen Grenze abhängig ist.
#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;
}
Weitere Informationen:
- gcc wird sich auf die 64-Bit-Konstanten warnen
- die printfs werden Warnungen erzeugen zu
- Wenn Sie mehr als 64-Bit benötigen, sollte der Code einfach genug sein, zu verlängern
ich im Voraus entschuldigen für die Codierung Verbrechen, die ich oben begangen - Barmherzigkeit guter Herr
!Es gibt eine schöne Sammlung von "Bit Twiddling Hacks", darunter eine Vielzahl von einfachen und nicht so einfach Bit Umkehr in C codiert Algorithmen unter http://graphics.stanford.edu/~seander/bithacks.html .
Ich persönlich mag die "Offensichtliche" algorigthm ( http: //graphics.stanford edu / ~ seander / bithacks.html # BitReverseObvious ), weil, na ja, es ist offensichtlich. Einige der anderen erfordern weniger Anweisungen auszuführen. Wenn ich wirklich das Heck aus etwas brauchen optimieren kann ich die nicht so offensichtlich, aber schnellere Versionen wählen. Andernfalls zur besseren Lesbarkeit, Wartbarkeit und Portabilität würde ich das Offensichtliche einer wählen.
Hier ist eine allgemeine nützliche Variation. Sein Vorteil ist seine Fähigkeit, in Situationen zu arbeiten, in dem der Bitlänge des Wertes umgekehrt werden - das Codewort - ist unbekannt, aber garantiert nicht einen Wert übersteigt wir maxLength nennen wollen. Ein gutes Beispiel für diesen Fall ist Huffman-Code-Dekompression.
Der folgende Code funktioniert auf Codeworte von 1 bis 24 Bit Länge. Es hat sich für die schnelle Ausführung auf einem Pentium D. optimiert Beachten Sie, dass es die Lookup-Tabelle so viele wie 3-mal pro Anwendung zugreift. Ich experimentierte mit vielen Variationen, die diese Zahl auf 2 auf Kosten einer größeren Tabelle (4096 und 65.536 Einträge) reduziert. Diese Version mit der 256-Byte-Tabelle, war der klare Sieger, zum Teil, weil es so vorteilhaft ist für die Datentabelle in dem Cache-Speicher zu sein, und vielleicht auch, weil der Prozessor eine 8-Bit-Lookup-Tabelle / Übersetzung Anweisung hat.
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));
}
}
Wie wäre:
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 Wert hält, und es wird in number_of_bits gespeichert)
Offensichtlich braucht Temp die längste vorstellbaren Datentyp zu sein, und wenn Sie Temp wieder in Wert, werden alle Fremd Bits in Temp kopieren sollte auf magische Weise verschwinden (glaube ich!).
Oder die 'c' Art und Weise zu sagen wäre:
while(value)
Ihre Wahl
Wir können die Ergebnisse speichern aller möglichen 1-Byte-Sequenzen in einem Array (256 verschiedene Einträge) Umkehren, dann eine Kombination von Lookups in dieser Tabelle verwenden und einige oring Logik das Gegenteil von integer zu erhalten.
Hier ist eine Variation und Korrektur TK-Lösung, die als die Lösungen von sundar klarer sein könnte. Es dauert 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);
}
Der generische Ansatz hat für Objekte jeglicher Art jeder Größe der Bytes des Objekts rückgängig zu machen wäre funktionieren würde, und die die Reihenfolge der Bits in jedem Byte umkehren. In diesem Fall wird das Bit-Level-Algorithmus auf eine konkrete Anzahl von Bits (ein Byte) gebunden, während die „Variable“ Logik (im Hinblick auf die Größe) auf das Niveau der gesamten Bytes angehoben wird.
Hier ist meine Verallgemeinerung der freien Speicherplatz-Lösung (falls wir einen Tag bekommen 128-Bit-Maschinen). Es führt zu Code Sprung frei, wenn sie mit gcc O3 kompiliert und ist offensichtlich unempfindlich gegen die Definition von foo_t auf gesunden Maschinen. Leider! Es hängt auf Verschiebung eine Potenz von 2 sein
#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));
}
Bei Bit-Umkehr ist zeitkritisch und vor allem in Verbindung mit FFT, ist die beste die gesamte Bit umgekehrt Array zu speichern. In jedem Fall wird diese Anordnung in der Größe kleiner sein als die Wurzeln der Einheit, die in FFT Cooley-Tukey-Algorithmus vorberechnet werden muß. Eine einfache Möglichkeit, um das Array zu berechnen 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
