La fonction A = 2 ^ B peut rapidement être calculée pour tout B en faisant Je serais heureux avec ne peut pas être fait aussi si ce n'est tout simplement pas possible de faire sans journaux ou une chose de type de recherche. a = 1 << b .
Qu'en est-il de l'autre sens, obtenir la valeur de B pour tout un? Il devrait être relativement rapide, de sorte que
7 Réponses :
On ne peut pas être fait sans tester le bit haut, mais la plupart des FPus de soutien modernes Log2, tout n'est donc pas perdu.
Construire une table d'apparence. Pour les entiers 32 bits, il n'y a que 32 entrées, il y a seulement 32 entrées, donc c'est O (1).
La plupart des architectures ont également une instruction pour trouver la position du bit le plus significatif d'un nombre a , qui est la valeur b . (GCC fournit le Pour un Bigint, il peut être calculé dans O (log A) en divisant à plusieurs reprises par 2. __ intégré_clz fonction pour cela .)
@JK: acutalement la table de recherche d'une BigInteger occupe une "taille infinie". Le A est celui dans A = 1 << B .
Je n'obtiens pas à quel point la table de consultation avec 32 entrées d'INT 32 bits devrait fonctionner. Toute astuce?
@Sven: non signé int table [] [2] = {{1,0}, {2,1}, {4,2}, ...} , puis vérifiez linéairement si a> = table [b] [0]
Merci d'avoir répondu. Je ne peux toujours pas voir un point dans cette table de recherche - il est plus lent que tandis que (a >> = 1) ++ b; et beaucoup plus compliqué. Habituellement, vous utilisez des tables de recherche pour accélérer les choses, comme dans Réponse de Mark Byers ' .
Pour ce genre de chose, je me réfère habituellement à cette page avec des hacks Bit:
Par exemple:
Trouver le journal Base 2 d'un entier avec une table de recherche : Il existe également quelques algorithmes O (log (n)) donnés sur cette page.
Le lien Bit Twiddling Hacks suggère une solution bien meilleure à la question sous la sous-section // ou (si vous savez que V est une puissance de 2):
Certaines architectures ont une instruction "Nombre de zéros". Par exemple, sur le bras:
MOV R0,#0x80 @ load R0 with (binary) 10000000 CLZ R1,R0 @ R1 = number of leading zeros in R0, i.e. 7
ou vous pouvez écrire:
int b = 0;
String numberS = "306180206916083902309240650087602475282639486413"
+ "866622577088471913520022894784390350900738050555138105"
+ "234536857820245071373614031482942161565170086143298589"
+ "738273508330367307539078392896587187265470464";
BigInteger a = new BigInteger(numberS);
while ((a = a.shiftRight(1)).compareTo(BigInteger.ZERO) > 0) b++;
System.out.println("b is: " + b);
Je ne pense pas que vous comprenez entièrement à quel point la notation de la Big O fonctionne.
Remarque, que A taille est constante . La seule chose qui peut vous confondre consiste à utiliser Biginteger classe et que vous n'avez même pas les opérateurs bitwises définis pour les cours.
@Margus: Pourquoi il n'y a pas d'opérateurs bitwises définis pour BigInteger?
Marge a raison pour des langues comme C, C # et Java. Mais il y en a d'autres (Ruby, Python, Haskell, JavaScript, etc.) qui n'a pas de limites sur des tailles entière.
@KennyTM - Je voulais dire que les opérateurs ne sont pas définis dans le matériel et sont émulés par des classes logicielles, cela les rend un peu plus lents.
O (1)? Si vous le dites, mais il est également linéaire dans le journal (A).
Si A est un double plutôt que d'int, il sera représenté comme une mantissée et un exposant. L'exposant est la partie que vous recherchez, car c'est le logarithme du nombre.
Si vous pouvez pirater la représentation binaire, vous pouvez obtenir l'exponent. Recherchez la norme IEEE pour voir où et comment l'exposant est stocké.
Pour une valeur intégrale, si une méthode d'obtention de la position du bit le plus significatif n'est pas disponible, vous pouvez effectuer une recherche binaire sur les bits pour la plus haute maximum 1 qui est donc O (Numbits de journal). Faire cela peut bien effectuer réellement plus vite que la conversion à un double en premier.
en Java, vous pouvez utiliser Integer.numberfleadingzeros pour calculer le logarithme binaire. Il renvoie le nombre de zéros de premier plan dans la représentation binaire, de sorte que
Est-il supposé que A est de la forme 2 ^ B (B étant entier)?