Dislikes Dislikes:  0
Ergebnis 1 bis 7 von 7

Thema: Bitlänge eines gespeicherten unsigned int in C ermitteln

  1. #1

    Registriert seit
    05.12.15
    Danke (erhalten)
    6
    Gefällt mir (erhalten)
    15

    Standard Bitlänge eines gespeicherten unsigned int in C ermitteln

    Anzeige
    Hey,

    Angenommen ich speichere einen Integer und schneide die führenden nullen ab, wie ermittle ich am effizientesten die übrig gebliebene Bitlänge?

    Vorschlag:

    Code:
    void bitlength(uint32_t t, uint32_t *counter)
    {
    	*counter = 0;
    	while(t <<= 1){
    		*counter += 1;
    	}
    }
    Vielleicht hilft auch mein Anwendungszweck, um den Sinn dahinter zu sehen.

    Ich habe zwei Arrays, sagen wir einfach
    Code:
    typedef uint32_t arr[12];
    const arr C;
    
    void mod_arr()
    {
    	//intepretiere B . A ( . bezeichnet Concatenation)
    	//berechne B . A mod C
    	//speichere in A
    }
    
    void main()
    {
    	arr A,B;
    	mod_arr(A,B);
    }
    Meine Idee zu mod_arr() ist: Berechne B - C so lange, wie B > C. Danach bestimmte die fehlenden Bits von links, d.h. Sum(i=0, n) bitlength(B[11-i]); sobald die erste bitlength > 0 ist, breche ab*. Speichere die fehlenden Bits an der Abbruchstelle und die Summe aller fehlenden Bits. Shifte B um die Summe aller Bits nach links, sodass B die Form [0b1....|0b01...|...|0b0|...|0b0] hat. Befülle die fehlenden Stellen mit A. Linksshifte A um die selbe Anzahl der Stellen. So hat A geht A gegen 0.

    Dieses Vorgehen wird so lange wiederholt, wie A != 0 und B > C. Speichere anschließend das Ergebnis in C.

    Wie man meiner Beschreibung nach sieht, benötige ich dafür die Operationen: bitlength, sum_bitlength, shift_left, fill_right, compare.

    Ich habe aber das Gefühl, dass mein Vorgehen nicht sonderlich effizient ist, um mein Ziel zu erreichen.



    * bei Constant-Time Implementation würde ich ab dieser Stelle einen anderen Counter erhöhen und n von Beginn an bei 11 belassen.
    Geändert von Shalec (13.09.17 um 15:02 Uhr)

  2. #2
    Moderator
    Registriert seit
    30.06.08
    Danke (erhalten)
    27
    Gefällt mir (erhalten)
    827

    Standard

    Du kannst im Speicher keine führenden Nullen wegschneiden. Die Größe ist der Variablen ist "fix".
    Du kannst per Bitmask von "rechts nach links" deinen integer durchgehen, bis du auf das erste gesetzte Bit stößt und daraus die "Bitlänge" des _WERTES_ ermitteln.

    Btw. Wenn es dir hilft, kannst du in C auch einen Integer mit einer bestimmten Länge vorgeben. Das macht man innerhalb einer Strukturdefinition.

    Ich habe aber das Gefühl, dass mein Vorgehen nicht sonderlich effizient ist, um mein Ziel zu erreichen.
    Beschreibe doch mal in Worten, was du mit dem Code ueberhaupt bezwecken willst - vielleicht gibt es für die Aufgabenstellung andere Lösungen.
    Wenn ein Gesetz nicht gerecht ist, dann geht die Gerechtigkeit vor dem Gesetz!

    Habo Blog - http://blog.hackerboard.de/

  3. #3

    Registriert seit
    05.12.15
    Danke (erhalten)
    6
    Gefällt mir (erhalten)
    15

    Standard

    Also mein oberstes Ziel ist folgendes zu berechnen:

    Code:
    left . right mod modulo
    wobei "." für eine Aneinanderhängung (Concatenation) steht.

    left und right sind jeweils so groß, wie der modulo. Also alle vom selben obigen Typ "arr".

    Meine Idee ist dahinter:

    1. Berechne left mod modulo so lange, wie left > modulo

    Speichere: arraylen = arraylength(right). (Anzahl aller gesetzter Bits in right)
    Falls arraylen != 0:

    1a. Speichere bitlen = bitlength(left); (Anzahl aller fehlender Bits, von links)
    Shifte den gesamten Array "left" um höchstens arraylen, mindestens bitlen vollständig nach links durch, sodass diese fehlenden Bits nun auf der rechten Seite als Nullen auftauchen.

    1b. Befülle diese Nullen mit Elementen aus "right", in right von links nach rechts ausgehend.

    1c. Shifte nun "right" um die selbe Anzahl wie in 1a nach links, sodass immer an der höchsten Position die höchsten Zahlen stehen.

    4. Wiederhole 1 bis die arraylength(right) == 0.

    5. Gebe "left " als Ergebnis zurück.


    (Man kann sich das wie ein Schieberegister vorstellen.)

  4. #4
    Moderator
    Registriert seit
    30.06.08
    Danke (erhalten)
    27
    Gefällt mir (erhalten)
    827

    Standard

    So ganz schlau werde ich daraus noch nicht - z.B. verstehe ich nicht, wozu dein typedef gut sein soll.

    Ganz allgemein - willst du das so loesen um Überträge zu behandeln?
    Wenn ein Gesetz nicht gerecht ist, dann geht die Gerechtigkeit vor dem Gesetz!

    Habo Blog - http://blog.hackerboard.de/

  5. #5
    Moderator Avatar von CDW
    Registriert seit
    20.07.05
    Danke (erhalten)
    34
    Gefällt mir (erhalten)
    846

    Standard

    Zitat Zitat von Shalec Beitrag anzeigen
    Hey,

    Angenommen ich speichere einen Integer und schneide die führenden nullen ab, wie ermittle ich am effizientesten die übrig gebliebene Bitlänge?

    Vorschlag:

    Code:
    void bitlength(uint32_t t, uint32_t *counter)
    {
    	*counter = 0;
    	while(t <<= 1){
    		*counter += 1;
    	}
    }
    man ffs
    SYNOPSIS
    #include <strings.h>

    DESCRIPTION
    The ffs(), ffsl() and ffsll() functions find the first (least
    significant) bit set in value and return the index of that bit.

    The fls(), flsl() and flsll() functions find the last (most significant)
    bit set in value and return the index of that bit.

    Bits are numbered starting at 1, the least significant bit. A return
    value of zero from any of these functions means that the argument was
    zero.

    SEE ALSO
    bitstring(3), bitset(9)
    oder __builtin_ffs Erweiterung des GCC. MS-Compiler sollte auch etwas ähnliches anbieten. Sinn: Hardware bietet oft direkte Unterstützung für solche Manipulationen oder Abfragen:
    Find first set - Wikipedia
    das sollte wesentlich schneller sein, als Eigenbaulösungen (die man ggf. noch als Fallback benutzen kann).
    Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
    Selig, wer nichts zu sagen hat und trotzdem schweigt.

  6. Gefällt mir Chromatin, Shalec liked this post
  7. #6

    Registriert seit
    05.12.15
    Danke (erhalten)
    6
    Gefällt mir (erhalten)
    15

    Standard

    Super, ich wusste, dass es sowas auch auf hardware-Basis gibt. ARM wird das anbieten in seiner ARMv7-M Architektur. Wie nutze ich denn innerhalb von C einen inline Befehl? Z.B. diesen:

    Code:
    __builtin_clz[l,ll,imax]
    Mir geht es tatsächlich nur um die führenden Nullen.

    Angenommen ich möchte von der Variable
    Code:
    uint32_t entry;
    die Anzahl der führenden Nullen auf Bitebene wissen, wie würde ich obige (count leading zeroes) Funktion anwenden?

  8. #7
    Moderator Avatar von CDW
    Registriert seit
    20.07.05
    Danke (erhalten)
    34
    Gefällt mir (erhalten)
    846

    Standard

    Anzeige
    Code:
    #include <stdio.h>                                                                         
    #include <limits.h>                                                                        
                                                                                               
    #define TEST_BITS 32 /* must be power of 2 */                                         
    #define TEST_WIDTH ((1 << TEST_BITS)-1)                                                    
                                                                                               
    #if UINT_MAX == TEST_WIDTH                                                                 
        typedef unsigned int test_t;                                                           
        #define CLZ(x) (__builtin_clz(x))                                                      
    #elif ULONG_MAX == TEST_WIDTH                                                              
        typedef unsigned long test_t;                                                          
        #define CLZ(x) (__builtin_clzl(x))                                                     
    #elif TEST_WIDTH < ULONG_MAX                                                               
        typedef unsigned long test_t;                                                          
        /* y & (x-1) == y mod x */                                                             
        #define CLZ(x) ( __builtin_clzl(x) & (TEST_BITS-1) )                                   
    #endif   
    
                                                                                      
    void test(test_t x) {                                                                      
        if (x == 0) {                                                                          
            puts("x == 0 :(");                                                                 
        } else {                                                                               
            printf("x: %x, leading zeros: %d\n", x, CLZ(x));                                   
        }                                                                                      
    }                                                                                          
    int main(int argc, char* argv[]) {                                                         
        test(0);                                                                               
        test(1);                                                                               
        test(0xFF);                                                                            
        test(0xFFFF);                                                                          
        test(0xFFFFFF);                                                                        
        test(0xFFFFFFFF);                                                                      
        return 0;                                                                              
    }

    Code:
    x == 0 :(
    x: 1, leading zeros: 31
    x: ff, leading zeros: 24
    x: ffff, leading zeros: 16
    x: ffffff, leading zeros: 8
    x: ffffffff, leading zeros: 0
    Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
    Selig, wer nichts zu sagen hat und trotzdem schweigt.

  9. Danke Shalec thanked for this post
    Gefällt mir Shalec liked this post

Ähnliche Themen

  1. Antworten: 3
    Letzter Beitrag: 08.03.11, 23:46
  2. String <=> cli::array^ Umwandlung
    Von ChiefWiggum im Forum Code Kitchen
    Antworten: 6
    Letzter Beitrag: 08.02.08, 20:30
  3. Antworten: 3
    Letzter Beitrag: 22.10.06, 16:05
  4. Antworten: 0
    Letzter Beitrag: 22.04.06, 17:14
  5. wert eines pcs ermitteln
    Von Sven im Forum Off topic-Zone
    Antworten: 3
    Letzter Beitrag: 09.05.04, 19:45

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •