mise en œuvre rapide de trouver la puissance précédente de 2 d'un nombre

Question

Consultez le code suivant:

#include <string> 
#include <iostream> 

std::size_t preceding_pow2(std::size_t n) 
{ 
    std::size_t k = 1; 
    while (k > 0 && k < n) { 
     k <<= 1; 
    } 
    return k >> 1; 
} 

int main(int argc, char* argv[]) 
{ 
    std::size_t n = argc > 1 ? std::stoull(argv[1]) : 1ULL << 6; 
    for (std::size_t i = 0; i < n; ++i) { 
     std::cout << i << " " << preceding_pow2(i) << std::endl; 
    } 
    return 0; 
} 

Elle produit le résultat suivant:

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

Ce qui est:

• Pour 0 en entrée, la sortie est 0
• Pour 1 en entrée, la sortie est 0
• Si l'entrée est une puissance de 2, il renvoie la puissance précédent de 2
• Si l'entrée est pas une puissance de 2, il renvoie la puissance de deux qui est inférieur à ce nombre

Y aurait-il un moyen plus rapide de mettre en œuvre cette fonction pour le code haute performance?

Answer 1

Vous pouvez réécrire votre fonction avec un bit twiddling hack:

std::size_t preceding_pow2(std::size_t v) { 
    v--; 
    v |= v >> 1; 
    v |= v >> 2; 
    v |= v >> 4; 
    v |= v >> 8; 
    v |= v >> 16; 
    return (++v) >> 1; 
} 

Demo.