Optymalizacja operacji arytmetycznych

Trochę o optymalizacji operacji arytmetycznych w matematyce, tak aby liczyć szybciej i łatwiej.

Trochę o optymalizacji operacji arytmetycznych w matematyce, tak aby liczyć szybciej i łatwiej.

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

Autor: Maker

optymalizacja technologia operacje programowanie arytmetyczne arytmetyka