odwrotnosc przesuniecia bitowego w lewo

0

Mamy liczbę 256.

2 << 7 = 256.
To jest oczywiste.
Ale jak dojść do tego że X równa się 7, przy 256 = 2 << X ?
Czyli mamy daną liczbę 256 i chcę wiedzieć jakie przesunięcie dwójki daję tą liczbę.
Można dać to w pętli, ale mi bardzo zależy żeby tak nie było (problem na mikroprocesory).

Alternatywnie można spojrzeć na to tak:
256 - 1 = 01111111b
Czyli liczba jedynek równa jest siedem. Ale chyba nie ma w C w standardowej bibliotece funkcji na ilość jedynek ?

0

Hm, logarytm?

0

w sumie fakt, ale myślałem ze da się to zapisać "bez obliczen"

            int x = 255;
            int wynik = 0;
            while (x > 1)
            {
                x >>= 1;
                ++wynik;

            }
0

2 << 7 = 256, gdyz 1<<8 = 256.

na poziomie nizej od C++, w assemblerze, sa rozkazy wyszukiwania pierwszej/ostatniej jedynki/zera w liczbie. majac liczbe postacji 2^n (np.: 256 = ..000100000000) traktujesz ja takim rozkazem szukania jedynki i dostajesz w odpowiedzi np. 8 - tak wiec jest to banalne.
maly problem zaczyna sie, gdy liczba przesuwana nie jest jedynka, a 2^m, czyli np. 8 zostalo przesuniete o 5. wynik = tez 256. 8 to 1<<3. 256 to 1<<8. 256 potraktowane szukaniem jedynki da X, 8 potraktowane szukaniem jedynki da Y, wiec aby 8 << (X-Y) = 256.
wiekszy problem masz, jezeli chcesz dowiedziec sie o ile przesunieto liczbe, ktora NIE jest postaci 2^m, np takie 2640 to 165 << 4. dostajesz liczbe: 101001010000 oraz 10100101 -- ile wynosilo przesuniecie? szukasz w obu jedynki od prawej - tu dostajesz 4 a tam zero. odpowiedz: 4-0=4, liczbe przesunieto o 4. łatwe? a gdyby wejsciowe liczby konczyly sie zerem. 1010010100000 i 101001010. szukasz jedynki: 5 i 1, czyli 5-1=4. hej, zgadza sie. chyba jednak latwe?

nie, nie calkiem latwe, gdyz sa problemy:

  • masz liczbe 0000000000 oraz druga liczbe 0000000000. o ile przesuniecie?
  • masz liczbe 0111110000 oraz druga liczbe 0000001110. o ile przesuniecie?
  • masz liczbe 1111111111 oraz druga liczbe 0000000001. o ile przesuniecie?
    itp. rozwiazanie, o ile istnieje, znajdz sam.

w C++ niestety standardowo chyba nieistnieje sposob zeby dobrac sie do tychze operacji, ale w wiekszosci bibliotek standardowych sa dorzucone krotkie funkcje systemowe ktore pozwalaja Ci skorzystac z szukania zera/jedynki w liczbie. ciezko sie czasem do nich dokopac, ale pamietam ze np. w crt visuala sa takowe.

mozna tez napisac je z palca - patrz na przyklad
http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive
przyczym zanim skopiujesz zerknij do
http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSet64
i raczej "skopiuj" to

1 użytkowników online, w tym zalogowanych: 0, gości: 1