Bitlänge eines gespeicherten unsigned int in C ermitteln

S

Shalec

0
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.
 
Zuletzt bearbeitet:
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.
Zum Vergrößern anklicken....

Beschreibe doch mal in Worten, was du mit dem Code ueberhaupt bezwecken willst - vielleicht gibt es für die Aufgabenstellung andere Lösungen.
 
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.)
 
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?
 
Shalec hat gesagt.:
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;
	}
}
Zum Vergrößern anklicken....
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)
Zum Vergrößern anklicken....
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).
 
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: 
[COLOR=#000000][FONT=monospace]__builtin_clz[l,ll,imax][/FONT][/COLOR]

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?
 
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
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben