Jaki jest najszybszy / najbardziej efektywny sposób na znalezienie najwyższego ustawionego bitu (msb) w liczbie całkowitej w C?

Jeśli mam jakąś liczbę całkowitą n i chcę poznać położenie najbardziej znaczącego bitu (to znaczy, jeśli najmniej znaczący bit znajduje się po prawej stronie, chcę poznać położenie najdalszego lewego bitu, czyli 1), jaka jest najszybsza / najskuteczniejsza metoda dowiedzenia się?

Wiem, że POSIX obsługuje ffs()metodę w strings.h, aby znaleźć pierwszy ustawiony bit, ale wydaje się, że nie ma odpowiedniej fls()metody.

Czy jest jakiś naprawdę oczywisty sposób na zrobienie tego, którego mi brakuje?

A co w przypadkach, gdy nie można używać funkcji POSIX do przenoszenia?

Edycja: A co z rozwiązaniem, które działa zarówno na architekturach 32-bitowych, jak i 64-bitowych (wiele list kodów wydaje się działać tylko na 32-bitowych intach).

GCC ma :

 - Wbudowana funkcja: int __builtin_clz (unsigned int x)
     Zwraca liczbę początkowych 0 bitów w X, zaczynając od najwyżej
     znacząca pozycja bitu. Jeśli X wynosi 0, wynik jest niezdefiniowany.

 - Wbudowana funkcja: int __builtin_clzl (unsigned long)
     Podobny do `__builtin_clz ', z tą różnicą, że typ argumentu to` unsigned
     długie'.

 - Wbudowana funkcja: int __builtin_clzll (unsigned long long)
     Podobny do `__builtin_clz ', z tą różnicą, że typ argumentu to` unsigned
     długo, długo ”.

Spodziewałbym się, że zostaną przetłumaczone na coś w miarę wydajnego dla twojej obecnej platformy, bez względu na to, czy będzie to jeden z tych fantazyjnych algorytmów do zawijania bitów, czy też pojedyncza instrukcja.

Przydatny trik jeśli wejście może być zerowy jest __builtin_clz(x | 1): bezwarunkowo ustawienie niskiej trochę bez modyfikowania żadnych innych sprawia, że wyjście 31dla x=0bez zmiany wyjścia dla jakiegokolwiek innego wejścia.

Aby tego uniknąć, inną opcją są elementy wewnętrzne specyficzne dla platformy, takie jak ARM GCC __clz(bez nagłówka) lub x86 _lzcnt_u32na procesorach obsługujących lzcntinstrukcję. (Uważaj, że lzcntdekoduje jak bsrna starszych procesorach zamiast błędów, co daje 31-lzcnt dla niezerowych wejść.)

Niestety nie ma możliwości przenośnego wykorzystania różnych instrukcji CLZ na platformach innych niż x86, które definiują wynik dla input = 0 jako 32 lub 64 (zgodnie z szerokością operandu). x86 też to lzcntrobi, bsrgenerując indeks bitowy, który kompilator musi odwrócić, chyba że używasz 31-__builtin_clz(x).

(„Niezdefiniowany wynik” nie jest C Undefined Behavior, tylko wartością, która nie jest zdefiniowana. W rzeczywistości jest to wszystko, co znajdowało się w rejestrze docelowym podczas wykonywania instrukcji. AMD to udokumentuje, Intel nie, ale procesory Intela implementują to zachowanie . Ale to nie jest to, co było wcześniej w zmiennej C, do której przypisujesz, zwykle tak nie działa, gdy gcc zamienia C w asm. Zobacz także Dlaczego zerwanie "zależności wyjściowej" LZCNT ma znaczenie? )

Zakładając, że korzystasz z x86 i gry dla trochę wbudowanego asemblera, Intel dostarcza BSRinstrukcje („odwrotne skanowanie bitowe”). Jest szybki na niektórych x86 (mikrokodowany na innych). Z instrukcji:

Przeszukuje operand źródłowy dla najbardziej znaczącego bitu zestawu (1 bit). Jeśli zostanie znaleziony 1 najbardziej znaczący bit, jego indeks bitowy jest przechowywany w operandzie docelowym. Operand źródłowy może być rejestrem lub lokalizacją pamięci; operandem przeznaczenia jest rejestr. Indeks bitowy jest przesunięciem bez znaku z bitu 0 argumentu źródłowego. Jeśli operand źródła treści ma wartość 0, zawartość operandu docelowego jest niezdefiniowana.

(Jeśli korzystasz z PowerPC, istnieje podobna cntlzinstrukcja („liczenie zer wiodących”).)

Przykładowy kod dla gcc:

#include <iostream>

int main (int,char**)
{
  int n=1;
  for (;;++n) {
    int msb;
    asm("bsrl %1,%0" : "=r"(msb) : "r"(n));
    std::cout << n << " : " << msb << std::endl;
  }
  return 0;
}

Zobacz także ten samouczek asemblera wbudowanego , który pokazuje (sekcja 9.4), że jest on znacznie szybszy niż kod zapętlony.

Ponieważ 2 ^ N jest liczbą całkowitą z ustawionym tylko N-tym bitem (1 << N), znalezienie pozycji (N) najwyższego ustawionego bitu jest liczbą całkowitą o podstawie 2 tej liczby.

http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

unsigned int v;
unsigned r = 0;

while (v >>= 1) {
    r++;
}

Ten „oczywisty” algorytm może nie być przezroczysty dla wszystkich, ale gdy zdasz sobie sprawę, że kod przesuwa się w prawo o jeden bit wielokrotnie, aż skrajny lewy bit zostanie przesunięty (zwróć uwagę, że C traktuje każdą niezerową wartość jako prawdę) i zwraca liczbę zmian, ma to sens. Oznacza to również, że działa nawet wtedy, gdy ustawiono więcej niż jeden bit - wynik jest zawsze dla najbardziej znaczącego bitu.

Jeśli przewiniesz w dół na tej stronie, istnieją szybsze, bardziej złożone odmiany. Jeśli jednak wiesz, że masz do czynienia z liczbami z wieloma wiodącymi zerami, naiwne podejście może zapewnić akceptowalną prędkość, ponieważ przesuwanie bitów jest dość szybkie w C, a prosty algorytm nie wymaga indeksowania tablicy.

UWAGA: Używając wartości 64-bitowych, zachowaj szczególną ostrożność podczas korzystania z wyjątkowo sprytnych algorytmów; wiele z nich działa poprawnie tylko dla wartości 32-bitowych.

To powinno być błyskawiczne:

int msb(unsigned int v) {
  static const int pos[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};
  v |= v >> 1;
  v |= v >> 2;
  v |= v >> 4;
  v |= v >> 8;
  v |= v >> 16;
  v = (v >> 1) + 1;
  return pos[(v * 0x077CB531UL) >> 27];
}

To trochę tak, jakby znaleźć rodzaj logu liczb całkowitych. Są trochę skomplikowane sztuczki, ale stworzyłem do tego własne narzędzie. Celem jest oczywiście szybkość.

Zrozumiałem, że procesor ma już automatyczny detektor bitów, używany do konwersji liczb całkowitych na zmiennoprzecinkowe! Więc użyj tego.

double ff=(double)(v|1);
return ((*(1+(uint32_t *)&ff))>>20)-1023;  // assumes x86 endianness

Ta wersja rzutuje wartość na podwójną, a następnie odczytuje wykładnik, który mówi, gdzie znajdował się bit. Fantazyjne przesunięcie i odjęcie polega na wyodrębnieniu odpowiednich części z wartości IEEE.

Nieco szybsze jest użycie pływaków, ale zmiennoprzecinkowe mogą podać tylko pierwsze 24-bitowe pozycje ze względu na mniejszą precyzję.

Aby zrobić to bezpiecznie, bez niezdefiniowanego zachowania w C ++ lub C, użyj memcpyzamiast rzutowania wskaźnika do dziurkowania typów. Kompilatorzy wiedzą, jak skutecznie go wbudować.

// static_assert(sizeof(double) == 2 * sizeof(uint32_t), "double isn't 8-byte IEEE binary64");
// and also static_assert something about FLT_ENDIAN?

double ff=(double)(v|1);

uint32_t tmp;
memcpy(&tmp, ((const char*)&ff)+sizeof(uint32_t), sizeof(uint32_t));
return (tmp>>20)-1023;

Lub w C99 i nowszych użyj pliku union {double d; uint32_t u[2];};. Należy jednak pamiętać, że w C ++ punning typu union jest obsługiwany tylko w niektórych kompilatorach jako rozszerzenie, a nie w ISO C ++.

Zwykle będzie to wolniejsze niż specyficzne dla platformy wewnętrzne instrukcje zliczania zer wiodących, ale przenośne ISO C nie ma takiej funkcji. Niektóre procesory nie mają również instrukcji zliczania wiodących zera, ale niektóre z nich mogą skutecznie konwertować liczby całkowite na double. Jednak wpisywanie wzorca bitowego FP z powrotem do liczby całkowitej może być powolne (np. Na PowerPC wymaga przechowywania / przeładowania i zwykle powoduje zablokowanie magazynu).

Ten algorytm może być potencjalnie przydatny w implementacjach SIMD, ponieważ mniej procesorów ma SIMD lzcnt. x86 otrzymał taką instrukcję tylko z AVX512CD

Tutaj Kaz Kylheku

Porównałem dwa podejścia do tych liczb ponad 63-bitowych (długi typ długi na gcc x86_64), trzymając się z dala od bitu znaku.

(Tak się składa, że ​​do czegoś potrzebuję tego „znajdź najwyższy bit”).

Zaimplementowałem wyszukiwanie binarne oparte na danych (ściśle oparte na jednej z powyższych odpowiedzi). Zaimplementowałem również ręcznie całkowicie rozwinięte drzewo decyzyjne, które jest po prostu kodem z natychmiastowymi operandami. Żadnych pętli, żadnych tabel.

Drzewo decyzyjne (upper_bit_unrolled) zostało ocenione jako szybsze o 69%, z wyjątkiem przypadku n = 0, dla którego wyszukiwanie binarne ma jawny test.

Specjalny test wyszukiwania binarnego dla przypadku 0 jest tylko 48% szybszy niż drzewo decyzyjne, które nie ma specjalnego testu.

Kompilator, maszyna: (GCC 4.5.2, -O3, x86-64, 2867 MHz Intel Core i5).

int highest_bit_unrolled(long long n)
{
  if (n & 0x7FFFFFFF00000000) {
    if (n & 0x7FFF000000000000) {
      if (n & 0x7F00000000000000) {
        if (n & 0x7000000000000000) {
          if (n & 0x4000000000000000)
            return 63;
          else
            return (n & 0x2000000000000000) ? 62 : 61;
        } else {
          if (n & 0x0C00000000000000)
            return (n & 0x0800000000000000) ? 60 : 59;
          else
            return (n & 0x0200000000000000) ? 58 : 57;
        }
      } else {
        if (n & 0x00F0000000000000) {
          if (n & 0x00C0000000000000)
            return (n & 0x0080000000000000) ? 56 : 55;
          else
            return (n & 0x0020000000000000) ? 54 : 53;
        } else {
          if (n & 0x000C000000000000)
            return (n & 0x0008000000000000) ? 52 : 51;
          else
            return (n & 0x0002000000000000) ? 50 : 49;
        }
      }
    } else {
      if (n & 0x0000FF0000000000) {
        if (n & 0x0000F00000000000) {
          if (n & 0x0000C00000000000)
            return (n & 0x0000800000000000) ? 48 : 47;
          else
            return (n & 0x0000200000000000) ? 46 : 45;
        } else {
          if (n & 0x00000C0000000000)
            return (n & 0x0000080000000000) ? 44 : 43;
          else
            return (n & 0x0000020000000000) ? 42 : 41;
        }
      } else {
        if (n & 0x000000F000000000) {
          if (n & 0x000000C000000000)
            return (n & 0x0000008000000000) ? 40 : 39;
          else
            return (n & 0x0000002000000000) ? 38 : 37;
        } else {
          if (n & 0x0000000C00000000)
            return (n & 0x0000000800000000) ? 36 : 35;
          else
            return (n & 0x0000000200000000) ? 34 : 33;
        }
      }
    }
  } else {
    if (n & 0x00000000FFFF0000) {
      if (n & 0x00000000FF000000) {
        if (n & 0x00000000F0000000) {
          if (n & 0x00000000C0000000)
            return (n & 0x0000000080000000) ? 32 : 31;
          else
            return (n & 0x0000000020000000) ? 30 : 29;
        } else {
          if (n & 0x000000000C000000)
            return (n & 0x0000000008000000) ? 28 : 27;
          else
            return (n & 0x0000000002000000) ? 26 : 25;
        }
      } else {
        if (n & 0x0000000000F00000) {
          if (n & 0x0000000000C00000)
            return (n & 0x0000000000800000) ? 24 : 23;
          else
            return (n & 0x0000000000200000) ? 22 : 21;
        } else {
          if (n & 0x00000000000C0000)
            return (n & 0x0000000000080000) ? 20 : 19;
          else
            return (n & 0x0000000000020000) ? 18 : 17;
        }
      }
    } else {
      if (n & 0x000000000000FF00) {
        if (n & 0x000000000000F000) {
          if (n & 0x000000000000C000)
            return (n & 0x0000000000008000) ? 16 : 15;
          else
            return (n & 0x0000000000002000) ? 14 : 13;
        } else {
          if (n & 0x0000000000000C00)
            return (n & 0x0000000000000800) ? 12 : 11;
          else
            return (n & 0x0000000000000200) ? 10 : 9;
        }
      } else {
        if (n & 0x00000000000000F0) {
          if (n & 0x00000000000000C0)
            return (n & 0x0000000000000080) ? 8 : 7;
          else
            return (n & 0x0000000000000020) ? 6 : 5;
        } else {
          if (n & 0x000000000000000C)
            return (n & 0x0000000000000008) ? 4 : 3;
          else
            return (n & 0x0000000000000002) ? 2 : (n ? 1 : 0);
        }
      }
    }
  }
}

int highest_bit(long long n)
{
  const long long mask[] = {
    0x000000007FFFFFFF,
    0x000000000000FFFF,
    0x00000000000000FF,
    0x000000000000000F,
    0x0000000000000003,
    0x0000000000000001
  };
  int hi = 64;
  int lo = 0;
  int i = 0;

  if (n == 0)
    return 0;

  for (i = 0; i < sizeof mask / sizeof mask[0]; i++) {
    int mi = lo + (hi - lo) / 2;

    if ((n >> mi) != 0)
      lo = mi;
    else if ((n & (mask[i] << lo)) != 0)
      hi = mi;
  }

  return lo + 1;
}

Szybki i brudny program testowy:

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

int highest_bit_unrolled(long long n);
int highest_bit(long long n);

main(int argc, char **argv)
{
  long long n = strtoull(argv[1], NULL, 0);
  int b1, b2;
  long i;
  clock_t start = clock(), mid, end;

  for (i = 0; i < 1000000000; i++)
    b1 = highest_bit_unrolled(n);

  mid = clock();

  for (i = 0; i < 1000000000; i++)
    b2 = highest_bit(n);

  end = clock();

  printf("highest bit of 0x%llx/%lld = %d, %d\n", n, n, b1, b2);

  printf("time1 = %d\n", (int) (mid - start));
  printf("time2 = %d\n", (int) (end - mid));
  return 0;
}

Używając tylko -O2, różnica staje się większa. Drzewo decyzyjne jest prawie czterokrotnie szybsze.

Porównałem również z naiwnym kodem przesuwania bitów:

int highest_bit_shift(long long n)
{
  int i = 0;
  for (; n; n >>= 1, i++)
    ; /* empty */
  return i;
}

Jest to szybkie tylko dla małych liczb, jak można by się spodziewać. Ustalając, że najwyższy bit to 1 dla n == 1, test porównawczy był szybszy o ponad 80%. Jednak połowa losowo wybranych liczb w przestrzeni 63-bitowej ma ustawiony 63. bit!

Na wejściu 0x3FFFFFFFFFFFFFFF wersja drzewa decyzyjnego jest nieco szybsza niż na 1 i pokazuje, że jest o 1120% szybsza (12,2 razy) niż przesuwnik bitów.

Dokonam również porównania drzewa decyzyjnego z wbudowanymi GCC, a także spróbuję mieszanki danych wejściowych zamiast powtarzania dla tej samej liczby. Mogą występować pewne przewidywania gałęzi i być może nierealistyczne scenariusze buforowania, które sztucznie przyspieszają powtórzenia.

Co powiesz na

int highest_bit(unsigned int a) {
    int count;
    std::frexp(a, &count);
    return count - 1;
}

?

unsigned int
msb32(register unsigned int x)
{
        x |= (x >> 1);
        x |= (x >> 2);
        x |= (x >> 4);
        x |= (x >> 8);
        x |= (x >> 16);
        return(x & ~(x >> 1));
}

1 rejestr, 13 instrukcji. Wierz lub nie, ale jest to zazwyczaj szybsze niż wspomniana powyżej instrukcja BSR, która działa w czasie liniowym. To jest czas logarytmiczny.

Z http://aggregate.org/MAGIC/#Most%20Ssequant%201%20Bit

Oto kilka (prostych) testów porównawczych algorytmów obecnie podanych na tej stronie ...

Algorytmy nie zostały przetestowane na wszystkich wejściach typu unsigned int; więc sprawdź to najpierw, zanim na ślepo użyjesz czegoś;)

Na moim komputerze najlepiej działają clz (__builtin_clz) i asm. asm wydaje się nawet szybszy niż clz ... ale może to wynikać z prostego testu porównawczego ...

//////// go.c ///////////////////////////////
// compile with:  gcc go.c -o go -lm
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/***************** math ********************/

#define POS_OF_HIGHESTBITmath(a) /* 0th position is the Least-Signif-Bit */    \
  ((unsigned) log2(a))         /* thus: do not use if a <= 0 */  

#define NUM_OF_HIGHESTBITmath(a) ((a)               \
                  ? (1U << POS_OF_HIGHESTBITmath(a))    \
                  : 0)



/***************** clz ********************/

unsigned NUM_BITS_U = ((sizeof(unsigned) << 3) - 1);
#define POS_OF_HIGHESTBITclz(a) (NUM_BITS_U - __builtin_clz(a)) /* only works for a != 0 */

#define NUM_OF_HIGHESTBITclz(a) ((a)                    \
                 ? (1U << POS_OF_HIGHESTBITclz(a))  \
                 : 0)


/***************** i2f ********************/

double FF;
#define POS_OF_HIGHESTBITi2f(a) (FF = (double)(ui|1), ((*(1+(unsigned*)&FF))>>20)-1023)


#define NUM_OF_HIGHESTBITi2f(a) ((a)                    \
                 ? (1U << POS_OF_HIGHESTBITi2f(a))  \
                 : 0)




/***************** asm ********************/

unsigned OUT;
#define POS_OF_HIGHESTBITasm(a) (({asm("bsrl %1,%0" : "=r"(OUT) : "r"(a));}), OUT)

#define NUM_OF_HIGHESTBITasm(a) ((a)                    \
                 ? (1U << POS_OF_HIGHESTBITasm(a))  \
                 : 0)




/***************** bitshift1 ********************/

#define NUM_OF_HIGHESTBITbitshift1(a) (({   \
  OUT = a;                  \
  OUT |= (OUT >> 1);                \
  OUT |= (OUT >> 2);                \
  OUT |= (OUT >> 4);                \
  OUT |= (OUT >> 8);                \
  OUT |= (OUT >> 16);               \
      }), (OUT & ~(OUT >> 1)))          \



/***************** bitshift2 ********************/
int POS[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};

#define POS_OF_HIGHESTBITbitshift2(a) (({   \
  OUT = a;                  \
  OUT |= OUT >> 1;              \
  OUT |= OUT >> 2;              \
  OUT |= OUT >> 4;              \
  OUT |= OUT >> 8;              \
  OUT |= OUT >> 16;             \
  OUT = (OUT >> 1) + 1;             \
      }), POS[(OUT * 0x077CB531UL) >> 27])

#define NUM_OF_HIGHESTBITbitshift2(a) ((a)              \
                       ? (1U << POS_OF_HIGHESTBITbitshift2(a)) \
                       : 0)



#define LOOPS 100000000U

int main()
{
  time_t start, end;
  unsigned ui;
  unsigned n;

  /********* Checking the first few unsigned values (you'll need to check all if you want to use an algorithm here) **************/
  printf("math\n");
  for (ui = 0U; ui < 18; ++ui)
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITmath(ui));

  printf("\n\n");

  printf("clz\n");
  for (ui = 0U; ui < 18U; ++ui)
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITclz(ui));

  printf("\n\n");

  printf("i2f\n");
  for (ui = 0U; ui < 18U; ++ui)
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITi2f(ui));

  printf("\n\n");

  printf("asm\n");
  for (ui = 0U; ui < 18U; ++ui) {
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITasm(ui));
  }

  printf("\n\n");

  printf("bitshift1\n");
  for (ui = 0U; ui < 18U; ++ui) {
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITbitshift1(ui));
  }

  printf("\n\n");

  printf("bitshift2\n");
  for (ui = 0U; ui < 18U; ++ui) {
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITbitshift2(ui));
  }

  printf("\n\nPlease wait...\n\n");


  /************************* Simple clock() benchmark ******************/
  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITmath(ui);
  end = clock();
  printf("math:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITclz(ui);
  end = clock();
  printf("clz:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITi2f(ui);
  end = clock();
  printf("i2f:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITasm(ui);
  end = clock();
  printf("asm:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITbitshift1(ui);
  end = clock();
  printf("bitshift1:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITbitshift2(ui);
  end = clock();
  printf("bitshift2\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  printf("\nThe lower, the better. Take note that a negative exponent is good! ;)\n");

  return EXIT_SUCCESS;
}

Chociaż prawdopodobnie użyłbym tej metody tylko wtedy, gdybym absolutnie potrzebował najlepszej możliwej wydajności (np. Do pisania jakiejś gry planszowej z użyciem bitboardów), najbardziej wydajnym rozwiązaniem jest użycie wbudowanego ASM. Zobacz sekcję Optymalizacje w tym poście na blogu, aby znaleźć kod z wyjaśnieniem.

[…], bsrlinstrukcja asemblera oblicza położenie najbardziej znaczącego bitu. Dlatego możemy użyć tego asmstwierdzenia:

asm ("bsrl %1, %0" 
     : "=r" (position) 
     : "r" (number));

Potrzebowałem rutyny, aby to zrobić i przed przeszukaniem sieci (i znalezieniem tej strony) wymyśliłem własne rozwiązanie oparte na wyszukiwaniu binarnym. Chociaż jestem pewien, że ktoś już to zrobił! Działa w stałym czasie i może być szybsze niż opublikowane "oczywiste" rozwiązanie, chociaż nie zgłaszam żadnych wielkich roszczeń, tylko zamieszczam je dla zainteresowania.

int highest_bit(unsigned int a) {
  static const unsigned int maskv[] = { 0xffff, 0xff, 0xf, 0x3, 0x1 };
  const unsigned int *mask = maskv;
  int l, h;

  if (a == 0) return -1;

  l = 0;
  h = 32;

  do {
    int m = l + (h - l) / 2;

    if ((a >> m) != 0) l = m;
    else if ((a & (*mask << l)) != 0) h = m;

    mask++;
  } while (l < h - 1);

  return l;
}

to jest jakiś rodzaj wyszukiwania binarnego, działa ze wszystkimi typami liczb całkowitych (bez znaku!)

#include <climits>
#define UINT (unsigned int)
#define UINT_BIT (CHAR_BIT*sizeof(UINT))

int msb(UINT x)
{
    if(0 == x)
        return -1;

    int c = 0;

    for(UINT i=UINT_BIT>>1; 0<i; i>>=1)
    if(static_cast<UINT>(x >> i))
    {
        x >>= i;
        c |= i;
    }

    return c;
}

dopełnić:

#include <climits>
#define UINT unsigned int
#define UINT_BIT (CHAR_BIT*sizeof(UINT))

int lsb(UINT x)
{
    if(0 == x)
        return -1;

    int c = UINT_BIT-1;

    for(UINT i=UINT_BIT>>1; 0<i; i>>=1)
    if(static_cast<UINT>(x << i))
    {
        x <<= i;
        c ^= i;
    }

    return c;
}

Niektóre zbyt złożone odpowiedzi tutaj. Technika Debruin powinna być używana tylko wtedy, gdy dane wejściowe są już potęgą dwójki, w przeciwnym razie jest lepszy sposób. Dla mocy 2 wejść Debruin jest absolutnie najszybszy, nawet szybszy niż _BitScanReversena każdym testowanym przeze mnie procesorze. Jednak w ogólnym przypadku _BitScanReverse(lub jakikolwiek element wewnętrzny jest wywoływany w twoim kompilatorze) jest najszybszy (na niektórych procesorach może być jednak mikrokodowany).

Jeśli funkcja wewnętrzna nie wchodzi w grę, tutaj jest optymalne rozwiązanie programowe do przetwarzania ogólnych danych wejściowych.

u8  inline log2 (u32 val)  {
    u8  k = 0;
    if (val > 0x0000FFFFu) { val >>= 16; k  = 16; }
    if (val > 0x000000FFu) { val >>= 8;  k |= 8;  }
    if (val > 0x0000000Fu) { val >>= 4;  k |= 4;  }
    if (val > 0x00000003u) { val >>= 2;  k |= 2;  }
    k |= (val & 2) >> 1;
    return k;
}

Zauważ, że ta wersja nie wymaga na końcu wyszukiwania Debruin, w przeciwieństwie do większości innych odpowiedzi. Oblicza pozycję w miejscu.

Tabele mogą być jednak lepsze, jeśli wywołujesz je wielokrotnie, ryzyko pominięcia pamięci podręcznej zostanie przyćmione przez przyspieszenie tabeli.

u8 kTableLog2[256] = {
0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
};

u8 log2_table(u32 val)  {
    u8  k = 0;
    if (val > 0x0000FFFFuL) { val >>= 16; k  = 16; }
    if (val > 0x000000FFuL) { val >>=  8; k |=  8; }
    k |= kTableLog2[val]; // precompute the Log2 of the low byte

    return k;
}

Powinno to zapewnić największą przepustowość spośród wszystkich podanych tutaj odpowiedzi dotyczących oprogramowania, ale jeśli wywołujesz to tylko sporadycznie, preferuj rozwiązanie bez tabel, takie jak mój pierwszy fragment.

Jak wskazują powyższe odpowiedzi, istnieje wiele sposobów określenia najbardziej znaczącego bitu. Jednak, jak również wskazano, metody te mogą być unikalne dla rejestrów 32- lub 64-bitowych. Strona bitów stanford.edu zawiera rozwiązania, które działają zarówno dla komputerów 32-bitowych, jak i 64-bitowych. Przy odrobinie pracy można je połączyć, aby zapewnić solidne podejście oparte na architekturze do uzyskania MSB. Rozwiązanie, do którego doszedłem, które skompilowałem / pracowałem na komputerach 64 i 32-bitowych, to:

#if defined(__LP64__) || defined(_LP64)
# define BUILD_64   1
#endif

#include <stdio.h>
#include <stdint.h>  /* for uint32_t */

/* CHAR_BIT  (or include limits.h) */
#ifndef CHAR_BIT
#define CHAR_BIT  8
#endif  /* CHAR_BIT */

/* 
 * Find the log base 2 of an integer with the MSB N set in O(N)
 * operations. (on 64bit & 32bit architectures)
 */
int
getmsb (uint32_t word)
{
    int r = 0;
    if (word < 1)
        return 0;
#ifdef BUILD_64
    union { uint32_t u[2]; double d; } t;  // temp
    t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
    t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = word;
    t.d -= 4503599627370496.0;
    r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF;
#else
    while (word >>= 1)
    {
        r++;
    }
#endif  /* BUILD_64 */
    return r;
}

Wersja w C przy użyciu kolejnych przybliżeń:

unsigned int getMsb(unsigned int n)
{
  unsigned int msb  = sizeof(n) * 4;
  unsigned int step = msb;
  while (step > 1)
 {
    step /=2;
    if (n>>msb)
     msb += step;
   else
     msb -= step;
 }
  if (n>>msb)
    msb++;
  return (msb - 1);
}

Zaleta: czas działania jest stały niezależnie od podanej liczby, ponieważ liczba pętli jest zawsze taka sama. (4 pętle w przypadku użycia „unsigned int”)

Wiem, że to pytanie jest bardzo stare, ale po tym, jak sam zaimplementowałem funkcję msb () , stwierdziłem, że większość rozwiązań przedstawionych tutaj i na innych stronach internetowych niekoniecznie jest najbardziej wydajnych - przynajmniej dla mojej osobistej definicji wydajności (patrz również Aktualizacja poniżej ). Dlatego:

Większość rozwiązań (zwłaszcza tych, które wykorzystują jakiś rodzaj binarnego schematu wyszukiwania lub naiwne podejście, które wykonuje liniowe skanowanie od prawej do lewej) wydaje się pomijać fakt, że w przypadku dowolnych liczb binarnych niewiele jest takich, które zaczynają się od bardzo długiej sekwencji zera. W rzeczywistości dla dowolnej szerokości bitowej połowa wszystkich liczb całkowitych zaczyna się od 1, a jedna czwarta z nich zaczyna się od 01 . Widzisz, dokąd zmierzam? Mój argument jest taki, że skanowanie liniowe zaczynające się od najbardziej znaczącej pozycji bitowej do najmniej znaczącej (od lewej do prawej) nie jest tak „liniowe”, jak mogłoby się wydawać na pierwszy rzut oka.

Można wykazać ¹ , że dla dowolnej szerokości bitowej średnia liczba bitów, które należy przetestować, wynosi co najwyżej 2. Przekłada się to na zamortyzowaną złożoność czasową O (1) w odniesieniu do liczby bitów (!) .

Oczywiście najgorszym przypadkiem jest nadal O (n) , gorsze niż O (log (n)), które uzyskuje się przy podejściach podobnych do wyszukiwania binarnego, ale ponieważ jest tak niewiele najgorszych przypadków, są one pomijalne dla większości aplikacji ( Aktualizacja : niezupełnie: może być ich niewiele, ale mogą wystąpić z dużym prawdopodobieństwem - patrz aktualizacja poniżej).

Oto "naiwne" podejście, które wymyśliłem, które przynajmniej na moim komputerze przewyższa większość innych podejść (schematy wyszukiwania binarnego dla 32-bitowych intów zawsze wymagają log ₂ (32) = 5 kroków, podczas gdy ten głupi algorytm wymaga mniej średnio niż 2) - przepraszam, że to C ++, a nie czyste C:

template <typename T>
auto msb(T n) -> int
{
    static_assert(std::is_integral<T>::value && !std::is_signed<T>::value,
        "msb<T>(): T must be an unsigned integral type.");

    for (T i = std::numeric_limits<T>::digits - 1, mask = 1 << i; i >= 0; --i, mask >>= 1)
    {
        if ((n & mask) != 0)
            return i;
    }

    return 0;
}

Aktualizacja : Podczas gdy to, co tutaj napisałem, jest całkowicie prawdziwe dla dowolnych liczb całkowitych, gdzie każda kombinacja bitów jest równie prawdopodobna (mój test szybkości mierzył po prostu, ile czasu zajęło określenie MSB dla wszystkich 32-bitowych liczb całkowitych), rzeczywistych liczb całkowitych, dla która taka funkcja zostanie wywołana, zwykle postępuje zgodnie z innym wzorcem: na przykład w moim kodzie ta funkcja jest używana do określenia, czy rozmiar obiektu jest potęgą 2, lub do znalezienia następnej potęgi 2 większej lub równej niż rozmiar obiektu . Domyślam się, że większość aplikacji używających MSB zawiera liczby, które są znacznie mniejsze niż maksymalna liczba, jaką może reprezentować liczba całkowita (rozmiary obiektów rzadko wykorzystują wszystkie bity w size_t). W tym przypadku moje rozwiązanie będzie faktycznie działać gorzej niż metoda wyszukiwania binarnego - więc prawdopodobnie powinno być preferowane to drugie, mimo że moje rozwiązanie będzie szybciej przeszukiwać wszystkie liczby całkowite.
TL; DR: Rzeczywiste liczby całkowite prawdopodobnie będą miały odchylenie w kierunku najgorszego przypadku tego prostego algorytmu, co ostatecznie pogorszy jego działanie - pomimo faktu, że jest on amortyzowany O (1) dla naprawdę dowolnych liczb całkowitych.

¹ Argument wygląda tak (szkic): Niech n będzie liczbą bitów (szerokość bitu). Łącznie jest 2 ⁿ liczb całkowitych, które można przedstawić za pomocą n bitów. Istnieją 2 liczby całkowite ^{n - 1} zaczynające się od 1 (pierwsze 1 jest stałe, pozostałe n - 1 bitów może być dowolnymi). Te liczby całkowite wymagają tylko jednej interakcji pętli, aby określić MSB. Ponadto istnieją 2 ^{n - 2} liczby całkowite zaczynające się od 01 , wymagające 2 iteracji, 2 ^{n - 3} liczby całkowite zaczynające się od 001 , wymagające 3 iteracji i tak dalej.

Jeśli zsumujemy wszystkie wymagane iteracje dla wszystkich możliwych liczb całkowitych i podzielimy je przez 2 ⁿ , całkowitą liczbę liczb całkowitych, otrzymamy średnią liczbę iteracji potrzebnych do wyznaczenia MSB dla n- bitowych liczb całkowitych:

(1 * 2 ^{n - 1} + 2 * 2 ^{n - 2} + 3 * 2 ^{n - 3} + ... + n) / 2 ⁿ

Ta seria średnich iteracji jest w rzeczywistości zbieżna i ma granicę 2 dla n do nieskończoności

Tak więc naiwny algorytm od lewej do prawej ma w rzeczywistości zamortyzowaną stałą złożoność czasową O (1) dla dowolnej liczby bitów.

c99dał nam log2. Eliminuje to potrzebę stosowania wszystkich specjalnych log2implementacji sosów, które widzisz na tej stronie. Możesz użyć log2implementacji standardu w następujący sposób:

const auto n = 13UL;
const auto Index = (unsigned long)log2(n);

printf("MSB is: %u\n", Index); // Prints 3 (zero offset)

nOd 0ULpotrzeb być chronione przed, jak również, ponieważ:

-∞ jest zwracane, a FE_DIVBYZERO jest podnoszone

Pisałem przykład z tej kontroli, które arbitralnie określa Indexsię ULONG_MAXtutaj: https://ideone.com/u26vsi

Plik studio wizualnenastępstwem jedynej odpowiedzi w gcc ephemienta jest:

const auto n = 13UL;
unsigned long Index;

_BitScanReverse(&Index, n);
printf("MSB is: %u\n", Index); // Prints 3 (zero offset)

Dokumentacja dla_BitScanReverse stanów Indexto:

Załadowany z pozycją bitu pierwszego znalezionego ustawionego bitu (1)

W praktyce Odkryłam, że jeśli nto 0UL, że Indexjest ustawiona0UL tak, jak byłoby to dla no 1UL. Ale jedyną rzeczą, zagwarantowane w dokumentacji w przypadku no 0ULto, że powrót jest:

0, jeśli nie znaleziono ustawionych bitów

Tak więc, podobnie jak w przypadku preferowanej log2implementacji powyżej, zwrot należy Indexw tym przypadku sprawdzić ustawiając na oflagowaną wartość. Ponownie napisałem przykład użycia ULONG_MAXtej wartości flagi tutaj: http://rextester.com/GCU61409

Pomyśl o operatorach bitowych.

Za pierwszym razem nie zrozumiałem pytania. Powinieneś utworzyć int z ustawionym najbardziej lewym bitem (pozostałe zero). Zakładając, że cmp jest ustawiony na tę wartość:

position = sizeof(int)*8
while(!(n & cmp)){ 
   n <<=1;
   position--;
}

Rozwijając benchmark Josha ... można poprawić clz w następujący sposób

/***************** clz2 ********************/

#define NUM_OF_HIGHESTBITclz2(a) ((a)                              \
                  ? (((1U) << (sizeof(unsigned)*8-1)) >> __builtin_clz(a)) \
                  : 0)

Odnośnie asm: zwróć uwagę, że istnieją bsr i bsrl (to jest „długa” wersja). normalny może być nieco szybszy.

Zwróć uwagę, że to, co próbujesz zrobić, to obliczyć liczbę całkowitą log2 liczby całkowitej,

#include <stdio.h>
#include <stdlib.h>

unsigned int
Log2(unsigned long x)
{
    unsigned long n = x;
    int bits = sizeof(x)*8;
    int step = 1; int k=0;
    for( step = 1; step < bits; ) {
        n |= (n >> step);
        step *= 2; ++k;
    }
    //printf("%ld %ld\n",x, (x - (n >> 1)) );
    return(x - (n >> 1));
}

Zauważ, że możesz próbować przeszukiwać więcej niż 1 bit na raz.

unsigned int
Log2_a(unsigned long x)
{
    unsigned long n = x;
    int bits = sizeof(x)*8;
    int step = 1;
    int step2 = 0;
    //observe that you can move 8 bits at a time, and there is a pattern...
    //if( x>1<<step2+8 ) { step2+=8;
        //if( x>1<<step2+8 ) { step2+=8;
            //if( x>1<<step2+8 ) { step2+=8;
            //}
        //}
    //}
    for( step2=0; x>1L<<step2+8; ) {
        step2+=8;
    }
    //printf("step2 %d\n",step2);
    for( step = 0; x>1L<<(step+step2); ) {
        step+=1;
        //printf("step %d\n",step+step2);
    }
    printf("log2(%ld) %d\n",x,step+step2);
    return(step+step2);
}

To podejście wykorzystuje wyszukiwanie binarne

unsigned int
Log2_b(unsigned long x)
{
    unsigned long n = x;
    unsigned int bits = sizeof(x)*8;
    unsigned int hbit = bits-1;
    unsigned int lbit = 0;
    unsigned long guess = bits/2;
    int found = 0;

    while ( hbit-lbit>1 ) {
        //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        //when value between guess..lbit
        if( (x<=(1L<<guess)) ) {
           //printf("%ld < 1<<%d %ld\n",x,guess,1L<<guess);
            hbit=guess;
            guess=(hbit+lbit)/2;
            //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        }
        //when value between hbit..guess
        //else
        if( (x>(1L<<guess)) ) {
            //printf("%ld > 1<<%d %ld\n",x,guess,1L<<guess);
            lbit=guess;
            guess=(hbit+lbit)/2;
            //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        }
    }
    if( (x>(1L<<guess)) ) ++guess;
    printf("log2(x%ld)=r%d\n",x,guess);
    return(guess);
}

Inna metoda wyszukiwania binarnego, być może bardziej czytelna,

unsigned int
Log2_c(unsigned long x)
{
    unsigned long v = x;
    unsigned int bits = sizeof(x)*8;
    unsigned int step = bits;
    unsigned int res = 0;
    for( step = bits/2; step>0; )
    {
        //printf("log2(%ld) v %d >> step %d = %ld\n",x,v,step,v>>step);
        while ( v>>step ) {
            v>>=step;
            res+=step;
            //printf("log2(%ld) step %d res %d v>>step %ld\n",x,step,res,v);
        }
        step /= 2;
    }
    if( (x>(1L<<res)) ) ++res;
    printf("log2(x%ld)=r%ld\n",x,res);
    return(res);
}

A ponieważ zechcesz je przetestować,

int main()
{
    unsigned long int x = 3;
    for( x=2; x<1000000000; x*=2 ) {
        //printf("x %ld, x+1 %ld, log2(x+1) %d\n",x,x+1,Log2(x+1));
        printf("x %ld, x+1 %ld, log2_a(x+1) %d\n",x,x+1,Log2_a(x+1));
        printf("x %ld, x+1 %ld, log2_b(x+1) %d\n",x,x+1,Log2_b(x+1));
        printf("x %ld, x+1 %ld, log2_c(x+1) %d\n",x,x+1,Log2_c(x+1));
    }
    return(0);
}

Uwzględnienie tego, ponieważ jest to „jeszcze jedno” podejście, wydaje się różnić od innych już podanych.

zwraca -1jeśli x==0, w przeciwnym razie floor( log2(x)) (maksymalny wynik 31)

Zmniejsz problem z 32 do 4 bitów, a następnie użyj tabeli. Może nieeleganckie, ale pragmatyczne.

To jest to, czego używam, gdy nie chcę używać z __builtin_clzpowodu problemów z przenośnością.

Aby uczynić go bardziej zwartym, można zamiast tego użyć pętli do redukcji, dodając 4 do r za każdym razem, maksymalnie 7 iteracji. Lub jakaś hybryda, na przykład (dla 64 bitów): pętla w celu zmniejszenia do 8, test w celu zmniejszenia do 4.

int log2floor( unsigned x ){
   static const signed char wtab[16] = {-1,0,1,1, 2,2,2,2, 3,3,3,3,3,3,3,3};
   int r = 0;
   unsigned xk = x >> 16;
   if( xk != 0 ){
       r = 16;
       x = xk;
   }
   // x is 0 .. 0xFFFF
   xk = x >> 8;
   if( xk != 0){
       r += 8;
       x = xk;
   }
   // x is 0 .. 0xFF
   xk = x >> 4;
   if( xk != 0){
       r += 4;
       x = xk;
   }
   // now x is 0..15; x=0 only if originally zero.
   return r + wtab[x];
}

Woaw, to było wiele odpowiedzi. Nie przepraszam, że odpowiadam na stare pytanie.

int result = 0;//could be a char or int8_t instead
if(value){//this assumes the value is 64bit
    if(0xFFFFFFFF00000000&value){  value>>=(1<<5); result|=(1<<5);  }//if it is 32bit then remove this line
    if(0x00000000FFFF0000&value){  value>>=(1<<4); result|=(1<<4);  }//and remove the 32msb
    if(0x000000000000FF00&value){  value>>=(1<<3); result|=(1<<3);  }
    if(0x00000000000000F0&value){  value>>=(1<<2); result|=(1<<2);  }
    if(0x000000000000000C&value){  value>>=(1<<1); result|=(1<<1);  }
    if(0x0000000000000002&value){  result|=(1<<0);  }
}else{
  result=-1;
}

Ta odpowiedź jest bardzo podobna do innej odpowiedzi ... no cóż.

Kod:

    // x>=1;
    unsigned func(unsigned x) {
    double d = x ;
    int p= (*reinterpret_cast<long long*>(&d) >> 52) - 1023;
    printf( "The left-most non zero bit of %d is bit %d\n", x, p);
    }

Lub uzyskaj część całkowitą instrukcji FPU FYL2X (Y * Log2 X), ustawiając Y = 1

Inny plakat udostępnił tablicę przeglądową używającą wyszukiwania o szerokości bajtów . Jeśli chcesz uzyskać nieco większą wydajność (kosztem 32 KB pamięci zamiast tylko 256 wpisów wyszukiwania), oto rozwiązanie wykorzystujące 15-bitową tabelę wyszukiwania , w C # 7 dla .NET .

Ciekawą częścią jest inicjalizacja tabeli. Ponieważ jest to stosunkowo mały blok, którego potrzebujemy na cały czas trwania procesu, przydzielam do tego niezarządzaną pamięć przy użyciu Marshal.AllocHGlobal. Jak widać, dla maksymalnej wydajności cały przykład jest napisany jako natywny:

readonly static byte[] msb_tab_15;

// Initialize a table of 32768 bytes with the bit position (counting from LSB=0)
// of the highest 'set' (non-zero) bit of its corresponding 16-bit index value.
// The table is compressed by half, so use (value >> 1) for indexing.
static MyStaticInit()
{
    var p = new byte[0x8000];

    for (byte n = 0; n < 16; n++)
        for (int c = (1 << n) >> 1, i = 0; i < c; i++)
            p[c + i] = n;

    msb_tab_15 = p;
}

Tabela wymaga jednorazowej inicjalizacji za pomocą powyższego kodu. Jest tylko do odczytu, więc pojedynczą kopię globalną można udostępniać w celu jednoczesnego dostępu. Dzięki tej tabeli możesz szybko sprawdzić logarytm liczb całkowitych ₂ , którego tutaj szukamy, dla wszystkich różnych szerokości całkowitych (8, 16, 32 i 64 bity).

Zwróć uwagę, że wpis w tablicy dla 0, jedyna liczba całkowita, dla której pojęcie „najwyższego ustawionego bitu” jest niezdefiniowane, otrzymuje wartość -1. To rozróżnienie jest konieczne do właściwej obsługi górnych słów o wartości 0 w poniższym kodzie. Bez dalszych ceregieli, oto kod dla każdego z różnych prymitywów całkowitych:

wersja ulong (64-bitowa)

/// <summary> Index of the highest set bit in 'v', or -1 for value '0' </summary>
public static int HighestOne(this ulong v)
{
    if ((long)v <= 0)
        return (int)((v >> 57) & 0x40) - 1;      // handles cases v==0 and MSB==63

    int j = /**/ (int)((0xFFFFFFFFU - v /****/) >> 58) & 0x20;
    j |= /*****/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 0x10;
    return j + msb_tab_15[v >> (j + 1)];
}

Wersja uint (32-bitowa)

/// <summary> Index of the highest set bit in 'v', or -1 for value '0' </summary>
public static int HighestOne(uint v)
{
    if ((int)v <= 0)
        return (int)((v >> 26) & 0x20) - 1;     // handles cases v==0 and MSB==31

    int j = (int)((0x0000FFFFU - v) >> 27) & 0x10;
    return j + msb_tab_15[v >> (j + 1)];
}

Różne przeciążenia dla powyższych

public static int HighestOne(long v) => HighestOne((ulong)v);
public static int HighestOne(int v) => HighestOne((uint)v);
public static int HighestOne(ushort v) => msb_tab_15[v >> 1];
public static int HighestOne(short v) => msb_tab_15[(ushort)v >> 1];
public static int HighestOne(char ch) => msb_tab_15[ch >> 1];
public static int HighestOne(sbyte v) => msb_tab_15[(byte)v >> 1];
public static int HighestOne(byte v) => msb_tab_15[v >> 1];

Jest to kompletne, działające rozwiązanie, które zapewnia najlepszą wydajność w .NET 4.7.2 dla wielu alternatyw, które porównałem ze specjalistyczną wiązką do testów wydajności. Niektóre z nich są wymienione poniżej. Parametrami testu była jednorodna gęstość wszystkich 65-bitowych pozycji, tj. 0 ... 31/63 plus wartość 0(co daje wynik -1). Bity poniżej docelowej pozycji indeksu zostały wypełnione losowo. Testy obejmowały tylko x64 , tryb wydania, z włączoną optymalizacją JIT.

To koniec mojej formalnej odpowiedzi tutaj; Poniżej znajduje się kilka przypadkowych uwag i linków do kodu źródłowego dla alternatywnych kandydatów do testów, związanych z testami, które przeprowadziłem w celu sprawdzenia wydajności i poprawności powyższego kodu.

Wersja podana powyżej, oznaczona jako Tab16A, była konsekwentnym zwycięzcą w wielu przebiegach. Tych różnych kandydatów w formie aktywnej pracy / od podstaw można znaleźć tutaj , tutaj i tutaj .

 1 kandydatów.HighestOne_Tab16A 622,496
 2 kandydatów.HighestOne_Tab16C 628,234
 3 kandydatów.HighestOne_Tab8A 649,146
 4 kandydatów.HighestOne_Tab8B 656847
 5 kandydatów.HighestOne_Tab16B 657,147
 6 kandydatów.HighestOne_Tab16D 659,650
 7 _highest_one_bit_UNMANAGED.HighestOne_U 702,900
 8 de_Bruijn.IndexOfMSB 709,672
 9 _old_2.HighestOne_Old2 715,810
10 _test_A.HighestOne8 757,188
11 _stary_1.HighestOne_Stary1 757,925
12 _test_A.HighestOne5 (niebezpieczne) 760,387
13 _test_B.HighestOne8 (niebezpieczne) 763,904
14 _test_A.HighestOne3 (niebezpieczne) 766,433
15 _test_A.HighestOne1 (niebezpieczne) 767,321
16 _test_A.HighestOne4 (niebezpieczne) 771,702
17 _test_B.HighestOne2 (niebezpieczne) 772,136
18 _test_B.HighestOne1 (niebezpieczne) 772,527
19 _test_B.HighestOne3 (niebezpieczne) 774,140
20 _test_A.HighestOne7 (niebezpieczne) 774,581
21 _test_B.HighestOne7 (niebezpieczne) 775,463
22 _test_A.HighestOne2 (niebezpieczne) 776,865
23 kandydatów.HighestOne_NoTab 777,698
24 _test_B.HighestOne6 (niebezpieczne) 779,481
25 _test_A.HighestOne6 (niebezpieczne) 781,553
26 _test_B.HighestOne4 (niebezpieczne) 785,504
27 _test_B.HighestOne5 (niebezpieczne) 789,797
28 _test_A.HighestOne0 (niebezpieczne) 809,566
29 _test_B.HighestOne0 (niebezpieczne) 814,990
30 _highest_one_bit.HighestOne 824,345
30 _bitarray_ext.RtlFindMostSsequantBit 894,069
31 kandydatów, Najwyższa Nieważna 898,865

Godne uwagi jest to, że straszna wydajność ntdll.dll!RtlFindMostSignificantBitvia P / Invoke:

[DllImport("ntdll.dll"), SuppressUnmanagedCodeSecurity, SecuritySafeCritical]
public static extern int RtlFindMostSignificantBit(ulong ul);

To naprawdę szkoda, ponieważ oto cała rzeczywista funkcja:

    RtlFindMostSignificantBit:
        bsr rdx, rcx  
        mov eax,0FFFFFFFFh  
        movzx ecx, dl  
        cmovne      eax,ecx  
        ret

Nie mogę sobie wyobrazić słabej wydajności wynikającej z tych pięciu linii, więc należy winić kary za zarządzane / natywne przejście. Byłem również zaskoczony, że testy naprawdę faworyzowały 32KB (i 64KB) short(16-bitowe) tablice bezpośredniego wyszukiwania w porównaniu z 128-bajtowymi (i 256-bajtowymi) byte(8-bitowymi) tablicami wyszukiwania. Wydawało mi się, że poniższe elementy będą bardziej konkurencyjne w przypadku wyszukiwania 16-bitowego, ale ta ostatnia konsekwentnie przewyższała to:

public static int HighestOne_Tab8A(ulong v)
{
    if ((long)v <= 0)
        return (int)((v >> 57) & 64) - 1;

    int j;
    j =  /**/ (int)((0xFFFFFFFFU - v) >> 58) & 32;
    j += /**/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 16;
    j += /**/ (int)((0x000000FFU - (v >> j)) >> 60) & 8;
    return j + msb_tab_8[v >> j];
}

Ostatnią rzeczą, na którą zwróciłem uwagę, było to, że byłem zszokowany, że moja metoda deBruijn nie wypadła lepiej. To jest metoda, której wcześniej używałem powszechnie:

const ulong N_bsf64 = 0x07EDD5E59A4E28C2,
            N_bsr64 = 0x03F79D71B4CB0A89;

readonly public static sbyte[]
bsf64 =
{
    63,  0, 58,  1, 59, 47, 53,  2, 60, 39, 48, 27, 54, 33, 42,  3,
    61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22,  4,
    62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21,
    56, 45, 25, 31, 35, 16,  9, 12, 44, 24, 15,  8, 23,  7,  6,  5,
},
bsr64 =
{
     0, 47,  1, 56, 48, 27,  2, 60, 57, 49, 41, 37, 28, 16,  3, 61,
    54, 58, 35, 52, 50, 42, 21, 44, 38, 32, 29, 23, 17, 11,  4, 62,
    46, 55, 26, 59, 40, 36, 15, 53, 34, 51, 20, 43, 31, 22, 10, 45,
    25, 39, 14, 33, 19, 30,  9, 24, 13, 18,  8, 12,  7,  6,  5, 63,
};

public static int IndexOfLSB(ulong v) =>
    v != 0 ? bsf64[((v & (ulong)-(long)v) * N_bsf64) >> 58] : -1;

public static int IndexOfMSB(ulong v)
{
    if ((long)v <= 0)
        return (int)((v >> 57) & 64) - 1;

    v |= v >> 1; v |= v >> 2;  v |= v >> 4;   // does anybody know a better
    v |= v >> 8; v |= v >> 16; v |= v >> 32;  // way than these 12 ops?
    return bsr64[(v * N_bsr64) >> 58];
}