vehiculos - services flhsmv gov mvcheckweb

encontrar la posición en el número de 64 bits

Question

Estoy tratando de encontrar la posición de dos 1 en un número de 64 bits. En este caso, los que están en las posiciones 0 y 63. El código aquí devuelve 0 y 32, que es solo la mitad derecha. ¿Por qué esto no funciona?

#include<stdio.h>
void main()
{
unsigned long long number=576460752303423489;
int i;
for (i=0; i<64; i++)
{
if ((number & (1 << i))==1)
{
printf("%d ",i);
}
}
}

Answer 1

El problema podría haberse evitado en primer lugar adoptando la metodología de aplicar el operador >> a una variable, en lugar de un literal:

if ((variable >> other_variable) & 1)
...

Answer 2

En lugar de recurrir a la manipulación de bits, se pueden usar las instalaciones del compilador para realizar tareas de análisis de bits de la manera más eficiente (utilizando en muchos casos solo una instrucción de CPU).

Por ejemplo, gcc y clang proporcionan esas rutinas prácticas:

__builtin_popcountll() - number of bits set in the 64b value
__builtin_clzll() - number of leading zeroes in the 64b value
__builtin_ctzll() - number of trailing zeroes in the 64b value
__builtin_ffsll() - bit index of least significant set bit in the 64b value

Otros compiladores tienen mecanismos similares.

Answer 3

Hay dos errores en la línea

if ((number & (1 << i))==1)

que debería leer

if (number & (1ull << i))

El cambio de 1 a 1ull significa que el desplazamiento a la izquierda se realiza en un valor de tipo unsigned long long lugar de int , y, por lo tanto, la máscara de bits puede alcanzar las posiciones 32 a 63. Eliminar la comparación a 1 se debe al number & mask (donde mask solo tiene un bit establecido) es mask o 0 , y la mask solo es igual a 1 cuando i es 0.

Sin embargo, cuando hago ese cambio, la salida para mí es 0 59 , que aún no es lo que esperaba. El problema restante es que 576460752303423489 (decimal) = 0800 0000 0000 0001 (hexadecimal). 0 59 es la salida correcta para ese número. El número que deseaba es 9223372036854775809 (decimal) = 8000 0000 0000 0001 (hex).

Por cierto, main es necesario para devolver int , no void , y necesita un return 0; explícito return 0; como su última acción (a menos que esté haciendo algo más sofisticado con el código de retorno). Sí, C99 te permite omitir eso. Hacerlo de todos modos

Answer 4

Porque (1 << i) es un valor int 32 bits en la plataforma que está compilando y ejecutando. Esto se extiende luego a 64 bits para la operación & con el valor number , lo que resulta en la duplicación del bit 31 en los bits 32 a 63.

Además, estás comparando el resultado del & con 1, que no es correcto. No será 0 si el bit está establecido, pero no será 1.

Cambiar un int de 32 bits por 32 no está definido.

Además, su número de entrada es incorrecto. Los bits establecidos están en las posiciones 0 y 59 (o 1 y 60 si prefiere contar comenzando en 1).

La solución es usar (1ull << i), o de otro modo para cambiar a la derecha el valor original y & con 1 (en lugar de cambiar a la izquierda 1). Y, por supuesto, si realiza el desplazamiento a la izquierda 1 y & con el valor original, el resultado no será 1 (excepto el bit 0), por lo que debe comparar != 0 lugar de == 1 .

Answer 5

Sé que la pregunta tiene algo de tiempo y múltiples respuestas correctas, mientras que mi debe ser un comentario, pero es un poco demasiado largo para eso. Le aconsejo encapsular la lógica de comprobación de bits en una macro y no use el número 64 directamente, sino que lo calcule. Echa un vistazo here para obtener una fuente bastante completa de hacks de manipulación de bits.

#include<stdio.h>
#include<limits.h>
#define CHECK_BIT(var,pos) ((var) & (1ULL<<(pos)))
int main(void)
{
unsigned long long number=576460752303423489;
int pos=sizeof(unsigned long long)*CHAR_BIT-1;
while((pos--)>=0) {
if(CHECK_BIT(number,pos))
printf("%d ",pos);
}
return(0);
}

Answer 6

#include<stdio.h>
int main()
{
unsigned long long number = 576460752303423489;
int i;
for (i=0; i<64; i++)
{
if ((number & (1ULL << i))) //here
{
printf("%d ",i);
}
}
}

Lo primero es usar 1ULL para representar unsigned long long constante unsigned long long . El segundo está en la sentencia if , lo que quieres decir es que no debes comparar con 1 , eso solo será cierto para el bit más a la derecha.

Salida: 0 59

Es correcto porque 576460752303423489 es igual a 0x800000000000001