Najszybszy sposób wyliczenia poprzez włączone bity liczby całkowitej

Question

Jaki jest najszybszy sposób wyliczenia poprzez liczbę całkowitą i zwrócenie wykładnika każdego bitu, który jest włączony? Widziałem przykład przy użyciu < < i innym przy użyciu Math.Pow. Zastanawiasz się, czy jest coś jeszcze, co jest naprawdę szybkie.

Dzięki.

Answer 1

Wyobrażam sobie, że przesunięcie bitów będzie najszybsze. Nieprześcigniony, ale myślę, że następujące powinny być szybkie (tak szybko jak IEnumerables są co najmniej).

IEnumerable<int> GetExponents(Int32 value) 
{ 
    for(int i=0; i<32; i++) 
    { 
     if(value & 1) 
      yield return i; 
     value >>= 1; 
    } 
} 

Jeśli chcesz, aby był szybszy, możesz rozważyć zwrot List<int> zamiast tego.

Answer 2

Domyślam się, że przesunięcie bitów (< <) jest najszybsze.

Answer 3

Tablica wyników dla bitów jednego bajtu powinna być zbliżona do najszybszej możliwej do wykonania w bezpiecznym kodzie C#. Przesunąć każdy z 4 bajtów z liczby całkowitej (odlewanie do uint, jeśli to konieczne) i indeksować do tablicy.

Elementami tablicy odnośników może być tablica wykładników lub, w zależności od tego, co robisz z bitami, być może delegaci, którzy działają.

Answer 4

Najszybszy podany rozkład dla danych wejściowych? Jeśli typowo ustawiony jest tylko jeden bit, może to być szybsze niż szukanie bitów set.

Przyjmując przyjętą odpowiedź dotyczącą znalezienia position of the least significant bit, która zajęła Bit Twiddling Hacks, to rozwiązanie rozwiązuje pętle, odnajduje, usuwa i zwraca pozycję każdego kolejnego najmniej znaczącego bitu.

static int[] MulDeBruijnBitPos = new int[32] 
    { 
     0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
     31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 
    }; 

    static IEnumerable<int> GetExponents(UInt32 v) 
    { 
     UInt32 m; 

     while(v != 0) { 
      m = (v & (UInt32) (-v)); 
      yield return MulDeBruijnBitPos[((UInt32) (m * 0x077CB531U)) >> 27]; 
      v ^= m; 
     } 
    } 

Pętle tylko tyle razy, ile jest ustawionych bitów.

Answer 5

Sposób najszybszy? Tabele przeglądowe są prawie zawsze najszybszym sposobem. Zbuduj tablicę int [] [] z czterema miliardami wpisów, po jednym dla każdej int, zawierającej tablicę żądanych liczb. Inicjowanie tabeli zajmie oczywiście trochę czasu, ale wyszukiwania będą niewiarygodnie szybkie.

Zaznaczam, że nie powiedziałeś, co oznacza "najszybszy" z wystarczającą precyzją, aby ktokolwiek mógł odpowiedzieć na pytanie. Czy to oznacza najszybszy czas amortyzacji, w tym czas uruchomienia, czy też margines czasu wyszukiwania, zakładając, że koszty uruchomienia mogą zostać zaniedbane? Mój szkic rozwiązania zakłada to drugie.

Oczywiście 32-bitowa maszyna z 2 miliardami bajtów przestrzeni adresowej nie będzie miała wystarczającej przestrzeni adresowej do przechowywania trzydziestu miliardów bajtów tablic. Zdobądź maszynę 64-bitową. Będziesz potrzebował przynajmniej tyle fizycznej pamięci zainstalowanej, jeśli chcesz, aby była szybka - stronicowanie zabije cię w inny sposób.

Mam nadzieję, że kilka nanosekund, które zaoszczędzisz na każdym wyszukiwaniu, warto kupić cały ten dodatkowy sprzęt. A może nie rzeczywiście chcesz uzyskać najszybszy sposób?

:-)

Answer 6

Tylko dla zabawy, tu jest jeden-liner przy użyciu LINQ.

Z pewnością nie jest to najszybszy sposób na zrobienie tego, choć niewiele pozostaje w tyle za innymi odpowiedziami, które używają bloków yield i iteratorów.

int test = 42; 

// returns 1, 3, 5 
// 2^1 + 2^3 + 2^5 
// = 2 + 8 + 32 
// = 42 
var exponents = Enumerable.Range(0, 32).Where(x => ((test >> x) & 1) == 1); 

Aby uzyskać szybsze rozwiązanie, prawdopodobnie zwrócę zwykłą kolekcję zamiast używać bloku iteratora. Coś takiego:

int test = 2458217; 

// returns 0, 3, 5, 6, 9, 15, 16, 18, 21 
// 2^0 + 2^3 + 2^5 + 2^6 + 2^9 + 2^15 + 2^16 + 2^18 + 2^21 
// = 1 + 8 + 32 + 64 + 512 + 32768 + 65536 + 262144 + 2097152 
// = 2458217 
var exponents = GetExponents(test); 

// ... 

public static List<int> GetExponents(int source) 
{ 
    List<int> result = new List<int>(32); 

    for (int i = 0; i < 32; i++) 
    { 
     if (((source >> i) & 1) == 1) 
     { 
      result.Add(i); 
     } 
    } 

    return result; 
} 

Answer 7

IEnumerable nie będzie działać. Optymalizacja niektórych przykładach w tym temacie:

Pierwszy z nich (najszybsza - 2,35 sekundy dla 10M tras, zakres 1..10M):

static uint[] MulDeBruijnBitPos = new uint[32] 
{ 
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 
}; 

static uint[] GetExponents(uint value) 
{ 
    uint[] data = new uint[32]; 
    int enabledBitCounter = 0; 

    while (value != 0) 
    { 
     uint m = (value & (0 - value)); 
     value ^= m; 
     data[enabledBitCounter++] = MulDeBruijnBitPos[(m * (uint)0x077CB531U) >> 27]; 
    } 

    Array.Resize<uint>(ref data, enabledBitCounter); 
    return data; 
} 

innej wersji (drugi najszybszy - 3 sekund 10M tras, zakres 1..10M):

static uint[] GetExponents(uint value) 
{ 
    uint[] data = new uint[32]; 
    int enabledBitCounter = 0; 

    for (uint i = 0; value > 0; ++i) 
    { 
     if ((value & 1) == 1) 
      data[enabledBitCounter++] = i; 
     value >>= 1; 
    } 

    Array.Resize<uint>(ref data, enabledBitCounter); 
    return data; 
} 

Answer 8

Jeśli nie będą dusić na małym C++:

void func(int i, int& n, int a[]){ 
    n = 0; 
    if (i < 0) a[n++] = 31; 
    i <<= 1; 
    if (i < 0) a[n++] = 30; 
    i <<= 1; 
    if (i < 0) a[n++] = 29; 
    i <<= 1; 

    ... 

    if (i < 0) a[n++] = 0; 
}