4. shiften mit multilength integers

shiften mit multilength integers

  • ?

    hi leute,

    wie kann man mit C shifts von beliebig großen zahlen durchführen? also ich hab mir eine funktion shl/shr vorgestellt, die integerzahlen von beliebiger größe in form eines void-zeigers nimmt. als zweiten parameter die länge des arrays, als dritten, die anzahl der bits, um die geshiftet werden soll. jetzt hab ich aber bemerkt, daß ein shift in C auch vom Vorzeichen des datentyps abhängen kann. also '<<' shiftet immer nullen und '>>' shiftet bei signed einsen, warum das? damit das vorzeichen nicht verloren geht?

    also jedenfalls will ich nur nullen 'reinshiften', so wie die asm befehle shl und shr. intern muss ich vermutlich mit chars arbeiten, da die größe der zahlen auch ungerade sein kann. aber das hauptproblem: ich muss ja immer alle bytes die links oder rechts vom momentanen stehen speichern, bevor ich die daneben drüber schiebe. wie soll ich das anstellen bzw. welchen vorschlag haltet ihr für am sinnvollsten?

    - eine rekursive funktion, die sich solange selbst aufruft, bis die shiftzahl 8 beträgt (dann bräuchte man nur ein byte speichern, wobei ich momentan noch nicht so recht weiß wie ich da vorgehn soll.)
    - den kompletten teil, der überschrieben wird in einem dynamischen buffer speichern und dann mit memmove drüberschreiben, dann eben den alten wieder anhängen?
    -... sonstige vorschläge, aber bitte keine fertigen codes

    Vielen dank schonmal im voraus

    0
  • U

    http://michael.dipperstein.com/bitlibs/bitarray-0.2.zip
    🙂

    0
  • ?

    hi undertaker,

    danke für den link hab mir alles mal angeschaut, aber ein paar sachen sind mir noch unklar, diese makros zum beispiel:

    /* position of bit within character */
#define BIT_CHAR(bit)         ((bit) / CHAR_BIT)

    sollte es korrekterweise nicht eher heißen 'position of character within character-array'? weil mit dem '%'-operator bekommt man doch eigentlich den 'offset' des bits im byte.

    /* array index for character containing bit */
#define BIT_IN_CHAR(bit)      (1 << (CHAR_BIT - 1 - ((bit)  % CHAR_BIT)))

    was erhält man mit diesem makro? das uchar element im array, welches das bit 'bit' enthält? so stehts jedenfalls im comment. das wäre aber dann das gleiche wie oben (jedenfalls wie der code oben). irgendwie hab ich das gefühl, dass die kommentare nicht zum code passen und das das englisch des autors nicht das allerbeste ist (oder aber meins hat sich jetzt auch mal urlaub gegönnt ;))

    noch eine andere geschichte: bin mir mit dem little und big endian zeugs nicht so ganz sicher...

    #include <stdio.h>

int main()
{
    char s[]="abc";
    unsigned a=*(unsigned*)s;        
    printf("%x\n", a); // ausgabe: 636261
    printf("%s\n", &a); //ausgabe: abc
    return 0;
}

    nach dem bsp. zu urteilen, hab ich ne little endian maschine, aber wann macht das in meinem fall einen unterschied? doch nur wenn solche datentypen wie ints shorts o.ä. in die register geladen werden oder? im speicher liegen sie praktsich immernoch als bigendian vor, so wie auch bei deinem link, wenn das MSB an position 0 steht.

    0
  • U

    huch, der code scheint tatsächlich ziemlich mies zu sein. allein das 'modulo' ist unverzeihbar (saulangsam).
    um ein bit in einem array zu setzen (LSB ganz links, aus sicht des arrays) würde ich das so machen:

    // setzt ein bit in einem array 
void BitArray_Set (unsigned char *array, int bit)
{
    int bytepos = bit>>3;   // gesuchtes byte im bit-array
    int bitpos = 7 - bit + (bytepos<<3);  // bit in diesem byte

    array[bytepos] |= (1<<bitpos);  // bit 'bitpos' im array-elment 'bytepos' setzen 
}

    zur 'endianess': bei little endian werden die bytes 'vertauscht' im speicher gehalten, also die niederwertigen kommen an die kleineren adressen. das muss man berücksichtigen, wenn man multibyte-werte (int, long, ect...) zwischen verschiedenen systemen austauschen will.
    🙂

    0
  • ?

    ja so ein paar bitschiebe-optimierungen hab ich auch reingepackt, war nur von den comments irritiert. und was das mit dem endian betrifft: heißt das dann das bei ints, longs etc. nur beim ausgeben (stdin, files) die bytes vertauscht werden (also bei hexadeizmaler aushgabe oder so)? weil so wie ichs momentan bei mir habe ist das MSB von byte 0 das höchstwertigste bit überhaupt. alle nachfolgenden haben dann einen gerigneren wert. bei einem unsigned int (4 byte) schreibe ich doch, wenn ichs in binärform ausgeben will, auch for(unsigned i=31; ...) und müsste dann doch eigentlich das MSB eines byte erwischen (nach meinem verständnis, das byte mit dem abstand 0 von der adresse der variablen)... wenn ich aber bei bit 31 im letzten byte landen würde, dann müsste entweder dieses bit ganz am ende stehn oder aber, wenn es, wie in meinem schaubild, das MSB irgendeines bytes ist, bei nummer 7 (von 31) also irgendwo in der mitte...

    +-------------------------+--------------------------+--------------------------+--------------------------+
+ 7  6  5  4  3  2  1  0  +  7  6  5  4  3  2  1  0  +  7  6  5  4  3  2  1  0  +  7  6  5  4  3  2  1  0  +
+-------------------------+--------------------------+--------------------------+--------------------------+
 31 30 29 28 27 26 25 24     23 22 21 20 19 18 17 16    15 14 13 12 11 10 9  8     7  6  5  4  3  2  1  0

    könnte mir jemand das nochmal erläutern wie die bytes und bits im speicher liegen? ich blick gerade gar nicht mehr durch 😞

    0
  • U

    also, die einzelnen bits werden nie vertauscht, na jedenfalls wenn es so ist, könnte es kein C programm der welt bemerken, denn die ganzen shift- und logik-operationen usw. gehen immer davon aus, dass in einem byte bit7 das höchstwertigste ist.
    aber bei multibyte-variablen werden die bytes unterschiedlich angeordnet. ein (long)0x12345678 als 'big endian' gespeichert, ist im speicher 0x12, 0x34, 0x56, 0x78. als 'little endian' gespeichert ist es 0x78, 0x56, 0x34, 0x21.
    🙂

    0
Anmelden zum Antworten