Как назначить самое большое n-битное целое число без знака для BigInteger в Java - PullRequest
Новая
       6

Как назначить самое большое n-битное целое число без знака для BigInteger в Java

1 голос
/ 16 августа 2010

У меня есть сценарий, в котором я работаю с большими целыми числами (например, 160 битами) и пытаюсь создать максимально возможное целое число без знака, которое может быть представлено битовым числом n во время выполнения. Точное значение n неизвестно до тех пор, пока программа не начнет выполнение и не прочитает значение из файла конфигурации. Так, например, n может быть 160, или 128, или 192, и так далее ...

Изначально я думал, что-то вроде: 

BigInteger.valueOf((long)Math.pow(2, n));

но потом я понял, что преобразование в long, которое происходит, как бы отрицательно сказывается на цели, учитывая, что long не состоит из достаточного количества битов, во-первых, для хранения результата. Есть предложения?

Ответы [ 4 ]

9 голосов
/ 16 августа 2010

На наибольшем n-битном числе без знака

Давайте сначала посмотрим, что это за число математически.

В двоичном представлении без знака наибольшее n -битное число будет иметь все биты равными 1. Давайте рассмотрим несколько примеров:

1 (2) = 1 = 2 1 - 1
11 (2) = 3 = 2 2 - 1
111 (2) = 7 =2 3 - 1
:
1………1 (2) = 2 n -1
n

Обратите внимание, что это аналогично и в десятичном формате.Наибольшее трехзначное число:

10 3 - 1 = 1000 - 1 = 999

Таким образом, подзадача поиска наибольшего n -битное число без знака вычисляет 2 n .

При вычислительной мощности 2

Современные цифровые компьютеры могут эффективно вычислять мощность двух, благодаряследующая схема:

2 0 = 1 (2)
2 1 = 10(2)
2 2 = 100 (2)
2 3 = 1000 (2)
:
2 n = 10………0 (2)
n

То есть 2 n - это просто число, бит которого n установлен в 1, а все остальноеустановите в 0 (помните, что биты нумеруются с нумерацией индексации).

Решение

Объединяя вышеприведенное, мы получаем это простое решение, используя BigInteger для нашей проблемы: 

final int N = 5;
BigInteger twoToN   = BigInteger.ZERO.setBit(N);
BigInteger maxNbits = twoToN.subtract(BigInteger.ONE);

System.out.println(maxNbits); // 31

Если шВместо этого мы использовали long, тогда мы можем написать что-то вроде этого: 

// for 64-bit signed long version, N < 64
System.out.println(
    (1L << N) - 1
); // 31

Нет операции "set bit n ", определенной для long, поэтому традиционно сдвиг битовиспользуется вместоНа самом деле, BigInteger аналог этой техники переключения также возможен: 

System.out.println(
    BigInteger.ONE.shiftLeft(N).subtract(BigInteger.ONE)
); // 31

См. Также

Дополнительные BigInteger подсказки

BigInteger имеют powметод для вычисления неотрицательной степени любого произвольного числа.Если вы работаете в модульном кольце, есть также modPow и modInverse.

Вы можете индивидуально setBit, flipBit или просто testBit.Вы можете получить общее значение bitCount, выполнить поразрядно and с другим BigInteger и shiftLeft / shiftRight и т. Д.

В качестве бонуса вы также можете вычислить gcd или проверить, является ли число isProbablePrime.

ВСЕГДА помните, что BigInteger, как и String, является неизменным .Вы не можете вызвать метод для экземпляра и ожидать, что этот экземпляр будет изменен.Вместо этого всегда присваивайте результат , возвращаемый методом, вашим переменным.

3 голосов
/ 16 августа 2010

Просто чтобы уточнить, хотите ли вы наибольший n-битный номер (т. Е. Он будет установлен на все n-битные значения). Если это так, следующее сделает это за вас: 

BigInteger largestNBitInteger = BigInteger.ZERO.setBit(n).subtract(BigInteger.ONE);

Что математически эквивалентно 2 ^ n - 1. Ваш вопрос имеет отношение к тому, как вы делаете 2 ^ n, что на самом деле является наименьшим числом n + 1 бит. Конечно, вы можете сделать это с помощью: 

BigInteger smallestNPlusOneBitInteger = BigInteger.ZERO.setBit(n);
2 голосов
/ 16 августа 2010

Я думаю, что есть метод pow непосредственно в BigInteger. Вы можете использовать его для своих целей

0 голосов
/ 16 августа 2010

Самый быстрый способ сделать это - использовать конструктор для BigInteger, который принимает byte[].

BigInteger(byte[] val), создающий объект BigInteger из массива байтов.Вы, однако, имеете дело с битами, и поэтому создание байта [], который может состоять из {127, 255, 255, 255, 255} для 39-битного целого числа, представляющего 2 ^ 40 - 1, может быть немного утомительным.

Вы также можете использовать конструктор BigInteger(String val, int radix) - который может быть более наглядным, чем то, что происходит в вашем коде, если вы не возражаете против снижения производительности при разборе строки.Затем вы можете сгенерировать строку типа val = "111111111111111111111111111111111111111", а затем вызвать BigInteger myInt = new BigInteger(val, 2); - что приведет к тому же 39-битному целому числу.

Первый вариант потребует некоторых размышлений о том, как представить ваш номер.Этот конкретный конструктор ожидает двухзначного представления числа с прямым порядком байтов.Второй, скорее всего, будет немного медленнее, но гораздо яснее.

РЕДАКТИРОВАТЬ: Исправленные числа.Я думал, что вы имели в виду представлять 2 ^ n и неправильно прочитали наибольшее значение, которое может хранить n битов.

...