Witam,
szukam najszybszego sposobu na przeszukiwaniu longa. Już tłumaczę o co mi chodzi
załóżmy, że mam liczbę: 0b000000000010000100000010000001000000000100010000000001000000000L
Potrzebuję znaleźć pozycje wszystkich jedynek występujących w liczbie. Czy jest do tego jakaś biblioteka lub szybszy sposób niż pętla i sprawdzanie pojedynczo każdego bitu?
Pozdrawiam
A czego spodziewasz się na wyjściu algorytmu?
-- edited: w sensie struktury danych przechowującej wynik
Przesuwanie maski bitowej 0x8000...000, bitowe mnożenie i pętla może być dość szybkie na JVM, Po iluś przekręceniach się pętli zostanie mocno zoptymalizowane - ale POD WARUNKIEM że w pętli nie powołujesz obiektów.
Pokaż co wymyśliłeś do tej pory, również sposób skorzystania z wyniku
knightMoves jest tym moim longiem, w którym szukam jedynek
pieces to moje figury (aplikacja to szachy)
for(int j = 0; j < pieces.length; j++) {
if((knightMoves & (1L << j)) > 0) {
possibleMoves.add(j);
}
}
Wedle mojej wiedzy nie ma jakiegoś szybszego sposobu niz sprawdzenie wszystkich bitów. A po co Ci to? Przecież złożoność nie jest duża (64 bity). Przykładowy kod (na wyjściu jest lista, listę Możesz sobie przekonwertować do czego tam Chcesz):
import java.util.ArrayList;
import java.util.List;
public class SearchLong {
private static List<Long> positions_of_one(long number) {
List<Long> ones = new ArrayList<>();
int position = 1;
while (number != 0) {
if ((number & 1L) != 0) {
ones.add(position);
}
position++;
number = number >>> 1;
}
return ones;
}
public static void main(String [] args)
{
System.out.println(positions_of_one(7L)); // [1, 2, 3]
}
}
Najszybsze są metody najstarsze ;-) czyli lookup. Utwórz tablicę z liczbami jedynek dla kolejnych wartości np. bajtu lub słowa. Dzielisz longa na kolejne bajty, słowa, które dają Ci indeksy do komórek w lookup i w ośmiu albo czterech krokach masz liczbę jedynek.
Optymalne wyszukiwanie pierwszej jedynki jest dostępne z poziomu C. Wspiera to procesor. W Javie się nie da. Ale może wcześniej należało coś zoptymalizować, zanim dostałeś te "longi".
jarekczek napisał(a):
Optymalne wyszukiwanie pierwszej jedynki jest dostępne z poziomu C. Wspiera to procesor. W Javie się nie da. Ale może wcześniej należało coś zoptymalizować, zanim dostałeś te "longi".
To nieprawda. Jeśli chodzi Ci o **bsr **i bsf to masz je w javie dostępne przez:
https://docs.oracle.com/javase/8/docs/api/java/lang/Long.html#numberOfTrailingZeros-long-
https://docs.oracle.com/javase/8/docs/api/java/lang/Long.html#numberOfLeadingZeros-long-