¿Se puede hacer el truco de bits 5-Op Log2 (Int 32) en Java?

Question

sólo para aclarar esto no es una cuestión tareas como he visto acusaciones similares formuladas contra otras preguntas bit-hacker:

Dicho esto, tengo este bit hackear en C:

#include <stdio.h> 

const int __FLOAT_WORD_ORDER = 0; 
const int __LITTLE_END = 0; 

// Finds log-base 2 of 32-bit integer 
int log2hack(int v) 
{ 
    union { unsigned int u[2]; double d; } t; // temp 
    t.u[0]=0; 
    t.u[1]=0; 
    t.d=0.0; 

    t.u[__FLOAT_WORD_ORDER==__LITTLE_END] = 0x43300000; 
    t.u[__FLOAT_WORD_ORDER!=__LITTLE_END] = v; 
    t.d -= 4503599627370496.0; 
    return (t.u[__FLOAT_WORD_ORDER==__LITTLE_END] >> 20) - 0x3FF; 
} 

int main() 
{ 
    int i = 25; //Log2n(25) = 4 
    int j = 33; //Log2n(33) = 5 

    printf("Log2n(25)=%i!\n", 
     log2hack(25)); 
    printf("Log2n(33)=%i!\n", 
     log2hack(33)); 

    return 0; 
} 

quiero para convertir esto a Java. Hasta ahora lo que tengo es:

public int log2Hack(int n) 
    { 
     int r; // result of log_2(v) goes here 
     int[] u = new int [2]; 
     double d = 0.0; 
     if (BitonicSorterForArbitraryN.__FLOAT_WORD_ORDER== 
       BitonicSorterForArbitraryN.LITTLE_ENDIAN) 
     { 
      u[1] = 0x43300000; 
      u[0] = n; 
     } 
     else  
     { 
      u[0] = 0x43300000; 
      u[1] = n; 
     } 
     d -= 4503599627370496.0; 
     if (BitonicSorterForArbitraryN.__FLOAT_WORD_ORDER== 
       BitonicSorterForArbitraryN.LITTLE_ENDIAN) 
      r = (u[1] >> 20) - 0x3FF; 
     else 
      r = (u[0] >> 20) - 0x3FF; 

     return r; 
    } 

(Nota que hay dentro de una clase de clasificación bitónica mío ...)

De todos modos, cuando corro esto para los mismos valores de 33 y 25, me sale en 52 cada caso

Sé que los números enteros de Java están firmados, así que estoy bastante seguro de que tiene algo que ver con por qué esto está fallando. ¿Alguien tiene alguna idea de cómo puedo hacer que este registro 2 de 5 operaciones y 32 bits funcione en Java?

P.S. Para el registro, la técnica no es mía, la tomé prestada aquí: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogIEEE64Float

Answer 1

Si está en Java, ¿no puede simplemente hacer 31 - Integer(v).numberOfLeadingZeros()? Si implementan esto usando __builtin_clz, debe ser rápido.

Answer 2

Creo que no entendiste el significado de ese código. El código C usa una unión - una estructura que asigna la misma memoria a dos o más campos diferentes. Eso hace posible acceder al almacenamiento asignado para el doble como enteros. En su código de Java, no usa una unión sino dos variables diferentes que están mapeadas en diferentes partes de la memoria. Esto hace que el truco falle.

Como Java no tiene uniones, debe usar la serialización para obtener los resultados que desea. Dado que es bastante lento, ¿por qué no utilizar otro método para calcular el logaritmo?

Answer 3

Está utilizando la unión para convertir su par de ints en un doble con el mismo patrón de bits. En Java, puede hacer eso con Double.longBitsToDouble, y luego convertir de nuevo con Double.doubleToLongBits. Java siempre (o al menos da la impresión de ser siempre) big-endian, por lo que no necesita la verificación de endianness.

Dicho esto, mi intento de adaptar su código a Java no funcionó. La firma de los enteros de Java podría ser un problema.