Как найти числа являющиеся степенями числа 2

12 марта 2022 г.

Фото Янко Ферлич на Unsplash

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

Введение

Давайте зададим еще один сложный вопрос, чтобы проверить ваше понимание побитовых операторов.

Пример 01:

“`javascript

Вход: 4

Вывод: True (поскольку 4 равно 2 ^ 2)

Пример 02:

“`javascript

Вход: 12

Выход: Ложь

Постановка задачи

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

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

“`javascript

Ввод = 64

Выход: правда

Объяснение

Мы решаем эту проблему, используя оператор & в компьютерах. Есть много способов решить эту проблему, два из которых являются простыми, а один — более сложным, но лучшим решением.

Предположим, что n неотрицательно. Для этого мы используем оператор &.

Решение: метод грубой силы/наивный подход

Подсказка. Самое интересное в вычислении степени двойки состоит в том, что у них количество установленных битов равно единице.

Алгоритм

1. Прочитайте введенное значение.

1. Несколько раз разделите ввод с помощью «2».

• если n не равно 1 и если оно нечетно, мы вернем false.

• иначе истина.

Вот как будет выглядеть наш алгоритм:

Код

“`javascript

экспортировать const IsEven = (n: число): логическое значение => {

вспомогательная функция (значение: число): логическое {

если (значение === 0) {

вернуть ложь;

в то время как (значение! == 1) {

если (значение % 2 !== 0) {

вернуть ложь;

значение >>= 1;

вернуть истину;

вернуть помощник(n);

console.log(IsEven(6));

console.log(IsEven(8));

Анализ сложности

Временная сложность: O(logn)

Это требует сложности log(n). Мы можем работать лучше за постоянное время, используя алгоритм Брайана Кернигана.

Пространственная сложность: O(1)

Пространственная сложность O(1). Он не выделял дополнительного места.

Упражнение по кодированию

Сначала просмотрите приведенные выше фрагменты кода и придумайте решение. Эта задача предназначена для вашей практики, поэтому попробуйте сначала решить ее самостоятельно. Если вы застряли, вы всегда можете обратиться к решению, представленному в разделе решений. Удачи!

“`javascript

экспорт const isPow2 = (n: число): логическое значение => {

// Пишите – Ваш – Код- Здесь

вернуть ложь; // изменить это, вернуть true/false на основе входных данных

Если у вас есть ответ, отлично! Если нет, это нормально, попрактикуйтесь в подобных задачах, и вы хорошо освоите трюки с битовыми манипуляциями.

Я объясню решение ниже.

Давайте посмотрим, как мы используем алгоритм Брайана Кернигана для достижения этой цели.

Обзор решения: алгоритм Брайана Кернигана

Это считается быстрее, чем предыдущий наивный подход.

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

В двоичном коде мы идем справа налево со степенью двойки.

Например:

2^0, 2^1, 2^2, 2^3, 2^4 и так далее.

Алгоритм

Прежде чем говорить об алгоритмических шагах, просмотрите табличную форму шагов, изображающих алгоритм.

1. Если (n & (n - 1) == 0), вернуть True.

1. иначе Ложь.

Давайте визуализируем значения в таблице ниже:

Давайте посмотрим на пару примеров:

“`java

n = 4 => 00000000 00000000 00000000 00000100

п – 1 = 3 => 00000000 00000000 00000000 00000011

(n & (n – 1)) = 0 => 00000000 00000000 00000000 00000000

(n&(n - 1)), здесь это становится 0, что является истиной. Следовательно, число «4» является степенью числа 2.

“`java

n = 6 => 00000000 00000000 00000000 00000110

п – 1 = 5 => 00000000 00000000 00000000 00000101

(n & (n – 1)) = 4 => 00000000 00000000 00000000 00000100

(n&(n - 1)) равно 4, что не равно 0. Следовательно, число «6» не является степенью числа 2.

Рассмотрим оптимизированный подход.

Код

Вот причина этого решения.

“`javascript

экспортировать const IsEven = (n: число): логическое значение => {

вспомогательная функция (значение: число): логическое {

если (значение === 0) {

вернуть ложь;

возврат (значение & (значение – 1)) === 0;

вернуть помощник(n);

console.log(IsEven(6));

console.log(IsEven(8));

Мы можем еще больше упростить этот код до одной строки, показанной ниже.

“`javascript

const IsEven = (n: число): логическое значение => {

вернуть n !== 0 && (n & (n – 1)) === 0;

console.log(IsEven (6));

console.log(IsEven (8));

Анализ сложности

Временная сложность: O(1)

Время выполнения зависит от количества «1-битов» в «n». В худшем случае все биты в n являются 1-битами. С 32-битным целым числом время выполнения составляет O(1).

Пространственная сложность: O(1)

Пространственная сложность O(1). Он не выделял дополнительного места.

Дополнительно

Если вы заинтересованы в освоении битовых трюков, у меня есть курс, который понравился более чем 100 тысячам программистов.

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

Эти битовые трюки могут помочь в соревновательном программировании и собеседованиях по кодированию при запуске алгоритмов, в основном за время O (1).

Это одна из самых важных/критических тем, когда кто-то готовится к собеседованию по программированию для компаний FAANG (Facebook, Amazon, Apple, Netflix и Google).

Для начала вы начнете с изучения системы счисления и того, как она представлена. Затем вы перейдете к изучению шести различных побитовых операторов: AND, OR, NOT, XOR и битового сдвига. На протяжении всего курса вы получите массу практического опыта, работая над практическими задачами, чтобы улучшить свое понимание.

К тому времени, когда вы закончите этот курс, вы будете решать проблемы быстрее и эффективнее!! 🤩

Ссылка на мой курс: [Master Bit Manipulation for Coding Interviews] (https://www.educative.io/courses/bit-manipulation?aff=xjzd).

Совместно опубликовано [здесь] (https://ggorantala.dev/power-of-two-a-google-interview-question-java-solution?x-host=ggorantala.dev).

---

Оригинал

There’s a simple trick for this problem:

bool IsPowerOfTwo(ulong x)
{
    return (x & (x - 1)) == 0;
}

Note, this function will report true for 0, which is not a power of 2. If you want to exclude that, here’s how:

bool IsPowerOfTwo(ulong x)
{
    return (x != 0) && ((x & (x - 1)) == 0);
}

Explanation

First and foremost the bitwise binary & operator from MSDN definition:

Binary & operators are predefined for the integral types and bool. For
integral types, & computes the logical bitwise AND of its operands.
For bool operands, & computes the logical AND of its operands; that
is, the result is true if and only if both its operands are true.

Now let’s take a look at how this all plays out:

The function returns boolean (true / false) and accepts one incoming parameter of type unsigned long (x, in this case). Let us for the sake of simplicity assume that someone has passed the value 4 and called the function like so:

bool b = IsPowerOfTwo(4)

Now we replace each occurrence of x with 4:

return (4 != 0) && ((4 & (4-1)) == 0);

Well we already know that 4 != 0 evals to true, so far so good. But what about:

((4 & (4-1)) == 0)

This translates to this of course:

((4 & 3) == 0)

But what exactly is 4&3?

The binary representation of 4 is 100 and the binary representation of 3 is 011 (remember the & takes the binary representation of these numbers). So we have:

100 = 4
011 = 3

Imagine these values being stacked up much like elementary addition. The & operator says that if both values are equal to 1 then the result is 1, otherwise it is 0. So 1 & 1 = 1, 1 & 0 = 0, 0 & 0 = 0, and 0 & 1 = 0. So we do the math:

100
011
----
000

The result is simply 0. So we go back and look at what our return statement now translates to:

return (4 != 0) && ((4 & 3) == 0);

Which translates now to:

return true && (0 == 0);

return true && true;

We all know that true && true is simply true, and this shows that for our example, 4 is a power of 2.

Число является степенью двойки, поэтому только одна из двоичных цифр числа равна 1.

Например: 10000, 100, 1 и т. Д.

Видно, что если вычесть это число из 1, двоичные цифры значения результата должны быть следующими: 1111, 11, 0 и т. Д.

Характеристики этих двух чисел: когда они делают или, результатом является их сумма, например:

Результат 10000 и 1111 равен 11111, результат 100 и 11 равен 111, 1 и 0 или 1.

Таким образом, мы можем определить, является ли число степенью 2, если мы реализуем метод:

	public static boolean is2Power(int number){
		if(number<=0){
			return false;
		}
		return (number|(number-1))==(2*number-1);
	}

Сделать тест:

		for(int i = 0;i<1000;i++){
			if(is2Power(i)){
				System.out.println(i);
			}
		}

Результат:

1
2
4
8
16
32
64
128
256
512

Дополнение (еще один способ реализации):

Также может быть достигнуто путем сдвига на 1. Как упомянуто выше, если число является степенью двойки, то его двоичное представление имеет только одну цифру, поэтому, если число 1 смещено, оно всегда будет равно числу при его перемещении в определенный бит. Итак, эта реализация выглядит следующим образом:

	public static boolean is2Power(int number){
		int j = 1;
		while (number>j) {
			j<<=1;
		}
		return j==number?true:false;
	}

Проверка:

		for(int i = 0;i<10000;i++){
			if(is2Power(i)){
				System.out.println(i);
			}
		}

Результаты:

1
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192