Разбор задачи 231. Power of Two с Литкода

https://leetcode.com/problems/power-of-two/

Условие

Дано число n, верни true, если оно степень двойки, Иначе - false.

Число n степень двойки, если есть число x такое, что n == 2^x.

Пример 1:

Ввод: n = 1
Вывод: true
Объяснение: 2^0 = 1

Пример 2:

Ввод: n = 16
Вывод: true
Объяснение: 2^4 = 16

Пример 3:

Ввод: n = 3
Вывод: false

Ограничения:

-2^31 <= n <= 2^31 - 1

Дополнительно: Можете ли вы решить это без циклов и рекурсии?

Решение

Можно решить просто делением на 2, и не забывая проверять остаток отделения на 2.

public class Solution {
    public bool IsPowerOfTwo(int n) {
        while (n > 1)
        {
            if (n % 2 != 0)
            {
                return false;
            }
            n /= 2;
        }
        return n == 1;
    }
}

Сложность O(logN). Если точнее, то логарифм от N по основанию 2. Мы можем опускать основание логарифма, если оно константа.

Можно ли это решить за O(1)? Да, можно.
Рассмотрим n в двоичном виде.
Если n - степень двойки, то в двоичном виде это будет 1 и какое-то количество нулей. Например, 8 = 1000b, 16 = 10000b, 64 = 1000000b и т.д.
Как узнать, что единица у нас только одна?
Рассмотрим число n - 1.
Если n = 8, то n - 1 = 7 = 111b, если n = 16, то n - 1 = 15 = 1111b.
Итак, получается, что если n - степень двойки, то n - 1, это такое число, где в двоичном виде стоит 0, где в n стоит единица, и где стоят единицы, где в n были нули. n - 1 получается инверсией числа n (если n - степень двойки).

Таким образом, для определения является ли число степенью двойки можно было бы использовать n & (n - 1) == 0
Однако, есть такое число:
1000 0000 0000 0000 0000 0000 0000 0000
Это int, и это -2147483648 или по-другому int.MinValue
И его не надо учитывать.
Если у нас знаковый int, то старший бит используется для знака, поэтому в итоге будет решение такое:

public class Solution {
    public bool IsPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}

Ещё одно решение такое:

public class Solution {
    public bool IsPowerOfTwo(int n) {
       return n > 0 && int.PopCount(n) == 1;
    }
}

PopCount - это метод для подсчета числа единиц в битовом представлении.