Ближайшая степень двойки java

Система счисления из единиц и двоек

Доброго времени суток, уважаемые форумчане)
есть задачка с олимпиады по информатике для 7-8 классов: «Как известно, в двоичной системе счисления используются только две цифры − 0 и 1. Например, число 18 в двоичной системе запишется как 10010.
Однажды Вася задумался: а что, если вместо цифры 0 использовать цифру 2? Например, число 18 тогда запишется как 1122. Действительно, 1∙2^3 + 1∙2^2 + 2∙2^1 + 2∙2^0 = 18.
Однако, у Васи возникли сложности с переводом чисел в эту систему. Помогите ему в решении этой задачи.
Входные данные
Одно целое число N в диапазоне от 1 до 10^9.
Выходные данные
Одна строка − представление числа N в описанной системе счисления.»
В общем, если я правильно понял, числа по порядку будут такие: 1 2 11 12 21 22 111 (вместо 1 10 11 101 и т.д. в двоичной)
и я совершенно не понимаю как реализовать перевод числа, возможно, сегодня уже пересидел и не замечаю чего-то.
Слышал, что тут сидят добрые люди, помогите пожалуйста

Вывести на экран n единиц ,затем 2n двоек
построить алгоритм решения задачи в виде блок схемы Написать программу выполнения задачи на языке.

Вывести на экран n единиц, 2n двоек, затем 3n троек
Вывести на экран n единиц, 2n двоек, затем 3n троек. Число вводит пользователь.

Найти количество единиц и двоек в каждом из массивов
Написать код в Pascal ABC. Дано:масссивы E(6),G(6),F(6),S(6). Найти количество единиц и двоек в.

Подсчет в последовательности количества единиц, двоек,троек и т.д
На вход программы подается последовательность чисел от 1 до 9, заканчивающаяся 0. Всего будет.

Источник

Округлить до следующей наибольшей степени числа 2

Учитывая положительное число n , найдите следующую наивысшую степень числа 2. Если n сам по себе является степенью двойки, возврат n .

Input: n = 20
Output: 32

Input: n = 16
Output: 16

Подход 1

Идея состоит в том, чтобы сбросить самый правый бит n пока не останется только один бит, который будет последним установленным битом данного числа. Обработать случай, когда n является степенью 2, изначально уменьшается n на 1. Обратите внимание, что эта операция не повлияет на вывод, поскольку нас интересует только последний установленный бит n .

Ниже приведена реализация этой идеи на C++, Java и Python:

C++

результат:

The next power of 2 is 128

Java

результат:

The next power of 2 is 128

Python

результат:

The next power of 2 is 128

Подход 2

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

Алгоритм может быть реализован следующим образом на C++, Java и Python:

C++

результат:

The next power of 2 is 128

Java

результат:

The next power of 2 is 128

Python

результат:

The next power of 2 is 128

Подход 3

Идея состоит в том, чтобы вычислить позицию p последнего установленного бита n и вернуть число с его p+1 набор бит. Ниже приведена программа на C++, Java и Python, которая демонстрирует это:

C++

результат:

The next power of 2 is 32

Java

результат:

The next power of 2 is 32

Python

результат:

The next power of 2 is 32

Подход 4

Идея состоит в том, чтобы установить все биты справа от старшего установленного бита в 1, а затем увеличить значение на 1, чтобы “прокрутить” до ближайшей степени двойки. Например, рассмотрим число 20. Преобразуем его двоичное представление 00010100 к 00011111 и прибавьте к нему 1, что даст следующую степень числа 20. т. е. (00011111 + 1) = 00100000 .

Этот подход демонстрируется ниже на C++, Java и Python:

C++

результат:

The next power of 2 is 256

Java

результат:

The next power of 2 is 256

Python

результат:

The next power of 2 is 256

Как работает сдвиг вправо и операция побитового ИЛИ?

Возьмем в качестве примера число 131, т.е. 10000011 в двоичном формате:

n—; // 10000011 ——> 10000010
n |= n >> 1; // 10000010 | 01000001 = 11000011
n |= n >> 2; // 11000011 | 00110000 = 11110011
n |= n >> 4; // 11110011 | 00001111 = 11111111
n |= n >> 8; // … (At this point, all bits are 1, so further bitwise OR
n |= n >> 16; // operations produce no effect)
n++; // 11111111 ——> 100000000

Есть один бит в 9th положение, которое представляет 2 8 , что действительно является следующей по величине степенью числа 2. Каждый из сдвигов перекрывает все существующие биты 1 в числе с некоторыми ранее нетронутыми 0, в конечном итоге создавая общее количество битов 1, равное общему количеству битов в исходном числе. Добавление единицы к этому значению дает новую степень числа 2.

Есть несколько других возможных решений этой проблемы.

Средний рейтинг 4.82 /5. Подсчет голосов: 115

Голосов пока нет! Будьте первым, кто оценит этот пост.

Сожалеем, что этот пост не оказался для вас полезным!

Расскажите, как мы можем улучшить этот пост?

Источник

Наибольшая степень двойки, которая меньше заданного числа в Java

В этой статье мы увидим, как найти наибольшую степень двойки, меньшую заданного числа.

Для наших примеров мы возьмем образец ввода 9. 20 равно 1, наименее действительный ввод, для которого мы можем найти степень 2 меньше, чем данный ввод 2. Следовательно, мы будем рассматривать только вводы больше 1 как допустимые. .

2. Наивный подход

Давайте начнем с 20, что равно 1, и мы будем продолжать умножать число на 2, пока не найдем число, которое меньше входного :

public long findLargestPowerOf2LessThanTheGivenNumber(long input) < Assert.isTrue(input >1, "Invalid input"); long firstPowerOf2 = 1; long nextPowerOf2 = 2; while (nextPowerOf2 < input) < firstPowerOf2 = nextPowerOf2; nextPowerOf2 = nextPowerOf2 * 2; >return firstPowerOf2; >

Давайте разберемся с кодом для примера input = 9.

Начальное значение для firstPowerOf2 равно 1, а nextPowerOf2 равно 2. Как мы видим, 2

Для первой итерации firstPowerOf2 равно 2, а nextPowerOf2 равно 2 * 2 = 4. Снова 4

Для второй итерации firstPowerOf2 равно 4, а nextPowerOf2 равно 4 * 2 = 8. Теперь 8

Давайте запустим несколько тестов для проверки нашего кода:

assertEquals(8, findPowerOf2LessThanTheGivenNumber(9)); assertEquals(16, findPowerOf2LessThanTheGivenNumber(32)); 

Временная сложность нашего решения составляет O (log ₂ (N)) . В нашем случае мы повторили log ₂ (9) = 3 раза.

3. Использование Math.log

Логарифм по основанию 2 дает, сколько раз мы можем рекурсивно разделить число на 2, другими словами, логарифм ₂ числа дает степень 2 . Давайте рассмотрим несколько примеров, чтобы понять это.

log ₂ (8) = 3 и log ₂ (16) = 4. В общем, мы можем видеть, что y = log ₂ x, где x = 2y.

Следовательно, если мы находим число, которое делится на 2, мы вычитаем из него 1, чтобы избежать сценария, в котором это число является полной степенью 2.

Math.log — это журнал ₁₀ . Чтобы вычислить log ₂ (x), мы можем использовать формулу log ₂ (x) = log ₁₀ (x) / log ₁₀ (2)

public long findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(long input) < Assert.isTrue(input >1, "Invalid input"); long temp = input; if (input % 2 == 0) < temp = input - 1; >long power = (long) (Math.log(temp) / Math.log(2)); long result = (long) Math.pow(2, power); return result; >

Предполагая, что наш входной образец равен 9 , начальное значение temp равно 9.

9% 2 равно 1, поэтому наша временная переменная равна 9. Здесь мы используем деление по модулю, которое даст остаток от 9/2.

Чтобы найти log ₂ (9), мы делаем log ₁₀ (9) / log ₁₀ (2) = 0,95424 / 0,30103 ~ = 3.

Теперь результат 23, что составляет 8.

assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(9)); assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(32));

На самом деле Math.pow будет выполнять ту же итерацию, что и в подходе 1. Следовательно, мы можем сказать, что и для этого решения временная сложность составляет O (Log ₂ (N)) .

4. Побитовая техника

Для этого подхода мы будем использовать технику побитового сдвига. Во-первых, давайте посмотрим на двоичное представление степени двойки, учитывая, что у нас есть 4 бита для представления числа

Присмотревшись, мы можем заметить, что мы можем вычислить степень двойки, сдвинув влево байты для 1 . т.е. 22 — это байты сдвига влево для разряда 1 на 2 и так далее.

Давайте закодируем, используя технику битового сдвига:

public long findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(long input) < Assert.isTrue(input >1, "Invalid input"); long result = 1; long powerOf2; for (long i = 0; i < Long.BYTES * 8; i++) < powerOf2 = 1 result = powerOf2; > return result; >

В приведенном выше коде мы используем наш тип данных long , который использует 8 байтов или 64 бита. Итак, мы будем вычислять степень от 2 до 264. Мы используем оператор сдвига бит чтобы найти степень 2. Для нашего образца ввода 9 после 4-й итерации значение powerOf2 = 16 и result = 8, где мы выходим из цикла как 16> 9 вход .

assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(9)); assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(32));

public long findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(long input) < Assert.isTrue(input >1, "Invalid input"); long result = 1; for (long i = input - 1; i > 1; i--) < if ((i & (i - 1)) == 0) < result = i; break; >> return result; >

assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(9)); assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(32));