Trouver bit de poids fort (le plus à gauche) qui est définie dans un tableau de bits

tl:dr; Pour 32 bits, utilisez de Bruijn multiplication.

C'est le "le plus rapide" portable algorithme. Il est beaucoup plus rapide et plus correcte que toutes les autres portable 32 bits MSB algorithmes dans ce fil.

La de Bruijn algorithme renvoie également à un résultat correct lorsque l'entrée est égale à zéro. L' __builtin_clozapine et _BitScanReverse instructions retourner des résultats incorrects lorsque l'entrée est égale à zéro.

Sur Windows x86-64, de Bruijn multiplication s'exécute à une vitesse comparable à l'équivalent (imparfait) fonction de Windows, avec une différence de performance de seulement 3%.

Voici le code.

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

    v |= v >> 1; //first round down to one less than a power of 2
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;

    return MultiplyDeBruijnBitPosition[( u32 )( v * 0x07C4ACDDU ) >> 27];
}

Toutes les autres réponses dans ce thread, soit courir beaucoup plus de mal que leurs auteurs suggèrent, ou de ne pas calculer correctement les résultats, ou les deux. Nous allons comparer tous et de vérifier qu'ils font ce qu'ils prétendent faire.

Ici est un simple C++11 harnais pour tester toutes ces implémentations. Il compile propre sur Visual Studio, mais devrait fonctionner sur tous les compilateurs modernes. Il vous permet d'exécuter le test en mode de performance (bVerifyResults = false) et dans le mode de vérification (bVerifyResults = true).

Voici les résultats en mode de vérification:

Verification failed for msbNative64: input was 0; output was 818af060; expected 0
Verification failed for msbFfs: input was 22df; output was 0; expected d
Verification failed for msbPerformanceJunkie32: input was 0; output was ffffffff; expected 0
Verification failed for msbNative32: input was 0; output was 9ab07060; expected 0

La performance "junkie" et Microsoft native implémentations de faire des choses différentes lorsque l'entrée est égale à zéro. msbPerformanceJunkie32 produit de -1, et Microsoft _BitScanReverse produit un nombre aléatoire, compatible avec le matériel sous-jacent de l'instruction. Aussi la msbPerformanceJunkie32 mise en œuvre produit un résultat qui est désactivée par celui de toutes les autres réponses.

Voici les résultats en mode performance, en cours d'exécution sur mon i7-4600 portables, compilé en mode release:

msbLoop64 took 2.56751 seconds               
msbNative64 took 0.222197 seconds            

msbLoop32 took 1.43456 seconds               
msbFfs took 0.525097 seconds                 
msbPerformanceJunkie32 took 1.07939 seconds  
msbDeBruijn32 took 0.224947 seconds          
msbNative32 took 0.218275 seconds            

La de Bruijn version beats les autres implémentations profondément parce qu'il est dépourvu de branches, et par conséquent, il fonctionne bien contre les entrées qui produisent une répartie uniformément ensemble de sorties. Toutes les autres versions sont plus lents contre l'arbitraire des intrants en raison des pénalités de la branche, les erreurs de prédiction sur les Processeurs modernes. Le smbFfs fonction produit des résultats incorrects de sorte qu'il peut être ignoré.

Certaines implémentations de travail sur 32 bits entrées, et un peu de travail sur 64 bits entrées. Un modèle va nous aider à comparer des pommes avec des pommes, quelle que soit la taille de saisie.

Voici le code. Téléchargez et exécutez les points de repère vous-même si vous le souhaitez.

#include <iostream>
#include <chrono>
#include <random>
#include <cassert>
#include <string>
#include <limits>
#ifdef _MSC_VER
#define MICROSOFT_COMPILER 1
#include <intrin.h>
#endif //_MSC_VER
const int iterations = 100000000;
bool bVerifyResults = false;
std::random_device rd;
std::default_random_engine re(rd());
typedef unsigned int u32;
typedef unsigned long long u64;
class Timer
{
public:
Timer() : beg_(clock_::now()) {}
void reset() {
beg_ = clock_::now();
}
double elapsed() const {
return std::chrono::duration_cast<second_>
(clock_::now() - beg_).count();
}
private:
typedef std::chrono::high_resolution_clock clock_;
typedef std::chrono::duration<double, std::ratio<1> > second_;
std::chrono::time_point<clock_> beg_;
};
unsigned int msbPerformanceJunkie32(u32 x)
{
static const unsigned int bval[] =
{ 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4 };
unsigned int r = 0;
if (x & 0xFFFF0000) {
r += 16 / 1;
x >>= 16 / 1;
}
if (x & 0x0000FF00) {
r += 16 / 2;
x >>= 16 / 2;
}
if (x & 0x000000F0) {
r += 16 / 4;
x >>= 16 / 4;
}
return r + bval[x];
}
#define FFS(t)  \
{ \
register int n = 0; \
if (!(0xffff & t)) \
n += 16; \
if (!((0xff << n) & t)) \
n += 8; \
if (!((0xf << n) & t)) \
n += 4; \
if (!((0x3 << n) & t)) \
n += 2; \
if (!((0x1 << n) & t)) \
n += 1; \
return n; \
}
unsigned int msbFfs32(u32 x)
{
FFS(x);
}
unsigned int msbLoop32(u32 x)
{
int r = 0;
if (x < 1) return 0;
while (x >>= 1) r++;
return r;
}
unsigned int msbLoop64(u64 x)
{
int r = 0;
if (x < 1) return 0;
while (x >>= 1) r++;
return r;
}
u32 msbDeBruijn32(u32 v)
{
static const int MultiplyDeBruijnBitPosition[32] =
{
0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};
v |= v >> 1; //first round down to one less than a power of 2
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
return MultiplyDeBruijnBitPosition[(u32)(v * 0x07C4ACDDU) >> 27];
}
#ifdef MICROSOFT_COMPILER
u32 msbNative32(u32 val)
{
unsigned long result;
_BitScanReverse(&result, val);
return result;
}
u32 msbNative64(u64 val)
{
unsigned long result;
_BitScanReverse64(&result, val);
return result;
}
#endif //MICROSOFT_COMPILER
template <typename InputType>
void test(unsigned int msbFunc(InputType),
const std::string &name,
const std::vector< InputType > &inputs,
std::vector< unsigned int > &results,
bool bIsReference = false
)
{
if (bIsReference)
{
int i = 0;
for (int i = 0; i < iterations; i++)
results[i] = msbFunc(inputs[i]);
}
InputType result;
if (bVerifyResults)
{
bool bNotified = false;
for (int i = 0; i < iterations; i++)
{
result = msbFunc(inputs[i]);
if ((result != results[i]) && !bNotified)
{
std::cout << "Verification failed for " << name << ": "
<< "input was " << std::hex << inputs[i]
<< "; output was " << result
<< "; expected " << results[i]
<< std::endl;
bNotified = true;
}
}
}
else
{
Timer t;
for (int i = 0; i < iterations; i++)
{
result = msbFunc(inputs[i]);
}
double elapsed = t.elapsed();
if ( !bIsReference )
std::cout << name << " took " << elapsed << " seconds" << std::endl;
if (result == -1.0f)
std::cout << "this comparison only exists to keep the compiler from " <<
"optimizing out the benchmark; this branch will never be called";
}
}
void main()
{
std::uniform_int_distribution <u64> dist64(0,
std::numeric_limits< u64 >::max());
std::uniform_int_distribution <u32> shift64(0, 63);
std::vector< u64 > inputs64;
for (int i = 0; i < iterations; i++)
{
inputs64.push_back(dist64(re) >> shift64(re));
}
std::vector< u32 > results64;
results64.resize(iterations);
test< u64 >(msbLoop64, "msbLoop64", inputs64, results64, true);
test< u64 >(msbLoop64, "msbLoop64", inputs64, results64, false);
#ifdef MICROSOFT_COMPILER
test< u64 >(msbNative64, "msbNative64", inputs64, results64, false);
#endif //MICROSOFT_COMPILER
std::cout << std::endl;
std::uniform_int_distribution <u32> dist32(0,
std::numeric_limits< u32 >::max());
std::uniform_int_distribution <u32> shift32(0, 31);
std::vector< u32 > inputs32;
for (int i = 0; i < iterations; i++)
inputs32.push_back(dist32(re) >> shift32(re));
std::vector< u32 > results32;
results32.resize(iterations);
test< u32 >(msbLoop32, "msbLoop32", inputs32, results32, true);
test< u32 >(msbLoop32, "msbLoop32", inputs32, results32, false);
test< u32 >(msbFfs32, "msbFfs", inputs32, results32, false);
test< u32 >(msbPerformanceJunkie32, "msbPerformanceJunkie32",
inputs32, results32, false);
test< u32 >(msbDeBruijn32, "msbDeBruijn32", inputs32, results32, false);
#ifdef MICROSOFT_COMPILER
test< u32 >(msbNative32, "msbNative32", inputs32, results32, false);
#endif //MICROSOFT_COMPILER
}

Il y a plusieurs façons de le faire, et de la performance relative des différentes implémentations est un peu dépendant de la machine (il m'arrive d'avoir comparé cela à une certaine mesure, pour un but similaire). Sur certaines machines, il y a même un construit-dans l'instruction de ce type (utilisez une si disponible et la portabilité peut être traitée).

Vérifier certaines implémentations ici (sous “entier logarithme de base 2”). Si vous utilisez GCC, découvrez les fonctions __builtin_clz et __builtin_clzl (qui ne ce pour les non-zéro entiers non signés et non signés longs, respectivement). Le “clozapine” signifie “compter les zéros non significatifs”, qui est encore une autre façon de décrire le même problème.

Bien sûr, si votre tableau de bits ne rentre pas dans une machine adaptée mot, vous avez besoin pour itérer sur les mots dans le tableau pour trouver le premier non nul mot et ensuite effectuer ce calcul uniquement sur ce mot.

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

J'ai travaillé avec un certain nombre de fonctions pour obtenir le bit le plus significatif, mais des problèmes se posent généralement se déplacer entre 32 bits et 64 bits des nombres ou en se déplaçant entre x86_64 et x86 boîtes. Les fonctions __builtin_clz, __builtin_clzl et __builtin_clzll fonctionnent bien pour les architectures 32 et 64 bits des nombres et à travers x86_64 et des machines x86. Cependant, trois fonctions sont nécessaires. J'ai trouvé un simple MSB, qui s'appuie sur le bouton droit de la maj qui va gérer tous les cas pour les nombres positifs. Au moins pour l'utilisation que j'allais en faire, il a réussi là où d'autres ont échoué:

int
getmsb (unsigned long long x)
{
int r = 0;
if (x < 1) return 0;
while (x >>= 1) r++;
return r;
}

Par la désignation d'entrée comme unsigned long long il peut gérer tout le nombre de classes à partir de unsigned char à unsigned long long et compte tenu de la définition de la norme, il est compatible pour x86_64 et x86 construit. Le cas pour 0 est défini pour revenir 0, mais peut être modifiée si besoin. Un simple test et de sortie sont:

int
main (int argc, char *argv[]) {
unsigned char c0 = 0;
unsigned char c = 216;
unsigned short s = 1021;
unsigned int ui = 32768;
unsigned long ul = 3297381253;
unsigned long long ull = 323543844043;
int i = 32767;
printf ("  %16u  MSB : %d\n", c0, getmsb (c0));
printf ("  %16u  MSB : %d\n", c, getmsb (c));
printf ("  %16u  MSB : %d\n", s, getmsb (s));
printf ("  %16u  MSB : %d\n", i, getmsb (i));
printf ("  %16u  MSB : %d\n", ui, getmsb (ui));
printf ("  %16lu  MSB : %d\n", ul, getmsb (ul));
printf ("  %16llu  MSB : %d\n", ull, getmsb (ull));
return 0;
}

De sortie:

             0  MSB : 0
216  MSB : 7
1021  MSB : 9
32767  MSB : 14
32768  MSB : 15
3297381253  MSB : 31
323543844043  MSB : 38

REMARQUE: pour des considérations relatives à la vitesse, à l'aide d'une seule fonction de faire la même chose centrée autour de __builtin_clzll est encore plus rapide d'un facteur de 6.

Pas le plus rapide, mais il fonctionne...

////C program
#include <math.h>
#define POS_OF_HIGHESTBIT(a) /* 0th position is the Least-Signif-Bit */    \
((unsigned) log2(a))         /* thus: do not use if a <= 0 */  
#define NUM_OF_HIGHESTBIT(a) ((!(a))          \
? 0 /* no msb set*/                   \
: (1 << POS_OF_HIGHESTBIT(a) ))
//could be changed and optimized, if it is known that the following NEVER holds: a <= 0
int main()
{
unsigned a = 5; //0b101
unsigned b = NUM_OF_HIGHESTBIT(a); //4 since 4 = 0b100
return 0; 
}

Je vais en ajouter un!

typedef unsigned long long u64;
typedef unsigned int       u32;
typedef unsigned char      u8;
u8 findMostSignificantBit (u64 u64Val)
{
u8 u8Shift;
u8 u8Bit = 0;
assert (u64Val != 0ULL);
for (u8Shift = 32 ; u8Shift != 0 ; u8Shift >>= 1)
{
u64 u64Temp = u64Val >> u8Shift;
if (u64Temp)
{
u8Bit |= u8Shift; //notice not using +=
u64Val = u64Temp;
}
}
return u8Bit;
}

Bien sûr, c'est de travailler sur une version 64 bits (unsigned long long), et non pas un tableau. En outre, beaucoup de gens ont souligné intégré g++ fonctions que je n'étais pas au courant. Comment intéressant.

De toute façon, ce trouve le bit le plus significatif en 6 itérations et donne une assertion si vous êtes passés à 0 à la fonction. Pas la meilleure fonction à utiliser si vous avez accès à une instruction du chipset.

Moi aussi, je suis aussi à l'aide de |= au lieu de += car ce sont toujours des puissances de deux, et OU est (classique) plus rapide que l'addition. Depuis que je suis seulement en ajoutant des pouvoirs uniques de 2 ensemble, je n'ai jamais rouler.

C'est un binaire de recherche, ce qui signifie qu'il trouve toujours le résultat en 6 itérations.

Encore une fois, c'est mieux:

u8 findMostSignificantBit2 (u64 u64Val)
{
assert (u64Val != 0ULL);
return (u8) (__builtin_ctzll(u64Val));
}

Ici est un simple, la force brute de l'algorithme de l'arbitraire d'un tableau de taille d'octets:

int msb( unsigned char x);  //prototype for function that returns 
// most significant bit set
unsigned char* p;
for (p = arr + num_elements; p != arr;) {
--p;
if (*p != 0) break;
}
//p is with pointing to the last byte that has a bit set, or
// it's pointing to the first byte in the array
if (*p) {
return ((p - arr) * 8) + msb( *p);
}
//what do you want to return if no bits are set?
return -1;

Je vais le laisser comme un exercice pour le lecteur de se donner un msb() de la fonction ainsi que l'optimisation de travailler sur int ou long long de la taille des interstices de données.

Pour java j'utilise ceci:

static public final int msb(int n) {
n |= n >>> 1;  
n |= n >>> 2; 
n |= n >>> 4; 
n |= n >>> 8; 
n |= n >>> 16; 
n >>>= 1;
n += 1; 
return n;
}

Et:

static public final int msb_index(int n) {
final int[] multiply_de_bruijn_bit_position = {
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
};
return multiply_de_bruijn_bit_position[(msb(n) * 0x077CB531) >>> 27];
}