Login lub e-mail Hasło   

Optymalizacja operacji arytmetycznych

Trochę o optymalizacji operacji arytmetycznych w matematyce, tak aby liczyć szybciej i łatwiej.
Wyświetlenia: 1.865 Zamieszczono 06/09/2007
Nie raz juz na forum spotkalem sie z pewnymi niejanosciami jesli chodzi o zastepowanie pewnych operacji arytmetycznych operacjami bitowymi dlatego postaram sie to tutaj krotko wyjasnic kiedy je mozna stosowac:

zapis 2^x jakby ktos nie wiedzial jest to nic innego jak 2 do potegi x

Ponizsze dzialania mozna stosowac wylacznie dla liczb dodatnich

1. Mnozenie(*) i dzielenie(/)

a) dzialanie a * b mozna zastapic poprzez szybsza operacje przesuniecia bitowego w lewo: a << x jezeli b = 2^x.
Wiadomo ze mnozenie jest przemienne takze jezeli a = 2^x dzialanie mozna zastapic przez: b << x
Przykladowo:
w = a * 32

poniewaz liczbe 32 mozna zapisac jako 2^5 powyzsza operacje mozna zapisac uzywajac operacji bitowej <<:
w = a << 5

b) dzialanie a / b mozna zastapic poprzez szybsza operacje przesuniecia bitowego w prawo: a >> x jezeli b = 2^x
Przykladowo:
w = a / 8

poniewaz liczbe 8 mozna zapisac jako 2^3 powyzsza operacje mozna zapisac uzywajac operacji bitowej >>:
w = a >> 3

2. Operacja modulo(%)
dzialanie a % b mozna zastapic przez operacje bitowa AND: a & (b-1) jezeli b = 2^x
Przykladowo:
w = a % 4

poniewaz 4 mozna zapisac jako 2^2 powyzsze dzialanie mozna zapisac uzywajac operacji bitowej &:
w = a & 2


Na koniec moze nie dzialanie arytmetyczne ale znana kazdemu a jak nie na pewno sie przyda optymalizacja tzw. operacji swap z pol. zamiana uzywajac operacji bitowej XOR(^)
zamiast:
w C:
void swap(int *a, int *b)
{
int x = *a;
*a = *b;
*b = x;
}

w C++:
void swap(int &a, int &b)
{
int x = a;
a = b;
b = x;
}

mozna to wykonac bez dodatkowej zmiennej uzywajac wlasciwosci operatora XOR:
w C:
void swap(int *a, int *b)
{
*a ^= *b;
*b ^= *a;
*a ^= *b;
}


w C++

void swap(int &a, int &b)
{
a ^= b;
b ^= a;
a ^= b;
}

Źródło: 4programmers.net. Treść udostępniona na zasadach licencji Creative Commons Attribution

Podobne artykuły


21
komentarze: 13 | wyświetlenia: 13702
16
komentarze: 5 | wyświetlenia: 8986
9
komentarze: 0 | wyświetlenia: 2765
49
komentarze: 18 | wyświetlenia: 64899
37
komentarze: 9 | wyświetlenia: 28452
9
komentarze: 1 | wyświetlenia: 35530
17
komentarze: 4 | wyświetlenia: 13913
15
komentarze: 5 | wyświetlenia: 32707
13
komentarze: 2 | wyświetlenia: 22938
12
komentarze: 2 | wyświetlenia: 18486
12
komentarze: 3 | wyświetlenia: 29735
11
komentarze: 1 | wyświetlenia: 10418
11
komentarze: 1 | wyświetlenia: 86331
 
Autor
Dodał do zasobów: Rafal Kinde
Artykuł



Drobne rzeczy, ale po nich właśnie odróżnisz profesjonalistę od amatora.

Czasem porządne przygotowanie akademickie jest potrzebne...



Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska