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

119

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).

Zxaos
źródło
jest tu kilka implementacji: graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightLinear (Edycja: po ponownym przeczytaniu twojego pytania, zdaję sobie sprawę, że powyższy link służy do znalezienia ustawionego bitu znajdującego się najbardziej po prawej stronie, a nie tak po lewej, jak potrzebujesz, chociaż bez poczucie rozmiaru słowa, trudno odpowiedzieć)
wydający
2
Zobacz „ Algorytmy liczby wiodących zer ” w Hacker's Delight .
Darius Bacon
To liczy zera po prawej stronie ; pytanie dotyczyło zer po lewej stronie. Przynajmniej w szybkim przejrzeniu go tam nie widzę.
Darius Bacon
2
czy chcesz konkretnie bitu o numerze „n”, czy wystarczyłoby 2 ^ n?
Alnitak
1
Spójrz na algorytmy „Log Base 2” - jak mówi Anderson w artykule: „Podstawa logu 2 liczby całkowitej jest taka sama, jak pozycja najwyższego zestawu bitów (lub najbardziej znaczącego zestawu bitów, MSB)”
Michael Burr

Odpowiedzi:

64

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? )

ephemient
źródło
5
MSVC będzie miał _BitScanReverse
zapadka freak
1
Zachowanie niezdefiniowane na zero pozwala im na kompilację do pojedynczej instrukcji BSR na x86, nawet jeśli LZCNT nie jest dostępny. Jest to duża zaleta w przypadku __builtin_ctzover ffs, który kompiluje się do BSF i CMOV, aby obsłużyć przypadek wejściowy równy zero. Na architekturach bez wystarczająco krótkiej implementacji (np. Stary ARM bez clzinstrukcji), gcc emituje wywołanie funkcji pomocniczej libgcc.
Peter Cordes,
41

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.

Timday
źródło
4
W rzeczywistości ta instrukcja jest zwykle mikrokodowana w pętlę i jest raczej powolna.
rlbond
2
Który ? BSR czy CNTLZ? Kiedy czytałem wspomniany powyżej x86-timing.pdf, BSR działa wolno tylko na Pentiumach Netburst. Jednak nic nie wiem o PowerPC.
dzień
5
... OK, po bliższym przyjrzeniu się stwierdzimy, że „BSR jest szybki tylko na procesorach P3 / Pentium-M / Core2 x86”. Wolno na Netburst i AMD.
dzień
1
Tylko jedno ostrzeżenie: ostatnie dwa linki są martwe.
Baum mit Augen
2
@rlbond: huh, BSR na P4 Prescott to 2 uops z opóźnieniem 16 cykli (!), z jednym na przepustowość 4c. Ale we wcześniejszym Netburst opóźnienie to tylko 4 cykle (nadal 2 uops) i jeden na przepustowość 2c. (źródło: agner.org/optimize ). Na większości procesorów ma również zależność od swojego wyjścia, której gcc nie bierze pod uwagę (gdy wejście ma wartość zero, faktycznym zachowaniem jest pozostawienie miejsca docelowego niezmienionego). Może to prowadzić do problemów, takich jak stackoverflow.com/questions/25078285/… . IDK, dlaczego gcc przegapił BSR podczas naprawiania tego.
Peter Cordes
38

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.

Quinn Taylor
źródło
2
@Johan Przejście przez debugera może pomóc wyjaśnić, dlaczego pętla została zakończona. Zasadniczo jest to ``, ponieważ wyrażenie w warunku zwraca się do 0 (co jest traktowane jako fałsz), gdy ostatni 1 bit zostanie przesunięty w prawo.
Quinn Taylor
2
Niezły pomysł, żeby wykorzystać taki efekt końcowy :)
Johan,
6
uwaga: musi być bez znaku, dla liczb całkowitych ze znakiem przesunięcie w prawo nie powiedzie się dla liczb ujemnych.
Xantix
2
Xantix: Zmiana w C / C ++ jest logiczną zmianą, więc działa dobrze. W przypadku języka Java, JavaScript lub D musisz użyć logicznego operatora przesunięcia >>>. Plus prawdopodobnie komparator != 0i nieokreślona liczba nawiasów.
Chase
8
@Chase: Nie, nie jest. To logiczna zmiana dla niepodpisanych . Dla podpisał , to może być lub nie być logiczną shift (i to zwykle arytmetyczny, w rzeczywistości).
Tim Čas
17

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];
}
Protagonista
źródło
25
7-bitowe przesunięcia, 5 lub instrukcje, wielokrotność i potencjalny brak pamięci podręcznej. :) Czy wykonałeś testy porównawcze, czy spojrzałeś na wygenerowany asembler? Może to skończyć się dość wolno, w zależności od tego, ile z tego kompilator może wyeliminować.
jalf
5
Jestem tu nowy. Nie mam negatywnych głosów, chłopaki. Jako jedyną odpowiedź podałem kod źródłowy, który faktycznie działa.
Protagonista
9
Prawdopodobnie „brak pamięci podręcznej” jest prawdopodobnie spowodowany tym, że kod wymaga dostępu do jego tabeli przeglądowej. Jeśli ta tabela nie zostanie zapisana w pamięci podręcznej, gdy zostanie wywołana, nastąpi wstrzymanie podczas pobierania. Może to spowodować, że wydajność w najgorszym przypadku będzie znacznie gorsza niż w rozwiązaniach bez LUT.
odpocząć
13
nie o to chodzi. Używa o wiele więcej pamięci podręcznej danych niż to konieczne (nawet więcej niż jeden wiersz pamięci podręcznej) i więcej pamięci podręcznej instrukcji niż to konieczne. Prawdopodobnie otrzymasz chybienia w pamięci podręcznej, których można było uniknąć przy pierwszym wywołaniu funkcji, i spowoduje to zanieczyszczenie pamięci podręcznej bardziej niż to konieczne, więc po wywołaniu inny kod może napotkać więcej błędów niż to konieczne. LUT często nie są warte zachodu, ponieważ pomyłki w pamięci podręcznej są drogie. Ale powiedziałem tylko, że to jest coś, co chciałbym przetestować, zanim stwierdziłem, że jest „szybki jak błyskawica”. Nie żeby to był na pewno problem.
jalf
6
Tabela ma 32 wpisy, a każda wartość jest <255 (127), więc zdefiniuj tabelę jako typ bez znaku, a zmieści się w pojedynczej 32-bajtowej linii pamięci podręcznej L1. A całość mieści się w dwóch liniach pamięci podręcznej.
ChuckCottrill,
16

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

SPWorley
źródło
2
Tak. A gcc zrobi nieprzyjemne rzeczy z takim kodem z -O2 ze względu na optymalizację aliasingu typów.
MSN
4
rzutowanie między liczbami całkowitymi a zmiennoprzecinkowymi może być zaskakująco drogie na procesorach x86
jalf
1
Tak, koszty FPU są wysokie. Jednak faktyczne pomiary czasu pokazały, że jest to szybsze niż wszystkie operacje bitowe, a zwłaszcza jakiekolwiek pętle. Wypróbuj to i weź najszybszy jest zawsze najlepszą radą. Nie miałem jednak problemu z GCC i -O2 z tym.
SPWorley
1
Czy nie jest to niezdefiniowane zachowanie (odczytywanie wartości przez wskaźnik niekompatybilnego typu)?
dreamlax
3
Hacker's Delight wyjaśnia, jak poprawić błąd w 32-bitowych liczbach zmiennoprzecinkowych w 5-3 Counting Leading 0's. Oto ich kod, który używa anonimowej unii do nakładania się asFloat i asInt: k = k & ~ (k >> 1); asFloat = (float) k + 0.5f; n = 158 - (asInt >> 23); (i tak, zależy to od zachowania zdefiniowanego w implementacji)
D Coetzee,
11

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.

Kaz
źródło
9
Nie mówię, że to nie jest dobre, ale Twój program testowy testuje tutaj tylko tę samą liczbę, która po 2-3 iteracjach ustawia predyktory gałęzi na ich ostateczną pozycję, a następnie wykona doskonałe przewidywania gałęzi. Dobrą rzeczą jest to, że przy całkowicie losowym rozkładzie połowa liczb będzie miała prognozę bliską doskonałej, a mianowicie bit63.
Surt
8

Co powiesz na

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

?

Marco Amagliani
źródło
To jest powolna (ale bardziej przenośna) wersja tej odpowiedzi , która wyjaśnia, dlaczego działa.
Peter Cordes
6
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

rlbond
źródło
7
Powyższy kod nie odpowiada na pytanie. Zwraca liczbę całkowitą bez znaku, w której najbardziej znaczący bit w x pozostaje włączony, a wszystkie pozostałe bity są wyłączone. Chodziło o zwrócenie pozycji najważniejszego na wędzidle.
Protagonista
3
Następnie możesz użyć podejścia sekwencyjnego De Bruijn, aby znaleźć indeks ustawionego bitu. :-)
R .. GitHub STOP HELPING ICE
5
@ Protagonista, powiedział w komentarzu, który albo wystarczy.
rlbond
Ten (z tej samej strony) zrobiłby to, czego potrzebujesz, ale wymaga dodatkowej funkcji. agregate.org/MAGIC/#Log2%20of%20an%20Integer
Quinn Taylor
1
BSR działa szybko na procesorach Intela przynajmniej od czasu Core2. LZCNT jest szybki na procesorach AMD i gcc używa go, __builtin_clzjeśli jest włączony z -march=nativeczy czymś (ponieważ jest szybki na każdym procesorze, który go obsługuje). Nawet na procesorach, takich jak rodzina AMD Bulldozer, gdzie BSR jest „wolny”, nie jest aż tak wolny: 7 m-operacji z 4-taktowymi opóźnieniami i jedną przepustowością na 4c. Na Atom BSR działa bardzo wolno: 16 cykli. Na Silvermont jest to 10 uopsów z 10 cyklami latencji. To może być nieco mniejsze opóźnienie niż BSR na Silvermont, ale IDK.
Peter Cordes
6

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;
}
Josh
źródło
6

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));
Noldorin
źródło
Aby rozwinąć: standardowe rozwiązanie pętli (przesunięcie w lewo i sprawdzenie MSB) jest prawdopodobnie najbardziej czytelne. Jak we wszystkich przypadkach związanych z kręceniem bitów, szybkości ASM nie można pokonać, chociaż nie ma sensu zaśmiecać kodu, chyba że jest to konieczne. Hacki są rozwiązaniem pośrednim - idź w jedną lub drugą stronę.
Noldorin
Powiedziałbym, że zrobienie logarytmu byłoby idealnie czytelnym rozwiązaniem (sprawdź wygenerowany asm, aby zobaczyć, czy kompilator może go zoptymalizować, aby użyć tej instrukcji asm)
jalf
Czasami wbudowane rozwiązanie ASM jest wolniejsze, w zależności od implementacji w mikrokodzie procesora.
rlbond
5
@rlbound: Nie mogę w to uwierzyć, chociaż mogę się mylić. Na każdym nowoczesnym procesorem można by pomyśleć, że to tłumaczone na jednej instrukcji ....
noldorinski
3
@Noldorin jest trochę za późno, ale .. Z definicji jest to pojedyncza instrukcja, ale jeśli jest mikrokodowana, jak sugeruje rlbond, wtedy ta pojedyncza instrukcja może wewnętrznie zdekodować do całej paczki µops. Zwykle ma to miejsce w przypadku mikroarchitektur AMD i Intel Atom, ale w normalnych mikroarchitekturach Intela jest to pojedyncza operacja do końca.
harold
4

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;
}
dangermouse
źródło
4

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;
}

źródło
4
Proszę rozważyć nie używanie ALL_CAPS dla typedefs, ani niczego poza makrami preprocesora. To jest powszechnie przyjęta konwencja.
underscore_d
4

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.

VoidStar
źródło
1
Niektóre odpowiedzi są bezgałęziowe, ale prawdopodobnie zostanie to skompilowane z gałęziami warunkowymi. Czy testowałeś tylko te same wartości wielokrotnie, czy był to prosty wzór, czy coś takiego? Błędne przewidywania branżowe zabijają wydajność. stackoverflow.com/questions/11227809/…
Peter Cordes
3

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;
}
David C. Rankin
źródło
Nie było int r; pierwotnie zdefiniowany nad #ifdef BUILD_64flagą? W takim przypadku nie będzie potrzebna redefinicja w ramach warunku.
David C. Rankin,
3

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”)


źródło
Jeśli napiszesz to z operatorem trójargumentowym ( msb += (n>>msb) ? step : -step;), prawdopodobnie więcej kompilatorów utworzy asm bez gałęzi, unikając błędnych przewidywań gałęzi na każdym kroku ( stackoverflow.com/questions/11227809/ ... ).
Peter Cordes,
3

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ć 1 , ż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 2 (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.

1 Argument wygląda tak (szkic): Niech n będzie liczbą bitów (szerokość bitu). Łącznie jest 2 n 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 n , 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 n

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.

Finnegan
źródło
2
Nie wydaje mi się, aby było to uczciwe założenie, że dane wejściowe do funkcji msb mają tendencję do równomiernego rozłożenia. W praktyce te dane wejściowe są zwykle rejestrami przerwań lub tablicami bitowymi lub inną strukturą danych z nierównomiernie rozłożonymi wartościami. Dla uczciwego punktu odniesienia myślę, że bezpieczniej jest założyć, że wyniki (a nie nakłady) będą równomiernie rozłożone.
johnwbyrd
3

dał 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 nastę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

Jonathan Mee
źródło
Nie, _BitScanReversezwraca 0 tylko wtedy, gdy dane wejściowe to 0. Jest to podobne do BSRinstrukcji x86 , która ustawia ZF tylko na podstawie wejścia, a nie wyjścia. Ciekawe, że MS określa dokumenty jako pozostające w stanie indexnieustawionym, gdy nie 1znaleziono żadnego bitu; który również pasuje do zachowania asm x86 programu bsr. (AMD dokumentuje to jako pozostawienie niezmienionego rejestru docelowego na src = 0, ale Intel po prostu podaje niezdefiniowane dane wyjściowe, mimo że ich procesory implementują zachowanie niezmienione). Jest to w przeciwieństwie do x86 lzcnt, co oznacza, 32że nie znaleziono.
Peter Cordes
@PeterCordes _BitScanReverseużywa indeksowania od zera, więc jeśli nwynosi 1, to indeks ustawionego bitu wynosi w rzeczywistości 0. Niestety, jak mówisz, jeśli nwynosi 0, to na wyjściu również jest 0 :( Oznacza to, że nie ma sposobu, aby użyć powrotu do rozróżnić n1 lub 0. Właśnie to próbowałem przekazać. Czy uważasz, że jest lepszy sposób, aby to powiedzieć?
Jonathan Mee
Myślę, że mówisz o tym, jak to się układa Index. To nie jest powrót wartość. Zwraca wartość logiczną, która jest fałszywa, jeśli wartość wejściowa wynosiła zero (i dlatego Index jest przekazywany przez odwołanie, a nie zwracany normalnie). godbolt.org/g/gQKJdE . I sprawdziłem: pomimo sformułowania dokumentów MS, _BitScanReversenie pozostawia indeksu nieustawionego n==0: po prostu dostajesz jakąkolwiek wartość w rejestrze, którego akurat używał. (Który w twoim przypadku był prawdopodobnie tym samym rejestrem, którego używał Indexpóźniej, co prowadzi do zobaczenia a 0).
Peter Cordes,
To pytanie nie jest oznaczone jako c ++.
technozaur
@technosaurus Dzięki, zapomniałem o sobie. Biorąc pod uwagę, że pytanie brzmi C, które faktycznie mieliśmy log2od C99.
Jonathan Mee
2

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--;
}
Wasilij
źródło
Co masz na myśli zamiana na ciąg? Definicja ffs przyjmuje int i zwraca int. Gdzie byłaby konwersja? A czemu miałaby służyć konwersja, gdybyśmy szukali bitów w słowie?
dreamlax
Nie wiedziałem o tej funkcji.
Vasil
8Powinno być CHAR_BIT. Jest to bardzo mało prawdopodobne, aby był to najszybszy sposób, ponieważ przy wyjściu z pętli wystąpi błędne przewidywanie gałęzi, chyba że jest to używane wielokrotnie z tym samym wejściem. Ponadto w przypadku małych wejść (dużo zer) musi dużo zapętlić. Jest to sposób zastępczy, którego można użyć jako łatwej do zweryfikowania wersji w teście jednostkowym w celu porównania ze zoptymalizowanymi wersjami.
Peter Cordes
2

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.

JonesD
źródło
1

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);
}
ChuckCottrill
źródło
1

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];
}
greggo
źródło
1

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óż.

Harry Svensson
źródło
Pisanie zmian 1<<kjest miłym akcentem. A co z maskami? (1 << (1<<k-1)-1<< (1<<k-1)? ( most optimal? Porównujesz superlatyw?)
siwobrody
@greybeard Jeśli spojrzysz na edycje tego pytania, zobaczysz, kiedy dodałem „optymalną” część. Zapomniałem go usunąć, ponieważ zmieniłem odpowiedź. Również nie jestem pewien, dlaczego mówimy o tych masek? (Jakie maski? Nie śledzę cię)
Harry Svensson
( Maska (bit) to wartości używane do wybiórczego wybierania / usuwania bitów / używane w &i &~.) Możesz zastąpić stałe szesnastkowe takimi jak ((type)1<<(1<<k))-1<<(1<<k).
siwobrody
No tak, używam masek, zupełnie o tym zapomniałem. Odpowiedziałem na to kilka miesięcy temu ... - Hmmm, cóż, ponieważ jest oceniany w czasie kompilacji, mówię, że jest to odpowiednik wartości szesnastkowych. Jednak jeden jest tajemniczy, a drugi szesnastkowy.
Harry Svensson
0

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

jemin
źródło
uhhhhh. co? jak to działa? czy jest w jakikolwiek sposób przenośny?
underscore_d
Kody w oknie są przenośne. Funkcja FYL2X () jest instrukcją fpu, ale można ją przenieść i można ją znaleźć w niektórych bibliotekach FPU / matematycznych.
jemin
@underscore_d Działa, ponieważ liczby zmiennoprzecinkowe są znormalizowane ... konwersja na podwójne przesuwa bity mantysy w celu wyeliminowania zera wiodącego, a ten kod wyodrębnia wykładnik i dostosowuje go, aby określić liczbę przesuniętych bitów. Z pewnością nie jest niezależny od architektury, ale prawdopodobnie będzie działać na każdym napotkanym komputerze.
Jim Balter,
To jest alternatywna wersja tej odpowiedzi. Zobacz tam komentarze dotyczące wydajności i przenośności. (W szczególności nieprzenośność rzutowania wskaźników dla punning typu). Używa matematyki adresowej tylko do przeładowania wysokich 32 bitów double, co jest prawdopodobnie dobre, jeśli faktycznie przechowuje / przeładowuje zamiast pisania kalambur w inny sposób, np. z movqinstrukcją, jaką możesz dostać tutaj na x86.
Peter Cordes
Zwróć też uwagę na mój [komentarz do tej odpowiedzi], w którym ostrzegam, że ta metoda daje błędną odpowiedź dla wartości w (przynajmniej) zakresie [7FFFFFFFFFFFFE00 - 7FFFFFFFFFFFFFFF].
Glenn Slayden
0

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 2 , 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];
}

Dużo dyskutuje się o tym, jak doskonałe i świetne metody deBruijna w tym pytaniu SO i zwykle się z tym zgadzam. Spekuluję, że chociaż zarówno metoda deBruijn, jak i metoda tabeli bezpośredniego wyszukiwania (które okazały się najszybsze), obie muszą przeszukiwać tabelę i obie mają bardzo minimalne rozgałęzienia, tylko deBruijn ma 64-bitową operację mnożenia. Przetestowałem tylko IndexOfMSBfunkcje tutaj - nie deBruijn - IndexOfLSBale spodziewam się, że ten drugi będzie miał znacznie większe szanse, ponieważ ma o wiele mniej operacji (patrz powyżej) i prawdopodobnie nadal będę go używać w LSB.

Glenn Slayden
źródło
1
Pamięć podręczna L1D na nowoczesnych procesorach x86 ma tylko 32 kB. Duży LUT może być gorszy niż mały LUT, chyba że wielokrotnie używasz tych samych wartości. Jeśli nie, będziesz często spóźniać się z pamięci podręcznej.
Peter Cordes,
0

Moja skromna metoda jest bardzo prosta:

MSB (x) = INT [Log (x) / Log (2)]

Tłumaczenie: MSB x jest wartością całkowitą (logarytm z podstawy x podzielony przez logarytm z podstawy 2).

Można to łatwo i szybko dostosować do dowolnego języka programowania. Wypróbuj na swoim kalkulatorze i przekonaj się, że to działa.

SpartanWar
źródło
To działa, jeśli wszystko, co Cię interesuje, to wydajność programisty. Jeśli zależy Ci na wydajności czasu działania, potrzebujesz alternatywnego algorytmu.
Mikko Rantalainen
Może się to nie powieść z powodu błędu zaokrąglenia. Na przykład w CPython 2 i 3 int(math.log((1 << 48) - 1) / math.log(2))to 48.
benrg
0

Oto szybkie rozwiązanie dla C, które działa w GCC i Clang ; gotowy do skopiowania i wklejenia.

#include <limits.h>

unsigned int fls(const unsigned int value)
{
    return (unsigned int)1 << ((sizeof(unsigned int) * CHAR_BIT) - __builtin_clz(value) - 1);
}

unsigned long flsl(const unsigned long value)
{
    return (unsigned long)1 << ((sizeof(unsigned long) * CHAR_BIT) - __builtin_clzl(value) - 1);
}

unsigned long long flsll(const unsigned long long value)
{
    return (unsigned long long)1 << ((sizeof(unsigned long long) * CHAR_BIT) - __builtin_clzll(value) - 1);
}

I trochę ulepszona wersja dla C ++ .

#include <climits>

constexpr unsigned int fls(const unsigned int value)
{
    return (unsigned int)1 << ((sizeof(unsigned int) * CHAR_BIT) - __builtin_clz(value) - 1);
}

constexpr unsigned long fls(const unsigned long value)
{
    return (unsigned long)1 << ((sizeof(unsigned long) * CHAR_BIT) - __builtin_clzl(value) - 1);
}

constexpr unsigned long long fls(const unsigned long long value)
{
    return (unsigned long long)1 << ((sizeof(unsigned long long) * CHAR_BIT) - __builtin_clzll(value) - 1);
}

Kod zakłada, że valuetak nie będzie 0. Jeśli chcesz zezwolić na 0, musisz to zmodyfikować.

BEZ NAZWY
źródło
0

Zakładam, że twoje pytanie dotyczy liczby całkowitej (zwanej poniżej v), a nie liczby całkowitej bez znaku.

int v = 612635685; // whatever value you wish

unsigned int get_msb(int v)
{
    int r = 31;                         // maximum number of iteration until integer has been totally left shifted out, considering that first bit is index 0. Also we could use (sizeof(int)) << 3 - 1 instead of 31 to make it work on any platform.

    while (!(v & 0x80000000) && r--) {   // mask of the highest bit
        v <<= 1;                        // multiply integer by 2.
    }
    return r;                           // will even return -1 if no bit was set, allowing error catch
}

Jeśli chcesz, aby działało bez uwzględnienia znaku, możesz dodać dodatkowe 'v << = 1;' przed pętlą (i odpowiednio zmień wartość r na 30). Daj mi znać, jeśli o czymś zapomniałem. Nie testowałem tego, ale powinno działać dobrze.

Antonin GAVREL
źródło
v <<= 1jest niezdefiniowanym zachowaniem (UB), gdy v < 0.
chux - Przywróć Monikę
0x8000000, może masz na myśli dodatkowe 0.
MM