Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek dla www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

operacje na bitach - zalewanie slowa jedynkami na prawo

15 Sty 2010 14:56 2802 35
  • Poziom 27  
    Witam. Mam nastepujacy problem. Potrzebuje zestawu kolejnych operacji na bitach(najlepiej jakąś sensowna sekwencje tzn 2, 3, max 4) ktore przeksztalca mi bajt w taki sposob ze patrzac od lewej po odnalezieniu pierwszej jedynki wszystkie bity na prawo ustawiane beda na 1. przyklad: 00110011->00111111, inny przyklad: 00000100->00000111. Wymagania:

    -ilosc operacji potrzebnych do wykonania musi byc stala - tzn nie zalezna od uzytego bajtu wejsciowego. a co za tym idze:
    -zadnych petli
    -zadnych (if - ow);

    Bo tak to potrafie sobie sam zrobic:) Negacje,ory,andy,xory i inne wynalazki dozwolone.

    Pisze w C, na atmega8 jesli to komus potrzebne.
  • Specjalista - Mikrokontrolery
    Najprościej za pomocą 256 elementowej tablicy LUT
  • Poziom 27  
    Moglbys powiedziec o co w tym biega?
  • Pomocny post
    Poziom 34  
    Tablica LUT jest prostą tablicą przekształcającą wszystkie wartości wejściowe na odpowiednie wartości wyjściowe. Jednak ową operację "zalewania w prawo" można zrealizować chociaż by przez przesunięcia w prawo i alternatywę:
    Code:
    v |= (v >> 1);
    
    v |= (v >> 2);
    v |= (v >> 4);
  • Moderator Programowanie
    Może się mylę, ale do prosto osiągnąć coś takiego w asemblerze :
    Zakładam że bajty są MSB -> LSB
    1. Tworzysz tablicę dopełnień
    - 1111 1111
    - 0111 1111
    - 0011 1111 itd.
    2. porównujesz bajt wejściowy z elementem tablicy (może być odejmowanie i test zera)
    3. jeżeli będzie równy lub mniejszy to wynikiem będzie funkcja OR bajty startowego i elementu tablicy.
    4. jeżeli element tablicy będzie większy (aby zachować zawsze tę samą ilość działań) dajesz odpowiednią ilość NOP.
  • Poziom 27  
    BoskiDialer napisał:
    Jednak ową operację "zalewania w prawo" można zrealizować chociaż by przez przesunięcia w prawo i alternatywę:
    Code:
    v |= (v >> 1);
    
    v |= (v >> 2);
    v |= (v >> 4);


    Dokladnie o cos w tym stylu chodzilo. Dzieki:) Jestes Boski:D
  • Poziom 43  
    Ale tam ma być 1, 2, 3, ... a nie 1, 2, 4... .
  • Poziom 34  
    Kolejne potęgi dwójki: 1, 2, 4, 8, 16 itd - jest dobrze. Jeśli na wejściu by było 1000 0000, to pierwsze przesunięcie i ustawienie da wynik 1100 0000, drugie przesunięcie da wynik 1111 0000, trzecie przesunięcie 1111 1111 - dla 8 bitów wystarczą te 3 operacje, przesuwanie o 8 da wartość zero a więc nic nie zmieni.
  • Poziom 43  
    A... Bo to operuje na obrobionych wcześniej danych. Myślałem że wpisy będą z kolejno przesuwanych wejściowych wartości i wtedy trzeba by przesuwać o 1, 2, 3, 4, 5... .
  • Poziom 42  
    a może tak?


    Code:
    v=0b00110010;
    

    wynik = (1<<( v>=128?1:0) )|(1<<( v>=64?1:0) )|(1<<( v>=32?1:0) )|(1<<( v>=16?1:0) )|(1<<( v>=8?1:0) )|(1<<( v>=4?1:0) )|(1<<( v>=2?1:0) )|(1<<( v>=1?1:0) );


    wynik będzie równy 0b00111111 ;)

    czyli działanie w jednej linijce
  • Poziom 43  
    Ale tam są instrukcje warunkowe.
  • Poziom 42  
    atom1477 napisał:
    Ale tam są instrukcje warunkowe.


    aaa tam IF'y ;) .... ale nie w takiej postaci o jakiej pisał autor - tzn nie ma typowych instrukcji IF - przecież a chyba o nie chodziło autorowi (tak mi się wydaje)
  • Poziom 43  
    mirekk36 napisał:
    atom1477 napisał:
    Ale tam są instrukcje warunkowe.


    aaa tam IF'y ;) .... ale nie w takiej postaci o jakiej pisał autor - tzn nie ma typowych instrukcji IF - przecież a chyba o nie chodziło autorowi (tak mi się wydaje)


    Gdzie napisałem „IFy”???
    Ale autor owszem napisał i to był jego błąd :D
  • Poziom 34  
    W zasadzie to co jest oczekiwane można zapisać w jednej linijce tak:
    Code:
    v = v | (v >> 1) | (v >> 2) | (v >> 3) | (v >> 4) | (v >> 5) | (v >> 6) | (v >> 7);

    czyli jeśli dany bit jest ustawiony, to wszystkie na prawo też mają zostać ustawione. Trochę niewygodny zapis, ale można go przepisać wykorzystując własność przesunięcia:
    Code:
    v = v | (v >> 1) | (v >> 2) | (v >> 3)   |   (v >> 4) | ((v >> 1) >> 4) | ((v >> 2) >> 4) | ((v >> 3) >> 4);

    Przesuwanie względem operacji bitowych jest rozdzielne:
    Code:
    v = v | (v >> 1) | (v >> 2) | (v >> 3)   |   (( v | (v >> 1) | (v >> 2) | (v >> 3) ) >> 4);

    Wyrażenie wewnętrzne powtarza się, a więc można to rozbić:
    Code:
    v = v | (v >> 1) | (v >> 2) | (v >> 3);
    
    v = v | (v >> 4);

    Dalej rozpisując przesunięcia i przepisując
    Code:
    v = v | (v >> 1)   |   ( (v | (v >> 1)) >> 2);
    
    v |= (v >> 4);

    Code:
    v = v | (v >> 1);
    
    v |= (v >> 2);
    v |= (v >> 4);

    Code:
    v |= (v >> 1);
    
    v |= (v >> 2);
    v |= (v >> 4);

    Tak więc widać, że jest to najprostsza postać rozwiązania.

    Rozwiązania używające warunków są rozwiązaniami niepraktycznymi (w sensie podanym przez autora: "ilosc operacji potrzebnych do wykonania musi byc stala"), gdyż w większości zostaną skompilowane do instrukcji skoków.
    mirekk36: twoje rozwiązanie jest wyjątkowo długie oraz niepraktyczne - każdy bit rozwiązania jest liczony osobnym warunkiem, kiedy można całość policzyć równolegle. Dodatkowo jest co poprawiać:
    - błędne wartości przy ?: - wszędzie 1 albo 0
    - przesunięcia można wciągnąć do ?: co zniweluje przesunięcia dając same stałe
    - przy okazji powyższego ujawni się błąd dla wartości 0: wszystkie jedynki będą przesuwane w lewo o 0, wynikiem będzie 1 zamiast oczekiwanego 0.
  • Poziom 42  
    BoskiDialer napisał:
    Tak więc widać, że jest to najprostsza postać rozwiązania.

    nie będę się licytował która jest najprostsza czy najlepsza czy jaka tam jeszcze i wcale nie miałem zamiaru udowadniać że moja propozycja jest lepsza od twojej itp

    BoskiDialer napisał:

    Rozwiązania używające warunków są rozwiązaniami niepraktycznymi (w sensie podanym przez autora), gdyż w większości zostaną skompilowane do instrukcji skoków.

    autor wyraźnie napisał że chodziło mu o if'y - a tu nagle wszyscy się "czepiają" ?: , i co z tego że to warunek? - poza tym czy tu był rozpisany konkurs na super praktyczność i minimalną jakąś objętość kodu ? ;)


    BoskiDialer napisał:

    mirekk36: twoje rozwiązanie jest wyjątkowo długie oraz niepraktyczne - każdy bit rozwiązania jest liczony osobnym warunkiem, kiedy można całość policzyć równolegle. Dodatkowo jest co poprawiać:
    - błędne wartości przy ?: - wszędzie 1 albo 0
    - przesunięcia można wciągnąć do ?: co zniweluje przesunięcia dając same stałe
    - przy okazji powyższego ujawni się błąd dla wartości 0: wszystkie jedynki będą przesuwane w lewo o 0, wynikiem będzie 1 zamiast oczekiwanego 0.



    autor wspominał o uzupełnianiu na prawo jedynek od pierwszego ustawionego bitu - więc nie widzę sensu wspominania o możliwości wystąpienia błędu dla wartości v=0 bo to nie ma sensu zgodnie z założeniami ;)

    poza tym chodziło mi tylko o pokazanie samej koncepcji takiego rozwiązania, a można to tak jak mówisz jeszcze poprawiać wg twoich cennych wskazówek albo zrobić całkiem inaczej jeszcze?

    ---------------------------------

    reasumując - oczywiście, że pod względem praktycznym, objętościowym (tzn ilości kodu) i koncepcyjnym wygrywa twój sposób BoskiDialer ;) - jeśli mamy to traktować jako konkurs a nie jako wskazanie kilku alternatywnych rozwiązań już nie ważne lepszych czy gorszych ale pokazujących możliwość zrobienia w języku C (fajnym języku) - takiego zadania w prostszy sposób bez budowania pętli i warunków IF
  • Poziom 34  
    Nigdzie nie mówiłem o "lepszości" rozwiązania jednego od drugiego, tylko o prostocie.
    Co do czepiania się ?: - chodzi o to, że w większości zostanie to skompilowane do instrukcji skoku co daje zmienny czas wykonywania, kiedy autor napisał "ilosc operacji potrzebnych do wykonania musi byc stala". If'y zostały wyszczególnione, ale mimo to ?: też odpada ze względu na bardziej ogólny warunek (stałość czasu).

    Wartość 1 dla przypadku v=0 jest nadinterpretacją, autor napisał, że w wyniku mają być ustawione: bit najwyższy oraz wszystkie na prawo. W wyniku nie można ustawić bitu 0, gdyż nie był on ustawiony ani na lewo od niego nie było nic ustawionego - wynik powinien być równy 0, mimo że nie zaznaczono tego jawnie.

    Co do "cennych" wskazówek:
    Code:
    wynik = (1<<( v>=128?1:0) )|(1<<( v>=64?1:0) )|(1<<( v>=32?1:0) )|(1<<( v>=16?1:0) )|(1<<( v>=8?1:0) )|(1<<( v>=4?1:0) )|(1<<( v>=2?1:0) )|(1<<( v>=1?1:0) );

    Wciągając przesunięcia pod ?:, poprawiając wartości przesunięć, zamieniając przesunięcia na stałe oraz poprawiając przypadek v=0 można uzyskać:
    Code:
    wynik = ( v>=128?128:0 )|( v>=64?64:0 )|( v>=32?32:0 )|( v>=16?16:0 )|( v>=8?8:0 )|( v>=4?4:0 )|( v>=2?2:0 )|( v>=1?1:0 );

    dalej można zauważyć, że v>=128 jest spełniony tylko wtedy, kiedy najwyższy bit jest ustawiony: ( v>=128?128:0 ) -> ( v & 0x80 )
    v>=64 jest spełnione tylko wtedy, kiedy co najmniej jeden z dwóch najwyższych bitów jest ustawiony: ( v>=64?64:0 ) -> (v|(v>>1)) & 0x40 itd.. uzyska się:
    Code:

    wynik =
       ( v & 0x80 ) |
       ( (v|(v>>1)) & 0x40 ) |
       ( (v|(v>>1)|(v>>2)) & 0x20 ) |
       ( (v|(v>>1)|(v>>2)|(v>>3)) & 0x10 ) |
       ( (v|(v>>1)|(v>>2)|(v>>3)|(v>>4)) & 0x08 ) |
       ( (v|(v>>1)|(v>>2)|(v>>3)|(v>>4)|(v>>5)) & 0x04 ) |
       ( (v|(v>>1)|(v>>2)|(v>>3)|(v>>4)|(v>>5)|(v>>6)) & 0x02 ) |
       ( (v|(v>>1)|(v>>2)|(v>>3)|(v>>4)|(v>>5)|(v>>6)|(v>>7)) & 0x01 );

    Jednak to z rozdzielności operacji na bitach można zapisać jako:
    Code:
    wynik =
    
       ( v & 0x80 ) |
       ( (v) & 0x40 ) | ( (v>>1) & 0x40 ) |
       ( (v) & 0x20 ) | ( (v>>1) & 0x20 ) | ( (v>>2) & 0x20 ) |
       ( (v) & 0x10 ) | ( (v>>1) & 0x10 ) | ( (v>>2) & 0x10 ) | ( (v>>3) & 0x10 ) |
       ( (v) & 0x08 ) | ( (v>>1) & 0x08 ) | ( (v>>2) & 0x08 ) | ( (v>>3) & 0x08 ) | ( (v>>4) & 0x08 ) |
       ( (v) & 0x04 ) | ( (v>>1) & 0x04 ) | ( (v>>2) & 0x04 ) | ( (v>>3) & 0x04 ) | ( (v>>4) & 0x04 ) | ( (v>>5) & 0x04 ) |
       ( (v) & 0x02 ) | ( (v>>1) & 0x02 ) | ( (v>>2) & 0x02 ) | ( (v>>3) & 0x02 ) | ( (v>>4) & 0x02 ) | ( (v>>5) & 0x02 ) | ( (v>>6) & 0x02 ) |
       ( (v) & 0x01 ) | ( (v>>1) & 0x01 ) | ( (v>>2) & 0x01 ) | ( (v>>3) & 0x01 ) | ( (v>>4) & 0x01 ) | ( (v>>5) & 0x01 ) | ( (v>>6) & 0x01 ) | ( (v>>7) & 0x01 );

    Po przegrupowaniu i połączeniu:
    Code:
    wynik = ( (v) & 0xFF ) | ( (v>>1) & 0x7F ) | ( (v>>2) & 0x3F ) | ( (v>>3) & 0x1F ) | ( (v>>4) & 0x0F ) | ( (v>>5) & 0x07 ) | ( (v>>6) & 0x03 ) | ( (v>>7) & 0x01 );

    Ze względu na zakres wartości zmiennej v normalnie jak i po przesunięciach, koniunkcje poznikają dając:
    Code:
    wynik = v | (v>>1) | (v>>2) | (v>>3) | (v>>4) | (v>>5) | (v>>6) | (v>>7);

    Co jest znaną już postacią.

    Reasumując: Wiele rozwiązań daje ten sam wynik, niektóre używają warunków, inne nie - czasem warto się pogłowić aby zoptymalizować kod, na przykład bez używania warunków.
  • Poziom 42  
    BoskiDialer napisał:
    - czasem warto się pogłowić aby zoptymalizować kod, na przykład bez używania warunków.


    pewnie, że tak ;) ja już od dawna lubię patrzeć na twoje optymalizacji kodu w C
  • Poziom 43  
    W życiu bym się nie spodziewał że tak prostą rzecz można w tak skomplikowany sposób zoptymalizować ;)
    Chyba BoskiDialer będzie niedługo miał co robić bo mam trochę rzeczy w C do zoptymalizowania ;)
  • Poziom 27  
    Jesli chodzi o ify - chodzilo mi o jakiekolwiek instrukcje warunkowe ktore moga spowodowac brak stalosci czasu wykonywania. Aktualnie przy uzyciu

    v |= (v >> 1);
    v |= (v >> 2);
    v |= (v >> 4);

    zdazaja mi sie bledy(czasami) przy wartosci okolo 0(w sumie nie jestem w stanie powiedziec czy tylko - wyglada na to jakby przy "szpilkach") -> na wyjsciu pojawia mi sie 00011111(i to tez nie na stale). Jednak podejrzewam że to wina hardware-u.(jednak co ciekawe w fazie testow gdzie przeksztalcenie bajtu bylo na if-ach problem nie wystepowal) Bede jeszcze nad tym pracowal.

    Ogolnie ukad pracuje jako wskaznik wysterowania(logarytmiczny). Po skonczeniu zamieszcze efekty. Jesli ktos ma mniej zlozony algorytm -czekam. Jednak aktualnie za najbardziej odpowiadajacy moim oczekiwania jest wlasnie kolegi Boskiego:)
  • Poziom 43  
    Ten program nie może generować błędów.
    Jeżeli masz błędy to z innych powodów.
    Tak czułem że to do wskaźnika wysterowania.
  • Poziom 27  
    Witam. Wklejam wam kod. Moze pomozecie mi rozszyfrowac co jest nie tak ze czasami mi sie pojawia na wyjsciu 00011111.(przy impulsach). Narazie testowalem jeden kanal - ADC1




    Code:


    /* VUmeter */
    #define F_CPU 8000000L            /* Częstotliwość kwarcu */
    #include <avr/io.h>
    #include <util/delay.h>   
    int main(void)
    {
       DDRB=0b11111111;//lewy
       DDRD=0b11111111;//prawy
       #define kan1 PORTB
       #define kan2 PORTD
       unsigned char reg1=0,reg2=0;
       ADMUX=0b11100001;
       ADCSRA=0b11000000;
       while(ADCSRA & 0b0100000);//czekaj puki konwersja sie zakonczy
       reg2=ADCH;
       while(1)
       {
          ADMUX=0b11100000;//wejscie 0
          ADCSRA=0b11000000;//start
          //kan2=reg2;
          reg2 |= (reg2 >> 1);
          reg2 |= (reg2 >> 2);
          reg2 |= (reg2 >> 4);
          kan2=reg2;
          while((ADCSRA & 0b0100000)==0b0100000);//czekaj puki konwersja sie zakonczy
          reg1=ADCH;
          ADMUX=0b11100001;//wejscie 1
          ADCSRA=0b11000000;//start
          reg1 |= (reg1 >> 1);
          reg1 |= (reg1 >> 2);
          reg1 |= (reg1 >> 4);
          kan1=reg1;
          while((ADCSRA & 0b0100000)==0b0100000);      //czekaj puki konwersja sie zakonczy
          reg2=ADCH;
       }
    }




    fusy: hfuse:0xD9 lfuse:0x24
  • Pomocny post
    Poziom 43  
    Cytat:
    while(ADCSRA & 0b0100000);//czekaj puki konwersja sie zakonczy

    Brakuje jednego zera.

    Powinno być:
    Cytat:
    while(ADCSRA & 0b01000000);//czekaj puki konwersja sie zakonczy


    Chociaż że wiem czy akurat tego zera brakuje. Bo może tego:
    Cytat:
    while(ADCSRA & 0b01000000);//czekaj puki konwersja sie zakonczy

    ;)

    Dodano po 3 [minuty]:

    I tak samo w tych dwóch kolejnych pętlach while.
  • Poziom 27  
    Pomoglo. na ifach czas konwersji musial byc krotszy niz wykonanie petli i blad sie nie pojawial. dzieki. swoja droga dziwne ze kompilator nie wywalil nawet warninga..(avr-gcc). Myslalem ze trzeba podawac cala postac bitowa
  • Poziom 42  
    cikol napisał:
    swoja droga dziwne ze kompilator nie wywalil nawet warninga..(avr-gcc). Myslalem ze trzeba podawac cala postac bitowa


    0b100

    też jest całą postacią bitową tyle że kompilator uzupełni sobie zera od lewej

    0b00000100
  • Poziom 27  
    mam problem z przesluchem pomiedzy kanalami. Czy mozliwe ze to dlatego że pojednej konwersji rozpoczynam odrazu druga? calosc smiga na wewnetrznych 8mhz. Przesluch jest taki ze przy zapalonych 4 diodach w jednym kanale zaczyna sie swiecic pierwsza w drugim. dla 5 diod w jednym swieca sie juz dwie w drugim
  • Poziom 43  
    To prawie niemożliwe. Masz raczej jakieś upływności na PCB.
  • Poziom 27  
    Calosc jest na pająku. Jak mialem na plytce testowej to dzialo sie to samo. Co do schematu ADC: prosty dzielnik napiecia z dioda odcinajaca skladowe ujemne.
  • Poziom 43  
    A miałem napisać: "upływności na PCB albo w pająku" ;)
    Ta dioda może coś przeszkadzać. Pokaż ten schemat.
  • Poziom 43  
    Podaj wartości elementów. Może są za małe wartości rezystorów i prąd obcinany przez diodę w jednym kanale przesuwa poziom masy (w układzie pewnie po drodze są jeszcze kondensatory elektrolityczne). W ogóle to dziwnie to podłączyłeś. Jak wyznaczasz głośność? Konkretnie.