Может ли 5-Op Log2 (Int 32) бит взломать в Java? - PullRequest
Новая
       13

Может ли 5-Op Log2 (Int 32) бит взломать в Java?

5 голосов
/ 03 декабря 2011

Просто, чтобы уточнить, что это НЕ домашний вопрос, поскольку я видел подобные обвинения, выдвинутые против других хакерских вопросов:

Тем не менее, у меня есть этот бит взлом в 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;
}

Я хочу преобразовать это в Java.Пока что у меня есть: 

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;
    }

(обратите внимание, что это внутри моего класса битовой сортировки ...)

Во всяком случае, когда я запускаю это для тех же значений 33 и 25,Я получаю 52 в каждом случае.

Я знаю, что целые числа Java подписаны, поэтому я почти уверен, что это как-то связано с тем, почему это не получается.У кого-нибудь есть идеи, как заставить этот 5-операционный 32-разрядный целочисленный журнал 2 работать на Java?

PS Для справки, техника не моя, я позаимствовал ее здесь: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogIEEE64Float

Ответы [ 3 ]

5 голосов
/ 03 декабря 2011

Если вы на Java, вы не можете просто сделать 31 - Integer(v).numberOfLeadingZeros()? Если они реализуют это, используя __builtin_clz, это должно быть быстро.

0 голосов
/ 04 декабря 2011

Вы используете объединение, чтобы преобразовать вашу пару целых в двойное число с одинаковым битовым шаблоном.В Java вы можете сделать это с Double.longBitsToDouble , а затем преобразовать обратно с помощью Double.doubleToLongBits .Java всегда (или, по крайней мере, создает впечатление, что она всегда), имеет порядок с прямым порядком байтов, так что вам не нужна проверка порядка байтов.

Тем не менее моя попытка адаптировать ваш код в Java не сработала.Могут быть проблемы со знаком целых чисел Java.

0 голосов
/ 03 декабря 2011

Я думаю, вы не поняли значение этого кода. Код C использует union - структуру, которая отображает одну и ту же память в два или более различных полей. Это позволяет получить доступ к хранилищу, выделенному для двойника, как целые числа. В вашем Java-коде вы используете не объединение, а две разные переменные, которые отображаются в разные части памяти. Это делает взломать неудачу.

Поскольку в Java нет союзов, вам пришлось использовать сериализацию для получения желаемых результатов. Поскольку это довольно медленно, почему бы не использовать другой метод для вычисления логарифма?

...