¿Cuál es la implementación de GCC (4.6+) __builtin_clz
? ¿Corresponde a alguna instrucción de CPU en Intel x86_64 (AVX)
?Implementación de __builtin_clz
Respuesta
Se debe traducir a una instrucción Bit Scan Reverse y un restar. El BSR proporciona el índice del 1 principal, y luego puede restarlo del tamaño de palabra para obtener el número de ceros a la izquierda.
Editar: si su CPU es compatible con LZCNT (conteo de cero principal), entonces eso probablemente también lo haga, pero no todos los chips x86-64 tienen esa instrucción.
Sí, corresponde a la instrucción de la CPU BSR (bit scan reverse).
Aquí hay un código de ejemplo que puede ayudarle a:
int a=20; //10100
//trailing zeroes
cout<<__builtin_ctz(a)<<endl; //gives 2
cout<<__builtin_ctz(a<<4)<<endl; //gives 6
//leading zeroes
cout<<__builtin_clz(a)<<endl; //gives 27
cout<<__builtin_clz(a>>4)<<endl; //gives 31
cout<<__builtin_clz(0)<<endl; //gives 32
Eso está mal. Corresponde a bsr y una resta. Además, el ejemplo no agrega nada al reclamo. Y también, la pregunta está claramente etiquetada como C y se ha mencionado un compilador particular (gcc). El código de ejemplo no funcionaría. – hroptatyr
Sí, y no.
CLZ (conteo de cero inicial) y BSR (cambio de bit de reversa) están relacionados pero son diferentes. CLZ es igual (tipo ancho de bit menos uno) - BSR. CTZ (conteo de origen cero), también conocido como FFS (buscar primer conjunto) es lo mismo que BSF (avance de exploración de bit)
¡Tenga en cuenta que todos estos están indefinidos cuando se opera en cero!
Respondiendo a su pregunta, la mayoría de las veces en x86 y x86_64, __builtin_clz genera una operación BSR restada de 31 (o cualquiera que sea el ancho de su tipo), y __builting_ctz genera una operación BSF.
Si quiere saber qué ensamblador GCC está generando, la mejor manera de saber es ver. La bandera -S tendrá salida de gcc el ensamblador que genera para la entrada dada:
gcc -S -o test.S test.c
Considere:
unsigned int clz(unsigned int num) {
return __builtin_clz(num);
}
unsigned int ctz(unsigned int num) {
return __builtin_ctz(num);
}
En x86 para gcc clz (-O2) genera:
bsrl %edi, %eax
xorl $31, %eax
ret
y para ctz:
bsfl %edi, %eax
ret
Tenga en cuenta que si usted realmente quiere BSR, y no clz, es necesario hacer 31 - clz (. De enteros de 32 bits) Esto explica la XOR 31, cuando x XOR 31 == 31 - x (esto identidad sólo es cierto para los números de la de 2^y - 1) por lo tanto:
num = __builtin_clz(num)^31;
produce
bsrl %edi, %eax
ret
- 1. ¿Implementación de Javascript Array.sort?
- 2. Implementación de BufferedIterator
- 3. .net implementación de bcrypt
- 4. Implementación de un HashMap
- 5. Mejor implementación de StAX
- 6. Implementación de varios servidores
- 7. Implementación de tubería
- 8. Advertencia de implementación incompleta
- 9. Implementación de código Tornado
- 10. Implementación de Hashtable
- 11. Implementación de Java Primitive
- 12. android Implementación de viewer
- 13. Implementación de Vector Clock
- 14. Recursos de implementación automática
- 15. R * ¿Implementación de C?
- 16. Implementación correcta de min
- 17. Implementación de módulos externos
- 18. Implementación OpenJDK de System.arraycopy
- 19. Números de implementación
- 20. implementación de quicksort
- 21. coincidencia de patrones - implementación
- 22. Implementación de Trie
- 23. Implementación de aloca
- 24. Implementación de mensajería JMS
- 25. ¿Qué implementación de LOGO?
- 26. Implementación genérica de System.Runtime.Caching.MemoryCache
- 27. Implementación de HashMap personalizada
- 28. Implementación de archivos Java
- 29. Implementación de CommonJS mínima
- 30. Implementación de tabla hash
Quizás quiso probarlo? –
No lo sé, pero si está disponible, 'LZCNT' parece ser un posible candidato. (Ver http://en.wikipedia.org/wiki/SSE4) – reuben