Совершенная сила двух между двумя числами

Question

Как мне найти идеальную силу двух между двумя числами? Пример ввода: 0 и 10 Выход: 2, 4, 8

Answer 1

Найти старший бит, установленный в 1 в первом числе, скажем, он находится в позиции x, считая от младшего бита.Затем найдите старший бит, установленный на 1 во втором числе, скажем, он находится в позиции y.Числа 2 ^{x + 1} , 2 ^{x + 2} ..., 2 ^y - это числа, которые вы ищете

Answer 2

Что ж, интересная часть - «Как получить наибольшую степень 2, которая меньше или равна моей верхней границе» и то же самое для наименьшей степени 2, которая больше или равна нижней границе.

И это легко сделать без петель. Для 32-разрядных чисел без знака:

floor(x):   ; floor power of 2
    x = x | (x >> 1)
    x = x | (x >> 2)
    x = x | (x >> 4)
    x = x | (x >> 8)
    x = x | (x >> 16)
    return x - (x >> 1)

ceil(x):   ; ceiling power of 2
    x = x - 1
    x = x | (x >> 1)
    x = x | (x >> 2)
    x = x | (x >> 4)
    x = x | (x >> 8)
    x = x | (x >> 16)
    return x + 1

Вы не сможете обойти цикл вывода чисел, ну да ладно.

Answer 3

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

0  = 00000000
10 = 00001010

=>

     00000001 (1)
     00000010 (2)
     00000100 (4)
     00001000 (8)

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

Answer 4

int first=0; //**first number which is a complete power of 2 in the range!**
 for(i=low;i<high;i++){
  if(2i==(i^(i-1)+1)){
   first=i;
   break;
  }
 }

while(first!=0){
 print first;
 first*=2;
 if(first>high){
  break;
}
}

Answer 5

шагов:

1. Допустим, n1 = start_of_range, n2 = end_of_range.
2. Узнайте, сколько бит необходимо для представления n1. Назовите это b.
3. Теперь 2**b будет следующей степенью двойки после n1.
4. Должно быть легко вычислить всю силу двойок до n2 из этого.

Пример кода Python:

#!/usr/bin/python
def get_bits(n):
    b = 0
    while n:
        n = n / 2
        b += 1
    return b

def get_power_of_two_in_range(n1, n2):
    b = get_bits(n1)
    x = 2**b
    res = []
    while x < n2:
        res.append(x)
        x = x * 2
    return res

def main():
    print get_power_of_two_in_range(0, 10)

if __name__ == '__main__':
    main()

Answer 6

Сколько раз вы можете сдвинуть бит, прежде чем доберетесь до 0?