dlaczego to działa? (znalezienie liczby nieparzystej w C++)

Question

for (unsigned int i = 1; i <= 100; i++) { 
    if (i & 0x00000001) { 
     std::cout << i<<","; 
    } 
} 

dlaczego (i jak): if(i & 0x00000001) wymyślić liczbę nieparzystą?

Answer 1

0x00000001 jest 1 w binarnym, chociaż on napisany w systemie szesnastkowym (base-16) notacja. To jest część 0x.

& jest bitowym operatorem "AND", który służy do wykonywania cyfrowej (bitowej) manipulacji.

i & 1 konwertuje wszystkie cyfry binarne i na zero, z wyjątkiem ostatniego.

Łatwo przekonwertować wynikową liczbę 1-bitową na wartość logiczną, do oceny za pomocą instrukcji if.

Poniższa tabela przedstawia ostatnie 16 cyfr binarnych i, i co się z nimi dzieje.

i: i in binary:  i & 1 in binary: convert to boolean 
---- ------------------- ------------------- --------------------- 
1 0000000000000001 0000000000000001 true 
2 0000000000000010 0000000000000000 false 
3 0000000000000011 0000000000000001 true 
4 0000000000000100 0000000000000000 false 
5 0000000000000101 0000000000000001 true 
6 0000000000000110 0000000000000000 false 
7 0000000000000111 0000000000000001 true 
8 0000000000001000 0000000000000000 false 
... ...     ...     ... 
99 0000000001100011 0000000000000001 true 
100 0000000001100100 0000000000000000 false 

Answer 2

Używa bitowego operatora "i" do maskowania wszystkich oprócz ostatniego. Jeśli ostatni bit ma wartość 1, liczba jest nieparzysta. Czy to wystarczające wytłumaczenie?

Answer 3

Kiedy patrzymy na liczby w bazie 10, łatwo jest stwierdzić, czy liczba jest podzielna przez 10: ma 0 w ostatniej pozycji. Powyższy kod również wskazuje cyfrę w ostatniej pozycji, ale w bazie 2. Jeśli jest niezerowa, numer to , a nie podzielny przez 2.

Answer 4

Maskuje ostatni bit. Jeśli spojrzysz na każde miejsce w reprezentacji binarnej liczby (..., 256, 128, 64, 32, 16, 8, 4, 2 i 1), zauważysz, że tylko jedno miejsce jest dziwne. Wszystkie pozostałe miejsca mają wartość parzystą niezależnie od tego, czy bity są ustawiane czy czyszczone (zero jest równe). Dodanie liczb parzystych zawsze da równą liczbę. Tylko to ostatnie miejsce określa parzystość liczby. Część i & &0x00000001 po prostu izoluje to ostatnie miejsce.

Answer 5

Dokonujesz porównania bitowego. Jeśli bit0 AND bit0 ma wartość 1, to bit odpowiedzi = 1.

Widząc, że & 0x00000001 wynosi 1, wszelkie liczby z tym bitem są nieparzyste.

0x00000001 = 1 
0x00000010 = 2 
0x00000011 = 3 
etc. 

Tak więc, jeśli robisz bitowego AND

00000001 AND 
00000001 = 
00000001 (same as true) 

00000010 AND 
00000001 = 
00000000 (same as false) 

00000011 AND 
00000001 = 
00000001 (same as true) 

etc 

Answer 6

Numery nieparzyste to wszystkie liczby w formularzu (2 * n + 1), gdzie n jest dowolną liczbą całkowitą (-2, -1,0,1 ...). Aby znaleźć nieparzystą liczbę, musisz sprawdzić, czy liczba całkowita, z którą pracujesz, ma "+1". Gdy jest zapisany jako liczba całkowita bez znaku, liczba może być wyrażona jako suma mocy 2: 2^0 + 2^1 + 2^2 + 2^4 itd. Wersja binarna liczby całkowitej bez znaku wygląda jak mapa prawdy rodzajów: dla każdego miejsca istnieje "1" w liczbie binarnej, dodaj tę moc dwóch do liczby. Tak więc, jeśli zaczynasz od prawej najbardziej cyfrowej reprezentacji binarnej liczby całkowitej bez znaku i przesuń w lewo, każda cyfra reprezentuje potęgę dwóch. Jeśli cyfra wynosi 1, dodajesz potęgę 2 do sumy roboczej i po osiągnięciu końca liczby binarnej.

sposób: 10001110b można przekształcić całkowitą poprzez zsumowanie potęgi dwójki:

skrajnie prawe: 2^1 + 2^2 + 2^3 + 2^7: LEFTMOST = 141

lewą jest to, że cyfra z prawej strony reprezentuje 2^0. Jest to zawsze 1. Wszystkie pozostałe cyfry oznaczają liczby parzyste. Zatem pod względem liczb nieparzystych trzeba znaleźć "+1". Odpowiada to cyfrze z prawej strony. Wszystkie pozostałe cyfry oznaczają liczby w formularzu "2 * n". Dlatego też, aby ustalić, czy liczba tego formatu (liczba całkowita bez znaku) jest nieparzysta, trzeba tylko sprawdzić, czy prawy najbardziej bit jest "1".

Operacja wykonywana na niepodpisanej liczbie całkowitej jest logiczną operacją AND. Cokolwiek AND ma wartość 0, oznacza 0, a 1 AND oznacza 1 oznacza 1. Operacja spowoduje, że wszystkie cyfry binarne w niezerowej liczbie całkowitej będą równe 0, z wyjątkiem binarnej cyfry reprezentującej 2^0 (co oznacza 1). Tak więc całkowita liczba binarna bez znaku sprowadza się do 0x00000001, jeśli jest nieparzysta, a 0x00000000, jeśli jest parzysta.

Uwaga: Kiedy piszę 0x00000000, "0x" oznacza, że ​​jest to format szesnastkowy. Każde "0" reprezentuje cztery bity. Więc 0x00 jest szesnastkowy dla 00000000b rozpisane w systemie binarnym, wynikające z możliwych liczba całkowita bez znaku binarne reprezentacje po AND'ing na liczbę całkowitą bez znaku są:

00000000000000000000000000000000b == 0 i 00000000000000000000000000000001b == 1

Answer 7

Zanim powiem co następuje, najpierw powiem, że prawie zawsze używam testu bitowego, aby określić, czy int jest nieparzyste, czy nieparzyste.

Ale, ściśle rzecz biorąc, powinieneś użyć (i % 2) lub ((i % 2) != 0), aby ustalić, czy i jest nieparzyste. To zadziała niezależnie od reprezentacji liczb ujemnych, podczas gdy na maszynie z jednym uzupełnieniem (-3 & 0x01) zwróci zero (wynik fałszywy), chociaż oczywiście jest dziwne.

Zdaję sobie sprawę, że machiens używające czegoś innego niż dopełnienie dwójki do reprezentowania liczby ujemnej są bardzo, bardzo rzadkie w dzisiejszych czasach, ale prawdą jest również, że kompilatory w dzisiejszych czasach będą powszechnie kompilować (i % 2) do testu bitowego. I pamiętajcie, że zazwyczaj nie stosuję się tutaj do własnych rad, więc może to świadczyć o prawdziwej wartości tej sugestii.

Answer 8

bitowego AND operator następująco tej tabeli prawdy dla każdego bitu:
0 = 0
1 = 0
0 = 0
1 = 1

Rejestracja komputerów praca z liczbami w bazie 2 i każdy bit reprezentuje potęgę dwóch wartości (1,2,4,8,16 ..),
najmniej znaczący bit reprezentuje jedyną nieparzystą liczbę, bez względu na to, jak duża lub mała jest wartość, oraz niezależnie od tego, czy jest podpisany, czy niepodpisany. Ponieważ wynikowy bit jest ustawiony tylko wtedy, gdy oba operandy mają ustawiony ten bit, wynikiem jest true tylko wtedy, gdy liczba jest nieparzysta.

przykład: 0b1110101 =
(1 * 2^0) + (1 * 2^1) + (0 * 2^2) + (1 * 2^3) +
(0 * 2^4) + (1 * 2^5) + (1 * 2^6) + (1 * 2^7) =
+ 2 + 0 + 8 + 0 + 32 + 64 + 128 = 235
Bez najmniej znaczącego zestawu bitów, wartość wynosiłaby 234, a tym samym parzystą liczbę.

Answer 9

Na przykład, w jaki sposób dokonać binarne równoważny

0 0 0 0 = 0

0 0 0 1 = 1

0 0 1 0 = 2

0 0 1 1 = 3

Więc można zobaczyć na każdej nieparzystej nr. LSB jest zawsze ustawiony, sama sprawdzić :)

Mam nadzieję, że moja odpowiedź jest jasna