Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Pojęcie bitu

Operacje bitowe w C++

SPIS TREŚCI
Podrozdziały

Operacje na bitach

W operacjach bitowych biorą udział słówka binarne. Operacje wykonywane są na odpowiadających sobie bitach tych słówek. W języku C++ mamy następujące operacje bitowe:

~ negacja

Operator ~ zmienia wszystkie bity argumentu na przeciwne, czyli wykonuje operację negacji bitów:

~0110 = 1001
C++
// negacja bitów
// (C)2020 mgr Jerzy Wałaszek
// I LO w Tarnowie

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

void itob( unsigned a )
{ 
    for( unsigned m = 8; m > 0; m >>= 1 )
        cout << (( a & m ) ? "1" : "0" );
}

int main( )
{ 
    srand( time( NULL ));

    unsigned x = rand( ) % 16;

    cout << "~";

    itob( x );

    cout << " = ";

    itob( ~x ); // tutaj dokonujemy negacji bitów

    cout << endl;

    return 0;
}
Wynik:
~0010 = 1101

| alternatywa

Operator | wykonuje operację alternatywy nad odpowiadającymi sobie bitami argumentów.

0101 | 0011 = 0111

C++
// alternatywa bitów
// (C)2020 mgr Jerzy Wałaszek
// I LO w Tarnowie

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

void itob ( unsigned a )
{ 
    for( unsigned m = 8; m > 0; m >>= 1 )
        cout << (( a & m ) ? "1" : "0" );
}

int main( )
{ 
    srand( time( NULL ));

    unsigned x = rand ( ) % 16;
    unsigned y = rand ( ) % 16;

    itob( x );

    cout << " | ";

    itob( y );

    cout << " = ";

    itob( x | y ); // tutaj dokonujemy alternatywy bitów

    cout << endl;

    return 0;
}
Wynik:
0110 | 0100 = 0110


& koniunkcja

Operator & wykonuje operację koniunkcji nad odpowiadającymi sobie bitami argumentów.

0110 & 1011 = 0010
C++
// koniunkcja bitów
// (C)2020 mgr Jerzy Wałaszek
// I LO w Tarnowie

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

void itob( unsigned a )
{ 
    for( unsigned m = 8; m > 0; m >>= 1 )
        cout << (( a & m ) ? "1" : "0" );
}

int main( )
{ 
    srand( time( NULL ));

    unsigned x = rand ( ) % 16;
    unsigned y = rand ( ) % 16;

    itob( x );

    cout << " & ";

    itob( y );

    cout << " = ";

    itob( x & y ); // tutaj dokonujemy koniunkcji bitów

    cout << endl;

    return 0;
}
Wynik:
1101 & 0111 = 0101

^ różnica symetryczna / suma modulo 2

Operator ^ wykonuje operację sumy modulo 2 nad odpowiadającymi sobie bitami argumentów.

0111 ^ 1001 = 1110
C++
// suma modulo 2 bitów
// (C)2020 mgr Jerzy Wałaszek
// I LO w Tarnowie

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

void itob( unsigned a ) 
{ 
    for( unsigned m = 8; m > 0; m >>= 1 )
        cout << (( a & m ) ? "1" : "0" );
}

int main( ) 
{ 
    srand( time( NULL ));
  
    unsigned x = rand( ) % 16;
    unsigned y = rand( ) % 16;
    
    itob( x );
    
    cout << " ^ ";
    
    itob( y );
    
    cout << " = ";
    
    itob( x ^ y ); // tutaj dokonujemy sumy symetrycznej bitów
    
    cout << endl;
    
    return 0;
}
Wynik:
0110 ^ 0100 = 0010

Tabelki opisanych powyżej operacji bitowych są następujące:

negacja
 a ~ a
0 1
1 0
alternatywa
 a b a | b
0 0 0
0 1 1
1 0 1
1 1 1
koniunkcja
 a b a & b
0 0 0
0 1 0
1 0 0
1 1 1
suma modulo 2
 a b a ^ b
0 0 0
0 1 1
1 0 1
1 1 0

Uwaga:

W języku C++ istnieją dwie formy operatorów:

  • logiczne (ang. logical) !, || i &&, które traktują swoje argumenty jako wyrażenia logiczne przyjmujące wartości true lub false. Wynikiem jest zawsze wartość logiczna true lub false.
  • bitowe (ang. bitwise) ~, |, & i ^, które traktują swoje argumenty jako słówka binarne i przeprowadzają operację logiczną na odpowiadających sobie bitach w tych słówkach. Wynikiem jest zawsze słówko binarne z bitami ustawionymi zgodnie z definicją danej operacji logicznej.

<<, >> przesunięcia bitowe

Operator >> przesuwa bity lewego argumentu o zadaną prawym argumentem ilość pozycji w prawo. Na przykład:

00111100 >> 2 = 00001111
10000000 >> 3 = 00010000

Bity, które wyjdą poza skrajną prawą pozycję są tracone. Przesunięcie bitów w prawo o 1 pozycję jest równoważne dzieleniu przez dwa. Przesunięcie o n pozycji w prawo jest równoważne dzieleniu przez 2 n. Operacje przesuwu są bardzo szybkie - o wiele szybsze od dzielenia. Jeśli nasz algorytm dużo dzieli przez 2 (lub potęgę 2), to warto się zastanowić, czy zamiast dzielenia, nie lepsza byłaby operacja przesuwu bitów w prawo. Operacja ta jest jednak ograniczona tylko do liczb całkowitych, natomiast operacja dzielenia może operować na dowolnych typach liczbowych.

Operator << przesuwa bity lewego argumentu o zadaną prawym argumentem ilość pozycji w lewo. Na przykład:

00001111 << 3 = 01111000
00000001 << 5 = 00100000

Operacja przesuwu bitów w lewo jest równoważna mnożeniu przez 2. Przesunięcie bitów w lewo o n  pozycji odpowiada pomnożeniu przez 2 n. Przesunięcie bitów jest o wiele szybsze od mnożenia.

Operacje bitowe często służą do modyfikacji zawartości zmiennej. Dlatego język C++ posiada formy skrócone operacji przypisania z modyfikacją :

zamiast stosuje się
a = a | b ; a |= b ;
a = a & b ; a &= b ;
a = a ^ b ; a ^= b ;
a = a >> n ; a >>= n ;
a = a << n ; a <<= n ;

Poniższy program dokonuje szybkiej konwersji wprowadzonej liczby dziesiętnej na jej zapis w systemie binarnym. Zasada działania opiera się na badaniu stanu kolejnych bitów liczby, która wewnętrznie jest przechowywana w postaci binarnej. Badanie polega na wykonywaniu koniunkcji bitowej z maską, w której jest cyklicznie przesuwany bit z pozycji najstarszej na najmłodszą. Wynik koniunkcji informuje nas o stanie badanego bitu.

C++
// przesuw bitów
// (C)2020 mgr Jerzy Wałaszek
// I LO w Tarnowie

#include <iostream>

using namespace std;

int main( )
{ 
    unsigned a,m;

    cin >> a;

    for( m = 2147483648; m > 0; m >>= 1 )
        cout << (( a & m ) ? "1" : "0" );

    cout << endl;

    return 0;
}
Wynik:
68542387
00000100000101011101111110110011
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.