Jak pewnie się orientujesz najnowsze procesory obsługują liczby 64-bitowe. Jak myślisz, o jakiej ilości bitów myślałem redagując temat ? 128 ? a może 1024 ? A co powiesz na liczbę, która składa się z 4GB, czyli 32Gbitów?

Pamiętasz jak poradziliśmy sobie z tym zagadnieniem w cz. 1 ? Jak zatem należałoby zmodyfikować nasz algorytm, aby znaleźć najstarszy bit tak dużej liczby. Przecież ona nie mieści się w pojedynczym rejestrze procesora. A zatem, nasze zadanie sprowadzi się do tego, aby odnaleźć pierszy ustawiony bit nie jak poprzednio w rejestrze tylko w pamięci (oczywiście tak jak w poprzednim przypadku liczymy od końca bufora, gdyż chodzi o najstarszy bit).

void getLongBitVectorEigenVal(
	unsigned long int* pSrcBitVector
	, unsigned long int* pDstBitVector
	, unsigned long int count)
{
	unsigned long int* srcVal = pSrcBitVector;
	unsigned long int* dstVal = pDstBitVector;
	for (int i = count - 1; i >= 0; --i)
	dstVal[i] = 0;
	for (int i = count - 1; i >= 0; --i)
	{
		asm
		{
		mov EBX, i;
		shl EBX, 2;
		mov ESI, srcVal;
		mov EDI, dstVal;
		mov EDX, [ESI + EBX];
		xor ECX, ECX;
		bsr EAX, EDX;
		jz not_found
		bts ECX, EAX;
		mov [EDI + EBX], ECX;
		jmp break_loop;
		not_found:
		mov [EDI + EBX], ECX;
		}
	}

	asm
	{
	break_loop:
	}
}

Rozpoczynamy od wyzerowania całego wektora docelowego (czyli naszej mega wielkiej liczby). Poruszając się od najdalej położonych bajtów ładujemy do rejestru kolejne coraz to młodsze bajty i wykonujemy znany nam z pierwszej części artykułu algorytm przeszukiwania bitowego. Owo przeszukiwanie bitowe powtarzamy tak długo, aż natrafimy na pierwszy ustawiony bit.

Powinieneś pamiętać, że fizycznie będziesz miał kłopot z zaalokowaniem dwóch liczb o rozmiarze 4GB każda.

Zastanawiasz się pewnie dlaczego tak dziwnie został napisany ten kod - wymieszany C++ i Assembler ? Chciałem Ci pokazać jak można używać tych dwóch języków.

Możnaby pokusić się o zoptymalizowanie pętli zerującej liczbę. Zobacz w debugu assemblerowym jak wygląda ta pętla, a sam dojdziesz do wniosku, że jest tam sporo nadmiarowych elementów.
Pewna nota dla tych którzy chętnie uprościliby ten kod stosując lodsd, movsd, stosd. Niestety instrukcje te operują na rejestrach segmentowych, którym należałoby zmienić wartość tak aby wskazywały na właściwe obszary pamięci. Konsekwencją operacji les czy lds jest wyjątek EAccessViolation wynika to z pewnych zabezpieczeń.

Tags: assembler, C++