Omówiono ideę algorytmu mini-max i postawiono problem adaptacji jego do prostej gry wieloosobowej (Pędzące żółwie). Zadaniem uczestików jest określenie sposobu wyliczania stanu gry celem wyboru najlepszego ruchu.
Celem zajęć było pokazanie w jaki sposób wiedza o reprezentacji liczb może pomóc w konstrukcji szybszych procedur obliczeniowych. Choć podane przykłady należą do kategorii ,,sztuczek'' programistycznych, to bywają nierzadko stosowane w praktyce wszędzie tam, gdzie szybkość kodu jest cechą nadrzędną. W trakcie zajęć zanalizowano następujące konstrukcje:
- Wybór wartości minimalnej z dwóch liczb bez użycia instrukcji warunkowej
#include
int getMin(int a, int b){
int tab[2] = {a,b};
int i= (a-b) >> 31 & 0x1;
return tab[1-i];
}
int main(void){
int v;
v = getMin(3,-6);
printf("%d",v);
return 0;
}
Przykład działania
UZUPELNIC
- Obliczenie znaku liczby całkowitej
int v; // we want to find the sign of v
int sign; // the result goes here
// CHAR_BIT is the number of bits per byte (normally 8).
sign = -(v < 0); // if v < 0 then -1, else 0.
// or, to avoid branching on CPUs with flag registers (IA32):
sign = -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));
// or, for one less instruction (but not portable):
sign = v >> (sizeof(int) * CHAR_BIT - 1);
Pokażemy na przykładzie działanie wersji
sign = v >> (sizeof(int) * CHAR_BIT - 1);
Dla ułatwienia przyjmujemy, że używamy int-ów 8-bitowch - w konsekwencji wyrażenie
(sizeof(int) * CHAR_BIT - 1)
przyjmuje wartość 7 (sizeof(int) wynosi 1, CHAR_BIT wynosi 8). Zapis >> oznacza przesunięcie bitowe w prawo ze znakiem (bit znaku jest kopiowany na ,,swoje'' miejsce). O tym, że tak jest można się przekonać patrząc na wynik działania następującego programu
#include
int main(void){
int v = -113;
printf("%d %d\n",v,v >> 1);
printf("%d %d\n",v,v >> 2);
printf("%d %d\n",v,v >> 3);
printf("%d %d\n",v,v >> 4);
return 0;
}
wynik:
fulmanp@t500-ubuntu:~/moje/work$ ./a.out
-113 -57
-113 -29
-113 -15
-113 -8
Zmienna v przyjmuje wartość -113, czyli w zapisie U2 wygląda jak poniżej (używamy 8 bitów, ale prawdziwe jest to dla dowolnej ich ilości)
10001111
Przesuwając teraz ten ciąg o jeden bit w prawo otrzymujemy
+-- dopisany bit znaku
|
| +-- bit jest odrzucany
| |
1 1000111 1
a więc pozostaje 11000111 czyli ciąg reprezentujący w kodzie U2 wartość -57.
Przesuwając teraz poprzednio otrzymany ciąg o jeden bit w prawo otrzymujemy
+-- dopisany bit znaku
|
| +-- bit jest odrzucany
| |
1 1100011 1
a więc pozostaje 11100011 czyli ciąg reprezentujący w kodzie U2 wartość -29.
Przesuwając teraz poprzednio otrzymany ciąg o jeden bit w prawo otrzymujemy
+-- dopisany bit znaku
|
| +-- bit jest odrzucany
| |
1 1110001 1
a więc pozostaje 11110001 czyli ciąg reprezentujący w kodzie U2 wartość -15.
Kontynuując to postępowanie 7 razy otrzymamy ciąg 11111111 a więc ciąg reprezentujący w kodzie U2 wartość -1. Tym samym zmienna sign przyjmie wartość -1 dla liczby, która była ujemna. Analogiczne rozumowanie pokazuje, że dla liczby dodatniej zmienna sign przyjmuje wartość 0.
- Sprawdzenie, czy dwie liczby całkowite są przeciwnego znaku
int x, y; // input values to compare signs
bool f = ((x ^ y) < 0); // true iff x and y have opposite signs
Przykład działania.
Jak widać z powyższego kodu, interesuje nas znak wyrażenia (x ^ y). Stosując ogólnie panujacą konwencję używania jako najbardziej znaczącego bitu (najbardziej z lewej strony) wartości 0 dla liczb dodatnich i 1 dla ujemnych otrzymujemy, że operacja XOR (czyli ^) dla dwóch liczb o identycznym znaku a więc dodatnich (kropki oznaczają dowolną wartość bitu)
0.......
0.......
lub ujemnych
1.......
1.......
zawsze zwraca
0.......
Jedynie, gdy jedna z liczb będzie ujemna a druga dodatnia, wynikiem będzie
1.......
a więc liczba ujemna. Stąd, dla liczb o przeciwnych znakach wartość logiczna wyrażenia ((x ^ y) < 0) jest prawdą.
- Obliczenie modułu liczby
int v; // we want to find the absolute value of v
unsigned int r; // the result goes here
int const mask = v >> (sizeof(int) * CHAR_BIT - 1);
r = (v + mask) ^ mask;
Przykład działania
Załóżmy, iż zmienna v przyjmuje wartość -113, czyli w zapisie U2 wygląda jak poniżej (używamy 8 bitów, ale prawdziwe jest to dla dowolnej ich ilości)
10001111
Wykorzystując obserwacje z przykładu Obliczenie znaku liczby całkowitej otrzymujemy, zmienna mask ma wartość
11111111
A zatem
10001111 v
11111111 mask
===================
10001110 + (v + mask)
10001110
11111111
===================
01110001 ^ (v + mask) ^ mask
Ciąg 01110001 reprezentuje liczbę 113.
- Obliczenie (bitu) parzystości dla bajtu
static const bool ParityTable256[256] =
{
# define P2(n) n, n^1, n^1, n
# define P4(n) P2(n), P2(n^1), P2(n^1), P2(n)
# define P6(n) P4(n), P4(n^1), P4(n^1), P4(n)
P6(0), P6(1), P6(1), P6(0)
};
unsigned char b; // byte value to compute the parity of
bool parity = ParityTable256[b];
Przykład działania
tutu
- Zamiana wartości dwóch zmiennych bez korzystania ze zmiennej pomocniczej
#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))
Przykład działania
tutu
- Jeszcze raz obliczanie wartości minimalnej i maksymalnej
int x; // we want to find the minimum of x and y
int y;
int r; // the result goes here
r = y ^ ((x ^ y) & -(x < y)); // min(x, y)
r = x ^ ((x ^ y) & -(x < y)); // max(x, y)
Przykład działania
POZOSTAWIONY JAKO ĆWICZENIE
- Sprawdzenie, czy zadana liczba jest potęgą liczby 2
unsigned int v; // we want to see if v is a power of 2
bool f; // the result goes here
f = (v & (v - 1)) == 0;
Note that 0 is incorrectly considered a power of 2 here. To remedy this, use:
f = v && !(v & (v - 1));
Przykład działania
POZOSTAWIONY JAKO ĆWICZENIE
- Połączenie bitów z dwóch bajtów w jeden bajt zgodnie z zadaną maską
unsigned int a; // value to merge in non-masked bits
unsigned int b; // value to merge in masked bits
unsigned int mask; // 1 where bits from b should be selected; 0 where from a.
unsigned int r; // result of (a & ~mask) | (b & mask) goes here
r = a ^ ((a ^ b) & mask);
Przykład działania
POZOSTAWIONY JAKO ĆWICZENIE
- Dzielenie modulo dla potęg liczby 2
const unsigned int n; // numerator
const unsigned int s;
const unsigned int d = 1U << s; // So d will be one of: 1, 2, 4, 8, 16, 32, ...
unsigned int m; // m will be n % d
m = n & (d - 1);
Przykład działania
POZOSTAWIONY JAKO ĆWICZENIE
Omówiono ideę programowania w logice na przykładzie języka Prolog. Wskazano istotne różnice i potencjalne możliwości wykorzystania.