Maskowanie oraz operacje na bitach

Jojnosn

2016-01-26 21:41

Jojnosn2016-01-26 21:41

Witam !

Mam problem z programem. Potrzebuje pomocy - głównie chodzi mi o pierwszą funkcję, za która zupełnie nie wiem jak mam się zabrać, żeby uzyskać właściwy format maski.

Napisz program, który będzie składał się z 3 funkcji:

Funkcja tworząca maskę, maskowanie(int N, int M, int P)
przyjmuje N - ilość jedynek, M - ile zer, P - ile powtórzeń.
Przykładowe wywołania:
maskowanie(1,2,1) -> wynik bitowo -> 100
maskowanie(2,3,3) -> wynik bitowo -> 110001100011000
Funkcja sprawdzająca, który jest najwyższy bit, licząc od prawej strony.
jeśli liczba = 15 (1111), to
ktoryBit(liczba) -> zwróci -> 4
jeśli liczba = 64 (1000000), to
ktoryBit(liczba) -> zwróci -> 7
Można to osiągnąć np. przesuwaniem liczby w prawo i sprawdzaniem odpowiedniego warunku.
Funkcje negująca i ustawiająca. Przyjmuje parametr, np. typu int (0-neguj, 1-ustaw).

Ogólnie program ma działać w ten sposób, że wczytujemy z konsoli liczbę. Maskujemy od najwyższego bitu w prawo (Najwyższy bit maski pokrywa się z najwyższym bitem liczby).
Jeśli najwyższy bit jest mniejszy od długości maski (np. liczba = 64, czyli ktoryBit() zwraca 7, a maska ma długość 8) - to wyświetlamy komunikat i nic nie robimy.

_13th_Dragon

2016-01-26 22:09

_13th_Dragon2016-01-26 22:09

Rejestracja:ponad 19 lat
Ostatnio:3 miesiące

Ta, straszna skomplikowana funkcja, przeczytać rozdział operacje bitowe i świczyć:

Kopiuj

uint64_t maskowanie(unsigned N,unsigned M,unsigned P)
  {
   uint64_t ret=0,msk=1;
   msk=((msk<<N)-1)<<M;
   for(N+=M;P--;ret|=msk) msk<<=N;
   return ret;
  }

Endrju

2016-01-26 22:30

Endrju2016-01-26 22:30

Rejestracja:około 22 lata
Ostatnio:ponad rok

Ponieważ jesteś leniwy dam Ci rozwiązanie drugiego zadania, które do niczego Ci się nie przyda. Ale jest ciekawe.

Otóż na x86 jest taka instrukcja bsr czyli bit scan reverse. Zwraca ona indeks najwyższego ustawionego bitu. (Jeżeli nie ma żadnych bitów, to jest undefined) Oczywiście ludzie liczą bity od zera, ale wymaganie w zadaniu jest, żeby liczyć od 1. Czyli 0 będzie oznaczało, że nie ma żadnych bitów.

Kopiuj

inline std::size_t ktoryBitHeHe(std::uint32_t value) {
  if (value > 0) {
  	return _bit_scan_reverse(value) + 1;
  } else {
  	return 0;
  }
}

http://ideone.com/Cgh0r9

edytowany 1x, ostatnio: Endrju 2016-01-26 22:31

Jojnosn

2016-01-26 23:12

Jojnosn2016-01-26 23:12

Dziękuje Panowie !
Jeśli jeszcze można - Zastanawia mnie teraz druga funkcja, do której jednak niechciałbym uzywać wyżej podanej opcji.
Z jakiego warunku powinienem skorzystać przy przesuwaniu bitów w prawo?

_13th_Dragon

2016-01-26 23:34

_13th_Dragon2016-01-26 23:34

Rejestracja:ponad 19 lat
Ostatnio:3 miesiące

Warunku przy przesuwaniu?
Może zacznij od przeczytania pierwszych kilku rozdziałów byle kursu, przynajmniej po to by móc zadać sensowne pytanie.

pingwindyktator

2016-01-27 07:22

pingwindyktator2016-01-27 07:22

Rejestracja:ponad 12 lat
Ostatnio:26 dni
Lokalizacja:Kraków
Postów:1055

Kopiuj

std::size_t ktoryBitHaHa(std::uint32_t value) {
  uint32_t result = 0;
  while (value > 0) {
    value >>= 1;
    ++result;
  }
  return result;
}

edytowany 1x, ostatnio: pingwindyktator 2016-01-27 07:28

_13th_Dragon 2016-01-27 07:27

a po kiego ci ten if?

pingwindyktator 2016-01-27 07:28

fakt

_13th_Dragon

2016-01-27 07:35

_13th_Dragon2016-01-27 07:35

Rejestracja:ponad 19 lat
Ostatnio:3 miesiące

Zastanawiam się czy to nie będzie średnio szybsze:

Kopiuj

std::size_t ktoryBitMath(std::uint32_t value) { return (std::size_t)std::log2((double)value); }

pingwindyktator 2016-01-27 08:04

Mój niezawodny framework twierdzi, że na -O3 mój kod jest 2x szybszy, chociaż na -Ofast Twój jest dużo dużo szybszy, ale to nie fair, bo masz tam -ffast-math ;D

_13th_Dragon 2016-01-27 08:38

Dla jakich liczb sprawdzałeś? Pamiętaj że dla uint32_t średnio ma się doliczyć 31 bitów.

pingwindyktator 2016-01-27 12:23

Testowałem oczywiście dla liczb w odpowiednim przedziale, to znaczy w funkcji losującej jest

if (std::is_integral&lt;T&gt;::value &amp;&amp; (std::numeric_limits&lt;T&gt;::max() &lt; (size_t(1) &lt;&lt; (length_in_bytes*8)))) throw std::range_error(&quot;given length in bytes won't fill into specified type&quot;);

_13th_Dragon 2016-01-27 12:50

sprawdź zwyczajnie dla liczby uint32_t value=1UL<<31; kilkakrotnie.

pingwindyktator 2016-01-27 13:02

To na -O3 mi to "kilkukrotnie" wywali kompilator. Ale okej, sprawdzę później.

Liczba odpowiedzi na stronę

Treść *

Treść

Podgląd

Kliknij, aby dodać treść...

Kliknij, aby dodać załącznik lub wklej ze schowka.

Instrukcja obsługi Markdown

Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj underline.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, , , <kbd>, <del>, , <dfn>, <pre>, <blockquote>, <hr/>, ,  oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H2O i m2 otrzymasz: H₂O i m².

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript document.write('Hello World'); ```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

Alt+L - zaznaczenie całej linii
Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

Ctrl+Enter - dodaj post
⌘+Enter - dodaj post (MacOS)

Maskowanie oraz operacje na bitach

Jojnosn

_13th_Dragon

Endrju

Jojnosn

_13th_Dragon

pingwindyktator

_13th_Dragon

Smileys & People

Animals & Nature

Food & Drink

Travel & Places

Activities

Objects

Symbols

Typografia

Linki

Wewnętrzne odnośniki

Wspomnienia użytkowników

Znaczniki HTML

Skróty klawiszowe

Indeks górny oraz dolny

Składnia Tex

Kod źródłowy

Krótkie fragmenty kodu

Kod wielolinijkowy

Tabelki

Lista uporządkowana i nieuporządkowana

Składnia Markdown

Skróty klawiszowe

Data Scientist

Programista Systemów Automatyki - PCS7

Java Developer

Junior Python Developer

Praca dla programistów

Forum dyskusyjne

Sprawy administracyjne

O nas

Skontaktuj się z nami